RBTree: A-Insertion (GeeksforGeeks)
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:
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: 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.
Pour ces 2 fonctions, ainsi que pour d'autres modifications, les lignes contiennent //WV sur les colonnes 70 à 73.
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 …
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
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 bicoloreWikipediA: Red–black tree
WikipediA: Rot-Schwarz-Baum
John Lenz: You could have invented red-black trees!
GeeksforGeeks: C Program for Red Black Tree Insertion
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.