Algo sur les ABR

Bonsoir,

Alors voila un petit moment que j'essaie de trouver deux algorithmes sur les ABR, l'un qui dit si un ABR est contenu dans un autre (tout les éléments de A sont contenus dans B, A et B étant deux ABR) et le second qui dit si un ABR est de domaine plus petit qu'un autre (le plus petit élément de A est supérieur ou égal au plus petit élément de B et le plus grand élément de A est inférieur ou égal au plus grand élément de B). Les algos que j'ai fais ne marchent apparemment pas.
Le premier:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

Contenu (A: arbre, B: arbre):booleen val:Entier début si vide?(A) ET vide?(B) alors renvoyer vrai val <- A.noeud sinon si non(app?(val, B)) alors renvoyer faux fin si contenu(A.sag, B.sag) contenu(A.sad, B.sad) fin

---

Le deuxième:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

domaine (A: arbre, B: arbre):booleen val_minA, val_minB, val_maxA, val_maxB:Entier début si vide?(A) ET vide?(B) alors renvoyer vrai sinon si vide?(A) OU vide?(B) alors renvoyer faux fin si val_minA <- min(A) val_minB <- min(B) val_maxA <- max(A) val_maxB <- max(B) si val_minB <= val_minA ET val_maxA <= val_maxB alors renvoyer vrai sinon renvoyer faux fin si fin

---

Merci de l'aide que vous pourrez m'apporter :)

Voyons, supposons que mes arbres binaires soient définis ainsi :

Code:

---

data Tree a = Leaf | Node (Tree a) a (Tree a)

---

Commençons par faire la liste des éléments d'un arbre :

Code:

---

1 2 3

flatten :: Tree a -> [a] flatten Leaf = [] flatten (Node fg a fd) = flatten fg ++ (a : flatten fd)

---

On est bien d'accord que l'invariant pour un arbre binaire de recherche est le suivant :

Code:

---

1 2 3 4 5

prop_searchTree :: (Ord a) => Tree a -> Bool prop_searchTree Leaf = True prop_searchTree (Node fg a fd) = prop_searchTree fg && prop_searchTree fd && all (< a) (flatten fg) && all (> a) (flatten fd)

---

Ce qui signifie qu'on peut écrire une procédure de recherche qui nous dit si tel élément est dans un arbre ou non :

Code:

---

1 2 3 4 5 6

contains :: (Ord a) => Tree a -> a -> Bool contains Leaf _ = False contains (Node fg a fd) b | a == b = True | a < b = contains fd b | otherwise = contains fg b

---

A partir de là, une méthode naïve pour vérifier si a est un sous-ensemble de b est :

Code:

---

1 2	subsetOf :: (Ord a) => Tree a -> Tree a -> Bool subsetOf tA tB = all (contains tB) (flatten tA)

---

et on peut utiliser cela pour tester l'égalité :

Code:

---

1 2	equal :: (Ord a) => Tree a -> Tree a -> Bool equal tA tB = subsetOf tA tB && subsetOf tB tA

---

Bien sûr on peut améliorer ces méthodes, mais je te laisse le soin de le faire.

--
Jedaï

Alors je ne critique aucunement ce que tu as fait mais le seul soucis est que je ne comprend pas du tout la syntaxe du langage d'algo que tu as utilisé:oops:

C'est du Haskell (langage de haut niveau, purement fonctionnel et à évaluation paresseuse).

Quant à tes algorithmes, le second est correct (il correspond exactement à ta description en tout cas), le premier est incorrect, le début marche mais :

Code:

---

1 2	contenu(A.sag, B.sag) contenu(A.sad, B.sad)

---

ne marche pas du tout, d'une part tu ne renvoies rien, quelque soit le résultat de ces fonctions, d'autre part, A.sag n'est pas forcément contenu par B.sag même si B contient A.sag .

--
Jedaï

