RBTree: A-Insertion (GeeksforGeeks)

Soyez le premier à donner votre avis sur cette source.

Vue 780 fois - Téléchargée 44 fois

Description

Bonjour,

Arbre rouge et noir (ou bicolore)

Traductions:
● En français: arbre rouge et noir, arbre bicolore.
● En anglais: RBTree, RB tree, red–black tree.
● En allemand: Rot-Schwarz-Baum.

Les arbres rouge et noir répondent aux exigences suivantes:
1) Un nœud est soit rouge soit noir;
2) La racine est noire;
3) Le parent d'un nœud rouge est noir;
4) A partir de chaque nœud, tous les chemins complets contiennent le même nombre de nœuds noirs.

Ces contraintes entraînent que le chemin complet le plus long possible (sa hauteur) ne peut être que deux fois plus long que le plus petit possible.
Un arbre rouge et noir est ainsi presque équilibré.
Comme les opérations d'insertion, de recherche et de suppression requièrent dans le pire des cas un temps proportionnel à la hauteur de l'arbre, les arbres bicolores restent efficaces, contrairement aux arbres binaires de recherche ordinaires.

En effet, à cause de la propriété 3), aucun chemin ne peut avoir deux nœuds rouges consécutifs.
Le plus petit chemin théorique de la racine à une feuille (NULL) ne contient alors que des nœuds noirs tandis que le plus grand alterne entre les nœuds rouges et noirs.
Et comme d'après la propriété 4), chacun de ces chemins contient le même nombre d'nœuds noirs, le plus grand chemin ne peut être deux fois plus grand que le plus petit.

La propriété 2) n'est pas nécessaire. Les seuls cas où la racine pourrait devenir rouge étant les deux cas où sa couleur n'a pas d'importance:
Soit la racine est le seul nœud, soit elle possède deux fils noirs.

On distingue deux méthodes de définir les nœuds: avec ou sans pointeur parent:
struct Node { // Nœud avec pointeur parent
  Node *parent, *left, *right;
  Bool color;
  int key;
  // ...
};

// ========== ou ==========

