RBTree: A-Insertion (GitHub)

Télécharger le projet
Commenter

Description

Bonjour,

Suite d'un certain nombre d'essais sur des logiciels d'insertion de nœuds dans un arbre bicolore, téléchargés à partir de sites "de bonne réputation".

Git-Hub nous propose un code de bonne qualité qui fonctionne parfaitement, en particulier en ce qui concerne l'insertion:
    GitHub: anandarao/Red-Black-Tree

Par contre, le programme d'interface du logiciel (main()) présenté est plus que "rudimentaire" !
Je l'ai donc adapté à ma manière, en ajoutant également les fonctions Dispaly::Show et HeightBlack. 
struct Display {
  int nbE,lev,Lev[MaxEle],Prn[MaxEle];
  Node *Arr[MaxEle];

  void Show(Node *root,char blk,HANDLE console) {
    if (root) {nbE=0; lev=0;} else return;
    Recur(root); 
    char lin[MaxEle*CarParLin],*ln=lin,*l,*ll;
    memset(lin,' ',nbE*CarParLin);
    for (int i=0; i<nbE; ++i,ln+=CarParLin) {
      l=ln+6*Lev[i];
      if (Lev[i]) {
        int n=Prn[i]-i,m=CarParLin;
        ll=l;
        if (n>0) *l=218; else {n=-n; m=-m; *l=192;} // '┌' ou '└'
        for (int k=1; k<n; ++k) {ll+=m; *ll=179;} // '│'
      }
      *++l=196; *++l=196; *++l=196; *++l='>'; *++l=0; // "───>"
    }
    ln=lin;
    for (int i=0; i<nbE; ++i,ln+=CarParLin) {
      SetConsoleTextAttribute(console,224); std::cout << ln;
      if (Arr[i]->color>=BLACK) {
        SetConsoleTextAttribute(console,15);
        if (blk) std::cout << ' ' << blk << Arr[i]->data << " n";
        else std::cout << ' ' << Arr[i]->data << " n";
      } else {
        SetConsoleTextAttribute(console,192);
        std::cout << ' ' << Arr[i]->data << " n";
      }
    }
    SetConsoleTextAttribute(console,224);
  }

  int Recur(Node *nod) { // nod != 0
    if (nbE>=MaxEle) return 0;
    if (nod->left) {++lev; Prn[Recur(nod->left)]=nbE; --lev;}
    int num=nbE++;
    Arr[num]=nod; Lev[num]=lev;
    if (nod->right) {++lev; Prn[Recur(nod->right)]=num; --lev;}
    return num;
  }
};
copier/coller à partir de la console
Comme cette opération ignore les couleurs, j'ai introduit le 2ᵉ paramètre blk dans:
    Display::Show(Node *root,char blk,HANDLE console) {...}
Ce qui permet de distinguer dans tous les cas les nœuds noirs, à l'aide d'un préfixe, comme par exemple '#' (blk=0: aucun préfixe).

La couleur DOUBLE_BLACK, utilisée ici par GitHub est, dans la mesure du possible, ignorée.

N'affichez pas des arbres de plus de mille nœuds, il n'y a pas de protection !

La fonction HeightBlack, tout en comptant la hauteur des nœuds noirs, teste la cohérence de l'arbre rouge noir: 
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

 
Bonne lecture …
 

Liens

CodeS-SourceS: RBTree: A-Insertion (GeeksforGeeks)
GitHub: anandarao/Red-Black-Tree
 
Télécharger le projet

Codes Sources

S'inscrire maintenant

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.

Du même auteur (William VOIROL)