Ok alors pour les second si il est bon j'ai du me tromper quelque part dans mon implémentation alors:lol: par contre pour le premier je vois à peut près ce que tu veux dire, et je suppose que tu m'en donne les détails dans ta réponse précédente:) je vais donc tenté de comprendre ce que tu as écrit dans ton langage;) si j'y arrive:mrgreen:

Pour le second, il y a juste un petit problème si l'un est vide et l'autre non, tu ne traite pas ce cas, non plus que tu ne traites le cas où A est vide dans le premier.

--
Jedaï

Voila en effet pour le second cela devait être la raison pour laquelle cela ne marchait pas:) sinon pour le premier je suis toujours dans le flou, je n'arrive décidément pas à comprendre ce que tu as marqué:oops: mais je continu

La structure de liste générale (récursive) permet de représenter tous les types d'arbres (binaires ou non).
Voici un petit programme en python qui teste si tous les éléments d'une première liste sont inclus dans une autre liste, quel que soit le niveau d'imbrication des deux listes.
Je pense que les idées sont les mêmes que dans la proposition de Jedaï, simplment la syntaxe python est plus proche du pseudocode.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

def inclatom(X,L2): # teste si un atome est inclus dans une liste aplatie if L2==[]: return False # aucun atome dans la liste vide A=L2[0] # A est la tete de liste (car en lisp) B=L2[1:] # B la queue (cdr en lisp) if X==A: # si X est A OK! return True else: return inclatom (X,B) # sinon tester si l'atome est dans la queue   def flat (L): # aplatit la liste en ne gardant que les atomes au plus bas niveau if L==[]: return L A=L[0] B=L[1:] if A.__class__!=list: return [A]+flat(B) else: return flat(A)+flat(B)     def inclist (L1,L2): # teste si tous les elements de la liste L1 se retrouvent dans la liste L2 P=flat(L1) Q=flat(L2) return all ([inclatom(X,Q) for X in P])     #programme principal print inclist ([[1, 2],3],[ 4, 1, [5, 2, 3]])

---

En effet je comprend mieux le principe avec le code python, car déjà c'est un langage que je connais et donc que je peux mieux comprendre que le Haskell que je ne connait vraiment pas et dont j'ignorais même jusqu'à l'existence:mrgreen:

Voila j'ai essayé de faire un algo non récursif, mais je le transformerai en récursif si il est correct. Cet algo test seulement si A est contenu dans B. Le voici:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

contenu (A: arbre, B: arbre):booleen tmp : Arbre test : Entier début tmp <- A si (vide?(A) ET vide?(B)) OU (vide?(A) ET non vide?(B)) alors renvoyer vrai sinon si non vide?(A) ET vide?(B) alors renvoyer faux fin si tant que non vide?(A) faire si recherche (A.val, B) alors test <- 1 sinon test <- 0 fin si A <- A.sad fin tant que A <- tmp tant que non vide?(A) faire si recherche (A.val, B) alors test <- 1 sinon test <- 0 fin si A <- A.sag fin tant que si test = 1 alors renvoyer vrai sinon renvoyer faux fin si fin

---

Une bonne part de la différence tient au fait que Python est impératif alors que Haskell est fonctionnel. D'autre part les listes de Python ne sont pas aussi fortement typées donc on peut y mettre des éléments de types différents. L'approche d'Haskell est plus fortement typé (et nettement plus performante au final).

Par ailleurs, il y a d'autres différences, par exemple le test d'appartenance inclatom() travaille sur la version aplatie de l'arbre et a une complexité moins bonne que le test d'appartenance contains() d'Haskell qui travaille directement sur l'arbre et utilise sa nature d'arbre binaire de recherche.

De plus flat() et flatten() ne renvoie pas la même liste : flatten() renvoie les éléments dans l'ordre tandis que flat() dépend de la structure de l'arbre et les renvoie dans l'ordre d'un parcours infixe.

Ta solution itérative est incorrecte, elle n'explore que les chaines extrèmes de A (la plus à gauche et la plus à droite). Pour les ABR, il est vraiment préférable de travailler récursivement.

