RBTree: B-Insertion (Personnelle)

Télécharger le projet
Commenter

Description

Bonjour,

Depuis bien des années, en regardant l'algorithme classique d'insertion d'un nœud dans un arbre bicolore, je me posais la question sur les avantages de l'utilisation de "rotations" pour réparer l'arbre.
Les codes basés sur l'algorithme classique peuvent s'étendre sur plusieurs pages.

Ne serait-il pas mieux de considérer autrement les situations "critiques" à restaurer.
C'est-à-dire en les mettant en face des situations corrigées, et d'écrire le code qui réalise cette restructuration ?

Après plusieurs essais, j'ai constaté qu'il était possible de simplifier bien des choses:
● Il n'est pas indispensable d'envisager l'idée de "rotations".
● Il n'est pas obligatoire de considérer l'oncle (souvent appelé "sibling": frère du père).
● Il n'est pas nécessaire de munir chaque nœud du pointeur parent.
● La recherche de l'emplacement de l'insertion peut être itérative.
● Le code s'écrit sur assez peu de lignes d'instructions.

Mais ce nouveau code (fonction Insert(k) dans RBTree.h) n'a pas été obtenu "sans peine".
Au début, il comportait bien le double d’instructions !
En effet, chaque "simplification" ou "amélioration" a nécessité de nombreux tests et corrections, et souvent aussi de "déceptions".

Remarque:
Les théoréticiens montrent que pour un RBTree, on a height <= 2·log₂(n+1).
Par exemple, pour n = 2³²-1 = 4294967295 nœuds, on a height <= 64, et le stack peut aisément être remplacé par un array de 64 éléments.
(Cette capacité peut être doublée en ajoutant deux éléments à l'array).

Cela m'a permis d'éliminer (dans chaque nœud) le pointeur parent en introduisant RBNode *arr[128], utilisé comme "stack". 

struct RBNode { // RBNode.h
  RBNode *sml, *big; //                 ┌─> sml: smaller
  int key;           // Diagramme: ──> nod
  bool black;        //                 └─> big: bigger

  RBNode(int k) {sml = 0; big = 0; key = k; black = false;} // constructor

  // ...

};

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

  // ...

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

};
Le code de la seconde partie:
    gᴮ < pᴿ: lignes 38-49 correspond à
    pᴿ < gᴮ: lignes 25-36, en intervertissant sml et big.
 
Il est bien sûr intéressant de comparer ce logiciel personnel avec ceux déjà étudiés.
Ce sera fait ces prochains jours dans CodeS-SourceS: RBTree: C-Insertion-Performance !

Attention: Souvent, ce type de routine retourne la (nouvelle) racine.
Ici, par contre, on retourne le nœud nouvellement créé new RBNode(k).

Merci de me faire parvenir les coordonnées d'articles sur les arbres bicolores, mais qui n'utilisent pas la notion d'oncle !
 
Remarque:
Il y a peu de temps, j'ai découvert l'article Wisconsin-Madison: Red-Black Trees.
Ils utilisent également, à la place de rotations, la comparaison des "états" avant (Before restructuring) et après (After restructuring).
Mais la solution après proposée ici est différente de la leur.
On n'a plus besoin de considérer l'oncle (frère du père ou sibling) et d'éliminer leur Case 2b: red sibling.
Malheureusement, cet article n'est pas accompagné d'un code.
Malheureusement effectivement, car l'auteur se serait aperçu que les schémas 2 et 4 (sur les 5 de Case 2:) sont erronés ! 
          │                           │
    ┌─────Gᴮ──┐                    ┌──Kᴮ──┐
    │         │          faux      │      │
  ┌─Pᴿ─┐    ┌─Sᴮ─┐      =====>   ┌─Pᴿ     Gᴿ──┐
  │    │    │    │               │            │
  1    Kᴿ   2    3               1          ┌─Sᴮ─┐
                                            │    │
                                            2    3


             │                            │
    ┌────────Gᴮ──┐                   ┌────Kᴮ───┐
    │            │       juste       │         │
  ┌─Pᴿ──┐        Sᴮ      =====>    ┌─Pᴿ─┐    ┌─Gᴿ─┐
  │     │                          │    │    │    │
  1   ┌─Kᴿ─┐                       1    2    3    Sᴮ
      │    │
      2    3
En effet, après le cas de changement de couleurs (case 2b:), le nœud Kᴿ peut avoir des enfants: ici 2 et 3 !
 
 
Bonne lecture …
 

Liens

CodeS-SourceS: RBTree: A-Insertion (GeeksforGeeks)
CodeS-SourceS: RBTree: A-Insertion (GitHub)
CodeS-SourceS: RBTree: A-Insertion (Sedgewick)
CodeS-SourceS: RBTree: C-Insertion-Performance
Wisconsin-Madison: Red-Black Trees
 
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)