RBTree: A-Insertion (Sedgewick)

Télécharger le projet
Commenter

Description

Bonjour,

Voici un troisième exemple d'utilisation d'un logiciel d'insertion de nœuds dans un arbre rouge et noir.

Sedgewick nous propose un logiciel très condensé en Java, qui a l'avantage de ne pas utiliser de pointeur "parent" dans chaque nœud:
    Sedgewick: RedBlackBST.java.

J'ai ajouté au fichier Tree.h une traduction en C de ce code, avec quelques adaptations, mais tout en y gardant les mêmes noms de fonctions et de variables (sauf color: red).
Par contre, j'ai éliminé la notion de value (val). 
struct Tree { // Tree.h
  Node *root = 0;
  bool duplicate;

  int Size() {return (root) ? root->Size() : 0;}

  int Height() {return (root) ? root->Height() : 0;}

  int HeightBlack() {return (root) ? root->HeightBlack() : 0;}

  Node *Search(int num) {return (root) ? root->Search(num) : 0;}

  int compare(int k, Node *nod) {
    if (k < nod->key) return -1; else if (k > nod->key) return 1; else return 0;
  }

  // -------- Depuis ici, traduction (simplifiée) de Sedgewick.java --------

  bool isRed(Node *nod) {return (nod) ? nod->red : 0;}

  Node *rotateRight(Node *h) { // h != 0
    Node *x = h->left;
    h->left = x->right;
    x->right = h;
    x->red = x->right->red;
    x->right->red = true;
    return x;
  }

  Node *rotateLeft(Node *h) { // h != 0
    Node *x = h->right;
    h->right = x->left;
    x->left = h;
    x->red = x->left->red;
    x->left->red = true;
    return x;
  }

  void flipColors(Node *h) { // h != 0
    h->red = !h->red;
    h->left->red = !h->left->red;
    h->right->red = !h->right->red;
  }

  Node *put(Node *h, int k) {
    if (duplicate) return h;
    if (h == 0) return new Node(k);

    int cmp = compare(k,h);
    if      (cmp < 0) h->left  = put(h->left,  k);
    else if (cmp > 0) h->right = put(h->right, k);
    else    {duplicate = true; return h;}

    // fix-up any right-leaning links
    if (isRed(h->right) && !isRed(h->left))       h = rotateLeft(h);
    if (isRed(h->left)  &&  isRed(h->left->left)) h = rotateRight(h);
    if (isRed(h->left)  &&  isRed(h->right))      flipColors(h);
    return h;
  }

  void put(int k) {
    duplicate = false;
    Node *h = put(root,k);
    if (!duplicate) {root = h, h->red = false;}
  }
};
Ce logiciel fonctionne bien, mais donne un arbre qui "penche" un peu à gauche (left-leaning), ou plutôt vers les petites valeurs.

Pour savoir si on a essayé d'insérer un nœud double, j'ai introduit la variable duplicate.
 
 
Bonne lecture …
 

Liens

CodeS-SourceS: RBTree: A-Insertion (GeeksforGeeks)
CodeS-SourceS: RBTree: A-Insertion (GitHub)
WikipediA: Left-leaning red–black tree
Sedgewick: 3.3 Balanced Search Trees
Sedgewick: LLRB
Sedgewick: Left-Leaning Red-Black Trees
Sedgewick: RedBlackBST.java
 
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)