Discussion :

[scary]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Jedai]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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ï

[scary]

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é

[Jedai]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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ï

[scary]

Ok alors pour les second si il est bon j'ai du me tromper quelque part dans mon implémentation alors 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

[Jedai]

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ï