ArbreAVL: B-Insertion (Personnelle-Bis)

Télécharger le projet
Commenter

Description

Bonjour,

Lors de mon premier article sur les insertions dans les arbres AVL, je m'étais posé la question s'il valait mieux, pour chaque nœud, mémoriser sa hauteur ou la différence des hauteurs de ses enfants.
Jusqu'à présent, nous avons toujours utilisé la première méthode.

De plus, lorsqu'une fonction crée un objet, elle devrait généralement retourner (le pointeur sur) ce nouvel objet.

Pourtant, les 7 codes analysés jusqu'à présent retournent la "racine" du sous-arbre ajouté ou modifié.
Il semble que la raison (principale ?) de cette manière de faire est de faciliter la création d'un code récursif assez simple !

Ce procédé modifie les hauteurs et la structure de l'arbre complet en redescendant systématiquement jusqu'à la racine globale.
Mais, souvent, les dernières opérations sont "neutres", et donc "superflues".

En s'approchant de la racine globale, il apparait que la différence des hauteurs (des deux enfants) reste plus souvent inchangé que les hauteurs elles-mêmes.

Cette idée m'a encouragé d'utiliser ici plutôt la différence dif que la hauteur hgt, et avec une méthode non récursive, c'est-à-dire itérative.

Mais du point de vue programmation, ces adaptations semblent plus difficiles que ce que nous avons vus pour l'arbre rouge et noir (CodeS-SourceS: RBTree: B-Insertion (Optimisation)):
Je peux vous avouer que le code ci-dessous n'a pas été développé "sans peine": 
struct Node {      //                 ┌─> sml: smaller
  Node *sml, *big; // Diagramme: ──> nod
  int key;         //                 └─> big: bigger
  int dif; // Difference in height of children
 
  Node(int k) {sml = big = 0; key = k; dif = 0;} // Constructor

  // ...

};

Node *Insert(int k) { // iterative, insert new Node(k) in root
  if (root == 0) {root = new Node(k); return root;}
  int idx = 0;
  bool add = true;
  Node *NN, *N, *P = root, *Q ,*R, *arr[128];
  do {
    arr[idx++] = P; 
    if (k < P->key) 
      if (P->sml) {P = P->sml; continue;}
      else {P->sml = N = NN = new Node(k); break;}
    if (k > P->key)
      if (P->big) {P = P->big; continue;}
      else {P->big = N = NN = new Node(k); break;}
    return 0; // k == P->key: Node(k) already inserted
  } while (1);
  do {
    P = arr[--idx]; // inserts N to parent P (N->key != P->key)
    if (k < P->key) {
      if (P->dif > 0) {P->sml = N; P->dif = 0; return NN;}
      if (P->dif == 0) {P->sml = N; P->dif = -1; N = P; continue;}
      Q = P->sml; // P->dif < 0 : P -
      if (k > Q->key) { 
        R = Q->big;        //    ┌─→ Q +·                    ┌─→ Q ··-(~R)
        Q->big = R->sml;   //    │   │   ┌─→ s               │   └─→ s
        R->sml = Q;        //    │   └─→ R -·+    ===>    ─→ R ·
        P->sml = R->big;   //    │       └─→ b               │   ┌─→ b
        R->big = P;        // ─→ P -                         └─→ P +··(~R)
        P->dif = (R->dif < 0) ? 1 : 0;
        Q->dif = (R->dif > 0) ? -1: 0;
        R->dif = 0;
        if (idx <= 0) {root = R; return NN;}
        P = arr[--idx]; // inserts R to parent P
        if (k < P->key) P->sml = R; else P->big = R;
        return NN;
      } // else k < Q->key
      P->sml = Q->big;     //    ┌─→ Q            ===>    ─→ Q ·
      Q->big = P;          //    │   └─→ b                   │   ┌─→ b
      P->dif = Q->dif = 0; // ─→ P -                         └─→ P ·
      if (idx <= 0) {root = Q; return NN;}
      P = arr[--idx]; // inserts Q to parent P
      if (k < P->key) P->sml = Q; else P->big = Q;
      return NN;
    } // else k > P->key
    if (P->dif < 0) {P->big = N; P->dif = 0; return NN;}
    if (P->dif == 0) {P->big = N; P->dif = 1; N = P; continue;}
    Q = P->big; // P->dif >= 0 : P +
    if (k < Q->key) {
      R = Q->sml;        // ─→ P +                         ┌─→ P ··-(~R)
      Q->sml = R->big;   //    │       ┌─→ s               │   └─→ s
      R->big = Q;        //    │   ┌─→ R -·+    ===>    ─→ R ·
      P->big = R->sml;   //    │   │   └─→ b               │   ┌─→ b
      R->sml = P;        //    └─→ Q -·                    └─→ Q +··(~R)
      P->dif = (R->dif > 0) ? -1 : 0;
      Q->dif = (R->dif < 0) ? 1 : 0;
      R->dif = 0;
      if (idx <= 0) {root = R; return NN;}
      P = arr[--idx]; // inserts R to parent P
      if (k < P->key) P->sml = R; else P->big = R;
      return NN;
    } // else  k > Q->key
    P->big = Q->sml;     // ─→ P +                         ┌─→ P ·
    Q->sml = P;          //    │   ┌─→ s                   │   └─→ s
    P->dif = Q->dif = 0; //    └─→ Q            ===>    ─→ Q ·
    if (idx <= 0) {root = Q; return NN;}
    P = arr[--idx]; // inserts Q to parent P
    if (k < P->key) P->sml = Q; else P->big = Q;
    return NN;
  } while (idx > 0);
  root = N; return NN;
}
Ce code a été un peu "étalé" pour bien séparer les différents cas et pour avantager la rapidité.

La comparaison sous
   CodeS-SourceS: ArbreAVL: C-Insertion-Performance
montre que l'effort a été récompensé !
Est-ce que cette version "Insertion AVL" serait même plus rapide que la meilleure des versions "Insertion RB" ?
 
 
Bonne lecture ...
 

Liens

CodeS-SourceS: ArbreAVL: A-Insertion (GeeksforGeeks)
CodeS-SourceS: ArbreAVL: A-Insertion (GitHub)
CodeS-SourceS: ArbreAVL: A-Insertion TheCrazyProgrammer)
CodeS-SourceS: ArbreAVL: B-Insertion (Classique)
CodeS-SourceS: ArbreAVL: B-Insertion (Amélioré)
CodeS-SourceS: ArbreAVL: B-Insertion (AmélioréBis)
CodeS-SourceS: ArbreAVL: B-Insertion (Personnelle)
CodeS-SourceS: ArbreAVL: C-Insertion-Performance
CodeS-SourceS: RBTree: B-Insertion (Optimisation)
CodeS-SourceS: RBTree: C-Insertion-Performance
 
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)