struct Node { // Nœud sans pointeur parent
  Node *left, *right;
  Bool color;
  int key;
  // ...
};
La première prend plus de place en mémoire et il faut tenir à jour la variable parent; par contre, elle semble simplifier la programmation.
La seconde nécessite l'utilisation d'un stack (le cas échéant d'un array) pour certaines routines (insertion, …).

En ce qui concerne la clé ou key, adoptons la définition habituelle et simple de nombre entier et non de texte.

Le but de cette série d'articles est de présenter d'abord deux ou trois logiciels "de bonne réputation", suivis d'un code personnel.
Puis d'en faire des comparaisons d'efficacité avec des arbres "très grands" (10⁶ à 10⁹ nœuds), car c'est dans ces cas là qu'un arbre bicolore est utile !

 
 

GeeksforGeeks.cpp

Pour commencer, utilisons le code proposé par GeeksforGeeks:
            GeeksforGeeks: C Program for Red Black Tree Insertion
Qui utilise un pointeur parent dans chaque nœud.

J'y ai modifié la fonction main() et ajouté les deux codes:
Display() (avec RecurDisplay) pour l'affichage.
HeightBlack() (avec RecurHeightBlack) pour tester l'arbre bicolore.

// Display function on console (by William VOIROL)                   //WV
const int MaxEle=256,CarParLin=121;                                  //WV
int nbE,lev,Lev[MaxEle],Prn[MaxEle];                                 //WV
Node *Arr[MaxEle];                                                   //WV
                                                                     //WV
int RecurDisplay(Node *nod) { // nod != 0                            //WV
  if (nbE>=MaxEle) return 0;                                         //WV
  if (nod->left) {++lev; Prn[RecurDisplay(nod->left)]=nbE; --lev;}   //WV
  int num=nbE++;                                                     //WV
  Arr[num]=nod; Lev[num]=lev;                                        //WV
  if (nod->right) {++lev; Prn[RecurDisplay(nod->right)]=num; --lev;} //WV
  return num;                                                        //WV
}                                                                    //WV
void RBTree::display() {                                             //WV
  if (root) {nbE=0; lev=0;} else return;                             //WV
  RecurDisplay(root);                                                //WV
  char lin[MaxEle*CarParLin],*ln=lin,*l,*ll;                         //WV
  memset(lin,' ',nbE*CarParLin);                                     //WV
  for (int i=0; i<nbE; ++i,ln+=CarParLin) {                          //WV
    l=ln+6*Lev[i];                                                   //WV
    if (Lev[i]) {                                                    //WV
      int n=Prn[i]-i,m=CarParLin;                                    //WV
      ll=l;                                                          //WV
      if (n>0) *l=218; else {n=-n; m=-m; *l=192;} // '┌' ou '└'      //WV
      for (int k=1; k<n; ++k) {ll+=m; *ll=179;} // '│'               //WV
    }                                                                //WV
    *++l=196; *++l=196; *++l=196; *++l='>'; *++l=0; // "───>"        //WV
  }                                                                  //WV
  ln=lin;                                                            //WV
  for (int i=0; i<nbE; ++i,ln+=CarParLin) {                          //WV
    SetConsoleTextAttribute(console,Fnd); printf("%s",ln);           //WV
    if (Arr[i]->color==RED) {                                        //WV
      SetConsoleTextAttribute(console,Red);                          //WV
      printf(" %i n",Arr[i]->data);                                 //WV
    } else {                                                         //WV
      SetConsoleTextAttribute(console,Black);                        //WV
      printf(" *%i n",Arr[i]->data);                                //WV
    }                                                                //WV
  }                                                                  //WV
  SetConsoleTextAttribute(console,Fnd);                              //WV
}                                                                    //WV
                                                                     //WV
int RecurHeightBlack(Node *nod) { // nod != 0                        //WV
    int leftH=0,rightH=0;                                            //WV
    if (nod->left) {                                                 //WV
      if (nod->data <= nod->left->data) return -1;                   //WV
      if (nod->color==RED && nod->left->color==RED) return -2;       //WV
      leftH=RecurHeightBlack(nod->left);                             //WV
    }                                                                //WV
    if (nod->right) {                                                //WV
      if (nod->data >= nod->right->data) return -1;                  //WV
      if (nod->color==RED && nod->right->color==RED) return -2;      //WV
      rightH=RecurHeightBlack(nod->right);                           //WV
    }                                                                //WV
    if (leftH==-1 || rightH==-1) return -1; // not sorted            //WV
    if (leftH==-2 || rightH==-2) return -2; // consecutive red nodes //WV
    if (leftH==-3 || rightH==-3 || leftH!=rightH) return -3;         //WV
                       // return -3: different number of black nodes //WV
    return leftH + ((nod->color==BLACK) ? 1 : 0);                    //WV
}  // Number of black nodes in the subtree nod                       //WV
                                                                     //WV
int RBTree::HeightBlack() { // Teste un RBTree  (by William VOIROL)  //WV
  return (root) ? RecurHeightBlack(root) : 0;                        //WV
}                                                                    //WV

Pour ces 2 fonctions, ainsi que pour d'autres modifications, les lignes contiennent //WV sur les colonnes 70 à 73.
 
 

Résultats

Inserted: 1, 3, 2
tree3: Inoder Traversal of Created Tree:
1  2  3

      ┌───> 1
 ───> *2
      └───> 3

BlackHeight = 1


Inserted: 1, 3, 2, 7, 6, 5, 4
tree7: Inoder Traversal of Created Tree:
1  2  3  4  5  6  7

      ┌───> *1
 ───> *2
      │           ┌───> 3
      │     ┌───> *4
      │     │     └───> 5
      └───> 6
            └───> *7

BlackHeight = 2



                              ┌───> 37
                        ┌───> *41
                        │     └───> 106
                  ┌───> 153
                  │     │     ┌───> 288
                  │     └───> *292
                  │           └───> 333
            ┌───> *491
            │     │     ┌───> *778
            │     └───> 1101
            │           └───> *1322
            │                 └───> 1323
      ┌───> *1478
      │     │                 ┌───> *1538
      │     │                 │     └───> 1600
      │     │           ┌───> 1726
      │     │           │     │     ┌───> 1840
      │     │           │     └───> *1842
      │     │           │           └───> 1869
      │     │     ┌───> *1942
      │     │     │     │           ┌───> 2082
      │     │     │     │     ┌───> *2190
      │     │     │     └───> 2316
      │     │     │           └───> *2382
      │     └───> 2391
      │           │                 ┌───> 2439
      │           │           ┌───> *2623
      │           │     ┌───> 2648
      │           │     │     └───> *2662
      │           └───> *2757
      │                 │     ┌───> *2859
      │                 │     │     └───> 2929
      │                 └───> 2995
      │                       └───> *3035
 ───> *3281
      │                             ┌───> 3548
      │                       ┌───> *3805
      │                 ┌───> *3811
      │                 │     │     ┌───> 3902
      │                 │     └───> *3931
      │                 │           └───> 4084
      │           ┌───> 4370
      │           │     │     ┌───> *4393
      │           │     └───> *4464
      │           │           │     ┌───> *4604
      │           │           │     │     └───> 4626
      │           │           └───> 4664
      │           │                 └───> *4771
      │     ┌───> *4827
      │     │     │                 ┌───> 4966
      │     │     │           ┌───> *5006
      │     │     │           │     └───> 5141
      │     │     │     ┌───> *5350
      │     │     │     │     └───> *5436
      │     │     └───> 5447
      │     │           │           ┌───> 5537
      │     │           │     ┌───> *5547
      │     │           │     │     └───> 5667
      │     │           └───> *5705
      │     │                 │     ┌───> *5724
      │     │                 └───> 5890
      │     │                       │     ┌───> 6118
      │     │                       └───> *6299
      │     │                             └───> 6308
      └───> 6334
            │                             ┌───> 6500
            │                       ┌───> *6541
            │                       │     └───> 6729
            │                 ┌───> 6827
            │                 │     └───> *6868
            │                 │           └───> 6944
            │           ┌───> *6962
            │           │     └───> *7035
            │           │           └───> 7376
            │     ┌───> 7421
            │     │     │                 ┌───> 7446
            │     │     │           ┌───> *7529
            │     │     │     ┌───> 7644
            │     │     │     │     └───> *7673
            │     │     └───> *7711
            │     │           └───> *8145
            │     │                 └───> 8253
            └───> *8467
                  │           ┌───> *8703
                  │     ┌───> *8716
                  │     │     │           ┌───> 8723
                  │     │     │     ┌───> *8756
                  │     │     │     │     └───> 8942
                  │     │     └───> 9040
                  │     │           └───> *9169
                  │     │                 └───> 9264
                  └───> 9358
                        │                 ┌───> 9629
                        │           ┌───> *9718
                        │     ┌───> 9741
                        │     │     └───> *9894
                        └───> *9895
                              │     ┌───> 9912
                              └───> *9954
                                    └───> 9961

BlackHeight = 4

Insert duplicate: 1942

???????
Dans la fonction Display(), j'ai fait précéder les nœuds noirs d'un '*', car les couleurs de la console ne suivent pas le copier/coller !

Comme vous pouvez le constater, le texte "After duplicate insert: 1942" n'apparait pas, car en insérant un nombre déjà inséré (double), le programme se plante malheureusement à la ligne de code 157:
            while ((pt != root) && (pt->color != BLACK) &&
              (pt->parent->color == RED))
avec l'erreur:  parent_pt a été nullptr !

Qui propose une correction ?
 
 
Bonne lecture …
 

Liens

WikipédiA: Arbre bicolore
WikipediA: Red–black tree
WikipediA: Rot-Schwarz-Baum
John Lenz: You could have invented red-black trees!
GeeksforGeeks: C Program for Red Black Tree Insertion
 

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Commenter la réponse de William VOIROL

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.