RBTree: B-Insertion (Optimisation)

Soyez le premier à donner votre avis sur cette source.

Vue 348 fois - Téléchargée 45 fois

Description

Bonjour,

En introduisant les résultats de mon propre code "RBTree: B-Insertion (Personnelle)" dans "C-Insertion-Performance", j'ai remarqué qu'il améliorait les temps d'exécution de quelques %.

Un autre avantage est qu'il n'utilise pas le pointeur parent dans chaque nœud (comme Sedgewick).

Par contre, l'arbre résultant n'est pas très régulier, c'est-à-dire que sa hauteur (Height) et sa hauteur en nœuds noirs (HeightBlack) sont grandes par rapport aux logiciels classiques.

Alors, je me suis remis à "l'ouvrage", en considérant cette fois la notion d'oncle.
En effet, en "ratissant" plus large dès le début, on risque de retrouver un résultat plus régulier à la fin.
Je m'approche donc de la l'algorithme classique, mais sans utiliser les rotations:
struct RBNode { // RBNode.h
  RBNode *sml, *big; //                 ┌─> sml: smaller
  int key;           // Diagramme: ──> nod
  bool black;        //                 └─> big: bigger

  // ...

};

struct RBTree { // RBTree.h
  RBNode *root = 0;

  // ...

  RBNode *Insert(int key) { // insert new RBNode(key) dans root
    int idx = 0;
    RBNode *arr[128], *r = root, *p, *g, *u; // p: parent; g: grandparent; u: uncle
    if (root) do {
      arr[idx++] = r;
      if (key < r->key)
        {if (r->sml) {r = r->sml; continue;} else break;}
      if (key > r->key)
        {if (r->big) {r = r->big; continue;} else break;}
      return 0; // key == r->key: double, already inserted
    } while (1);
    RBNode *k = new RBNode(key), *n = k; // n, k: new RBNode(key)
    while (idx > 0) {
      p = arr[--idx];
      if (n->key < p->key) p->sml = n; else p->big = n;
      if (p->black||n->black) return k; // parent black or n black
      if (idx > 0) g = arr[--idx]; else break; // no grandparent
      u = (p == g->sml) ? g->big: g->sml;
      if (u != 0 && u->black == false) { // uᴿ
        g->black = false;   //         ┌── nᴿ                      ┌── nᴿ
        p->black = true;    //     ┌── pᴿ            ====>      ── pᴮ
        u->black = true;    //  ── gᴮ         (4 possibilities)    └── gᴿ
        n = g;              //     └── uᴿ                              └── uᴮ
      } else if (p == g->sml) { // uᴮ               pᴿ < gᴮ
        if (n == p->sml) {  //                      nᴿ < pᴿ
          g->black = false; //         ┌── nᴿ                      ┌── nᴿ
          g->sml = p->big;  //     ┌── pᴿ                       ── pᴮ
          p->black = true;  //     │   └── x         ====>         │   ┌── x
          p->big = g;       //  ── gᴮ                              └── gᴿ
          n = p;            //     └── uᴮ                              └── uᴮ
        } else {            //                      pᴿ < nᴿ
          g->black = false; //     ┌── pᴿ                          ┌── pᴿ
          g->sml = n->big;  //     │   │   ┌── x                   │   └── x
          p->big = n->sml;  //     │   └── nᴿ        ====>      ── nᴮ
          n->black = true;  //     │       └── y                   │   ┌── y
          n->sml = p;       //  ── gᴮ                              └── gᴿ
          n->big = g;       //     └── uᴮ                              └── uᴮ
        }
      } else {              // uᴮ                   gᴮ < pᴿ
        if (n == p->big) {  //                      pᴿ < nᴿ
          g->black = false; //     ┌── uᴮ                              ┌── uᴮ
          g->big = p->sml;  //  ── gᴮ                              ┌── gᴿ
          p->black = true;  //     │   ┌── x         ====>         │   └── x
          p->sml = g;       //     └── pᴿ                       ── pᴮ
          n = p;            //         └── nᴿ                      └── nᴿ
        } else {            //                      nᴿ < pᴿ
          g->black = false; //     ┌── uᴮ                              ┌── uᴮ
          g->big = n->sml;  //  ── gᴮ                              ┌── gᴿ
          p->sml = n->big;  //     │       ┌── x                   │   └── x
          n->black = true;  //     │   ┌── nᴿ        ====>      ── nᴮ
          n->big = p;       //     │   │   └── y                   │   ┌── y
          n->sml = g;       //     └── pᴿ                          └── pᴿ
        }
      } // RBNode z in a diagramme ► zᴮ: z black; zᴿ: z red; z: z any color
    } // while (idx > 0)
    root = n; n->black = true; return k;
  } // By William VOIROL, Switzerland, CodeS-SourceS: 15 jan 2019.

  // ...

};

Faites un essai avec l'interface en compilant Optimisation.cpp.
La "représentation graphique" sur la console montre que l'arbre résultant semble plus régulier.

Avec des tests "sérieux", je vais prochainement mettre à jour l'article évolutif RBTree: C-Insertion-Performance.
 
 
Bonne lecture …
 

Liens

CodeS-SourceS: RBTree: A-Insertion (GeeksforGeeks)
CodeS-SourceS: RBTree: A-Insertion (GitHub)
CodeS-SourceS: RBTree: A-Insertion (Sedgewick)
CodeS-SourceS: RBTree: B-Insertion (Personnelle)
CodeS-SourceS: RBTree: C-Insertion-Performance
 

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.