Discussion :

[monsieurouxx]

Bonjour,
Ma question concerne le "Red-Black Tree" dans sa forme la plus classique, telle qu'elle a été décrite maintes fois déjà, par exemple ici (à partir de la page 273).

Jusqu'à présent, tous les algorithmes itératifs d'insertion que je rencontre (et j'inclus la procédure auxiliaire RB-INSERT-FIXUP le cas échéant) font appel à un certain moment à x->parent->parent, c'est-à-dire le grand-père de l'élément en cours.

Or, cela n'a pas de sens quand l'arbre est vide, ou est de hauteur 1.

Je pensais qu'il s'agissait d'une négligence du théoricien et que cela devait être pris en compte dans une implémentation concrète.
Or, je constate la même "faille" dans cette honnête implémentation en C.

Ainsi, je me demande comment il faut faire? A quel endroit l'algorithme esquive-t-il le problème d'une racine valant NIL ou tout autre problème similaire???

Un petit coup de pouce serait le bienvenu...

[pseudocode]

Ainsi, je me demande comment il faut faire? A quel endroit l'algorithme esquive-t-il le problème d'une racine valant NIL ou tout autre problème similaire???

Un petit coup de pouce serait le bienvenu...

Heu... s'il n'existe pas de grand-parent, c'est que ton arbre a au maximum 3 noeuds (1 racine et ses 2 fils). Donc il n'y a pas trop de problème de rééquilibrage.

[monsieurouxx]

Donc il n'y a pas trop de problème de rééquilibrage.

Donc d'après toi (vous) il s'agit d'une simple feignantise dans l'écriture de l'algo, qui ne prend pas tous les cas en compte?

[pseudocode]

Donc d'après toi (vous) il s'agit d'une simple feignantise dans l'écriture de l'algo, qui ne prend pas tous les cas en compte?

Non, ce n'est pas ca. C'est juste qu'il n'y a pas besoin de rééquilibrer l'arbre quand celui-ci est composé d'une racine (black) + 2 fils (red) : dans ce cas c'est un ajout dans un arbre binaire normal, donc aucune raison de chercher a calculer le grand-père.

(c'est le case #2 dans wikipedia : http://en.wikipedia.org/wiki/Red-black_tree )

[monsieurouxx]

Afin de clarifier le problème, voici les algos (RB-INSERT et RB-INSERT-FIXUP) :

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
19
20
21
22
23
24
25
RB-INSERT(T, z)
{
    y = NIL;
    x = root[T];
    while(x <> NIL)
    {
        y = x;
        if(key[z] <key[x])
            x = left[x];
        else
            x = right[x];
    }
    P[z] = y;
    if( y == NIL)
        root[T] = z;
    else
         if (key[z] < key[x])
             left[y] = z;
         else
              right[y] = z;
     left[z] = NIL;
     right[z] = NIL;
     color[z] = “RED”;
     RB-INSERT-FIXUP(T, z);
}

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
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
RB-INSERT-FIXUP(T, z)
{
    while(color[P[z]]==”RED”)
    {
        if(P[z] == left[P[P[z]])
        {
            y=right[P[P[z]];
            if(color[y]==”RED”)
            {
                 color[P[z]] = “BLACK”;
                 color[y] = “BLACK”;
                 color[P[P[z]]] = “RED”;
                 z = P[P[z]];
            }
            else
           {
                 if(z == right[P[z]])
                 {
                      z = P[z];
                      LEFT-ROTATE(T, z);
                 }
                 color[P[z]] = “BLACK”;
                 color[P[Pz]] = “RED”;
                 RIGHT-ROTATE(T,P[P[z]]);
            }
        }
        else
        {
             y=left[P[P[z]];
             if(color[y]==”RED”)
             {
                 color[P[z]] = “BLACK”;
                 color[y] = “BLACK”;
                 color[P[P[z]]] = “RED”;
                 z = P[P[z]];
             }
             else
             {
                  if(z == left[P[z]])
                  {
                      z = P[z];
                      RIGHT-ROTATE(T, z);
                  }
                  color[P[z]] = “BLACK”;
                  color[P[Pz]] = “RED”;
                  LEFT-ROTATE(T,P[P[z]]);
             }
         }
     }
     color[root[T]] = “BLACK”;
}

[pseudocode]

Afin de clarifier le problème, voici les algos (RB-INSERT et RB-INSERT-FIXUP)

Ca prouve ce que je disais. RB-INSERT c'est une insertion classique dans un arbre binaire, et RB-INSERT-FIXUP ca modifie l'arbre pour respecter les contraintes red-black.

La fonction RB-INSERT-FIXUP commence par verifier que le PARENT est "red", ce qui n'est pas le cas quand on est dans le cas Racine+2 fils. Donc on ne rentre pas dans la boucle while, et donc on ne cherche pas le grand-père.

[monsieurouxx]

La fonction RB-INSERT-FIXUP commence par verifier que le PARENT est "red", ce qui n'est pas le cas quand on est dans le cas Racine+2 fils. Donc on ne rentre pas dans la boucle while, et donc on ne cherche pas le grand-père.

Ah, d'accord, je comprends mieux.

Cas 1: quand l'arbre est nul
--> INSERT en fait la racine et affecte parent=NIL

Cas 2: quand l'arbre contient un seul element
--> INSERT effectue une simpel insertion et termine en en faisant un element rouge

Cas 3: Arbre de hauteur 2:
--> L'élement est inseré, mais INSERT-FIXUP ne fait pas l'erreur de chercher un grand-père car il détecte un élément rouge avant même de tenter cela.

(Bon, mon message manque de précision, mais je vois l'idée)
Merci beaucoup! Cas résolu.

[pseudocode]

Cas 3: Arbre de hauteur 2:
--> L'élement est inseré, mais INSERT-FIXUP ne fait pas l'erreur de chercher un grand-père car il détecte un élément rouge avant même de tenter cela.

(Bon, mon message manque de précision, mais je vois l'idée)
Merci beaucoup! Cas résolu.

voila, c'est ça.

[monsieurouxx]

[EDIT: message effacé par erreur]

[monsieurouxx]

Mince, j'ai encore une question.
Pensez-vous que TOUS les arbres peuvent partager le MEME noeud Nil, ou bien celà va-t-il poser problème?
(Ecrit mathématiquement: Soient T1 et T2 deux arbres. Si Nil[T1] = Nil[T2], alors l'algorithme produit toujours le résultat attendu).

En théorie, Nil[T] est juste une sentinelle, donc pas de risuqe d'écraser une valeur importante, si?

[pseudocode]

Mince, j'ai encore une question.
Pensez-vous que TOUS les arbres peuvent partager le MEME noeud Nil, ou bien celà va-t-il poser problème?
(Ecrit mathématiquement: Soient T1 et T2 deux arbres. Si Nil[T1] = Nil[T2], alors l'algorithme produit toujours le résultat attendu).

En théorie, Nil[T] est juste une sentinelle, donc pas de risuqe d'écraser une valeur importante, si?

Ce Nil[x] est spécifique à l'implémentation. Ca n'existe pas dans la définition algorithmique d'un black-red tree (la racine est juste le seul noeud de l'arbre qui n'a pas de parent). Donc je ne peux pas répondre a cette question d'un point de vue algo.

[monsieurouxx]

Ce Nil[x] est spécifique à l'implémentation. Ca n'existe pas dans la définition algorithmique d'un black-red tree

Justement, c'était la cause de mon problème jusquà présent.

Il semblerait que, suivant la définition duy Red-Black tree, il faille que Nil[T] soit un "véritable" noeud, et pas une simple valeur "NULL". Autrement l'algorithme ne marche pas (dès línsertion dans un arbre vide, l'algo essaie d'évaluer p[Nil[T]]).

Donc, il me semble que ma question a un sens au vu de cet algorithme.

[pseudocode]

Justement, c'était la cause de mon problème jusquà présent.

Il semblerait que, suivant la définition duy Red-Black tree, il faille que Nil[T] soit un "véritable" noeud, et pas une simple valeur "NULL". Autrement l'algorithme ne marche pas (dès línsertion dans un arbre vide, l'algo essaie d'évaluer p[Nil[T]]).

Donc, il me semble que ma question a un sens au vu de cet algorithme.

C'est un peu tordu comme manière de voir les choses. L'insertion dans un Red-Black tree est exactement la même que dans un binary tree. Et dans un binary tree il n'y a pas de noeud NIL auquel se raccroche la racine.

[monsieurouxx]

C'est un peu tordu comme manière de voir les choses. L'insertion dans un Red-Black tree est exactement la même que dans un binary tree. Et dans un binary tree il n'y a pas de noeud NIL auquel se raccroche la racine.

On est d'accord! Mais ce n'est pas moi qui ai écrit l'algo!
Et c'est une version de l'algo mondialement reconnue! (c'est celle que je retrouve systématiquement).

Avez-vous tenté l'insertion dans un arbre nul et constaté par vous même le problème lors de l'évaluation de p[nil[T]] ?

[pseudocode]

On est d'accord! Mais ce n'est pas moi qui ai écrit l'algo!
Et c'est une version de l'algo mondialement reconnue! (c'est celle que je retrouve systématiquement).

Ce n'est pas un algo mais une implémentation. Alors c'est peut-être une "implémentation mondialement reconnue", mais ca ne change pas le fait que ce n'est pas un problème d'algo. Il y a d'ailleurs plein d'implémentations de binary tree qui n'utilisent pas un noeud NIL qui serait le parent de la racine.

Si je reprend le code C donné dans ton premier post, on peut y lire :

Code :

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

1
2
3
4
5
6
7
/*  A sentinel is used for root and for nil.  These sentinels are */
/*  created when RBTreeCreate is caled.  root->left should always */
/*  point to the node which is the root of the tree.  nil points to a */
/*  node which should always be black but has aribtrary children and */
/*  parent and no key or info.  The point of using these sentinels is so */
/*  that the root and nil nodes do not require special cases in the code */

Ce qui prouve que c'est un choix d'implémentation qui permet de traiter la racine comme les autres noeuds, et donc de supprimer la gestion de certains cas dans le code.

Enfin, pour savoir si le même noeud NIL peut être utilisé pour plusieurs instances d'arbre, il faut lire le code. Et vu qu'il est détruit dans la fonction "RBTreeDestroy()", je ne pense pas qu'il soit bon de le réutiliser.