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.