Je rappelle quel est l'équivalent de contenu() dans mon code :

Code:

---

subsetOf tA tB = all (contains tB) (flatten tA)

---

Si on intègre également les fonctions que tu n'as probablement pas dans ta librairie (contains() correspond à ton app?()) :

Code:

---

1 2 3 4 5 6

flatten Leaf = [] flatten (Node fg a fd) = flatten fg ++ (a : flatten fd)   -- Fait partie de la bibliothèque standard de Haskell : all p [] = True all p (x:xs) = p x && all p xs

---

--
Jedaï

Ok et bien je ne connaissais pas du tout ce langage fonctionnel, le seul que je connaisse est Lisp (ou Scheme).

Sinon en effet mon algo est incorrect je l'ai d'ailleurs réalisé juste un peu après l'avoir posté. Apparemment mon soucis est que je n'arrive pas à voir quand effectuer la récursion sur les noeuds:?

Et je suis vraiment désolé mais je suis vraiment paumer avec ce langage je ne comprend pas à quoi correspond cette syntaxe:oops:

Code:

---

subsetOf tA tB = all (contains tB) (flatten tA)

---

définit une fonction "subsetOf" qui prend deux arguments tA et tB. Elle retourne le résultat de l'expression "all (contains tB) (flatten tA)" qui est un appel à la fonction "all" sur les arguments "contains tB" et "flatten tA". "contains tB" est une application partielle de la fonction contains qui renvoie donc une fonction anonyme qui teste si son argument appartient à tB, "all" applique cette fonction anonyme à tous les éléments de la liste renvoyée par "flatten tA" qui contient tous les éléments de tA, "all (contains tB) (flatten tA)" vérifie donc que tous les éléments de tA appartiennent à tB.

--
Jedaï

donc si j'ai bien compris c'est comme si j'écrivais:

Code:

---

1 2 3 4

contenu (A: arbre, B: arbre):booleen début renvoyer app?(A.val, B) (mais pour toute les valeur de A) fin

---

Si c'est pas ça j'ai toujours rien compris:oops:

Tout à fait, et tu es bien d'accord que c'est ce que tu veux faire, n'est-ce pas ? Ton problème est dans ce "(mais pour toutes les valeurs de A)".

En fait tu as deux approches : soit tu construit quelque chose qui te permet de parcourir un arbre et tu fais :

Code:

---

1 2 3 4 5 6 7 8

contenu (A: arbre, B: arbre):booleen début for val in A si non app?(val, B) renvoyer faux fin renvoyer vrai fin

---

Soit tu ne construit pas cette abstraction intermédiaire et tu utilise une récursion directe :

Code:

---

1 2 3 4

contenu?(A: arbre, B: arbre):booleen début renvoyer vide?(A) OU (app?(A.val, B) ET contenu?(A.sag, B) ET contenu?(A.sad, B)) fin

---

--
Jedaï

Oui c'est bien ce que je veux. Donc si je fais:

Code:

---

1 2 3 4 5 6 7

contenu (A: arbre, B: arbre):booleen début si non app?(parcours(A), B) alors renvoyer faux fin si renvoyer vrai fin

---

la fonction parcours est:

Code:

---

1 2 3 4 5 6 7 8

parcours (A: arbre):entier début si non vide?(A) alors renvoyer A.val parcours (A.sag) parcours (A.sad) fin si fin

---

Que renvoie parcours() ? A priori tu ne testes toujours que la racine, et tu plantes si A est vide.

J'ai mis un petit addendum à mon message précédent, je pense que ça te suffira.

--
Jedaï

Je n'ai rien dit ma fonction ne marcherait pas car "parcours" renverrai toujours la même valeur.

Sinon oui en effet je comprend mieux maintenant avec ce que tu as marqué avant :) je préfère d'ailleurs la version récursive:mrgreen:

Merci beaucoup de ton aide précieuse:king: