ArbreAVL: B-Insertion (Amélioré)

Télécharger le projet
Commenter

Description

Bonjour,

Avez-vous trouvé des améliorations que l'on pourrait apporter au code de l'article
   ArbreAVL: B-Insertion (Classique) ?
En attendant, je vous propose déjà quatre "réctifications".

Remarque: Dans l'article mentionné ci-dessus, j'utilise #include "Node.cpp" pour insérer un bout de code écrit sur un fichier séparé.
Ceci n'est pas très "standard", mais permet d'éviter d'attacher explicitement ce fichier au projet.
Pour éviter de possibles problèmes avec certains compilateurs, j'ai remplacé cet include directement par le code concerné (avant l'interface).
 

Amélioration 1: Mémoire

Dans les trois implémentations téléchargées, Node est défini comme suit: 
Node {
  int key;
  Node *sml, *big;
  int hgt;
};
Intéressons-nous à la taille mémoire de cet élément:
En compilant sous 32 bits, on trouve (avec sizeof) 16 octets.
Sous 64 bits (ce qui est aujourd'hui recommandé) on a 32 octets.
Ecrivons maintenant: 
Node {
  Node *sml, *big;
  int key, hgt;
};
on obtient (respectivement) 16 et 24 octets !rr
Ceci résulte de l'"alignement" des variables sur 4 ou 8 octets, c'est-à-dire 32 ou 64 bits.
L'ancienne définition de la structure était bonne du temps des 32 bits, mais pas avec 64.
 

Amélioration 2: Balance

La fonction int Balance(Node *nod) est complète pour tous les cas, aussi pour nod=0. 
int Balance(Node *nod) {
  return (nod) ? Hgt(nod->sml) - Hgt(nod->big) : 0;
}

Node *Insert(Node *nod, int k) { // insert new Node(k) in subtree nod
  if (nod) {
    if (k < nod->key) nod->sml = Insert(nod->sml, k);
    else if (k > nod->key) nod->big = Insert(nod->big, k);
    else return nod; // double
  } else return new Node(k);
  nod->hgt = 1 + MAX(Hgt(nod->sml), Hgt(nod->big));
  int bal = Balance(nod);
  if (bal > 1 && k < nod->sml->key) return RotBig(nod);
  if (bal < -1 && k > nod->big->key) return RotSml(nod);
  if (bal > 1 && k > nod->sml->key)
    {nod->sml = RotSml(nod->sml); return RotBig(nod);}
  if (bal < -1 && k < nod->big->key)
    {nod->big = RotBig(nod->big); return RotSml(nod);}
  return nod; // returns the new root
}

Mais lors de la seule utilisation au milieu de Node *Insert(Node *nod, int k), on sait que nod existe (!= 0) et on peut donc remplacer:
   int bal = Balance(nod);
simplement par:
   int bal = Hgt(nod->sml) - Hgt(nod->big);
et éviter un test if (nod).
 

Amélioration 3: trop de comparaisons

Après l'instruction corrigée ci-dessus, on fait les tests pour déterminer la nécessité de rotations: 
  // ...
  if (bal > 1 && k < nod->sml->key) return RotBig(nod);
  if (bal < -1 && k > nod->big->key) return RotSml(nod);
  if (bal > 1 && k > nod->sml->key)
    {nod->sml = RotSml(nod->sml); return RotBig(nod);}
  if (bal < -1 && k < nod->big->key)
    {nod->big = RotBig(nod->big); return RotSml(nod);}
  return nod; // returns the new root
Malheureusement, lorsque elles sont évitables (et qu'on arrive la dernière instruction de la fonction (return nod;), on aura testé  (bal > 1) et aussi (bal < -1)  deux fois !
Corrigeons cela: 
    // ...
    if (bal > 1) {
    if (k < nod->sml->key) return RotBig(nod);
    if (k > nod->sml->key) {nod->sml = RotSml(nod->sml); return RotBig(nod);}
  }
  if (bal < -1) {
    if (k > nod->big->key) return RotSml(nod);
    if (k < nod->big->key) {nod->big = RotBig(nod->big); return RotSml(nod);}
  }
  return nod; // returns the new root

Amélioration 4: variable inutile

Dans les codes: 
Node *RotBig(Node *y) {
  Node *x = y->sml;
  Node *xb = x->big;
  x->big = y;
  y->sml = xb;
  y->hgt = MAX(Hgt(y->sml), Hgt(y->big)) + 1;
  x->hgt = MAX(Hgt(x->sml), Hgt(x->big)) + 1;
  return x;
}

Node *RotSml(Node *x) {
  Node *y = x->big;
  Node *ys = y->sml;
  y->sml = x;
  x->big = ys;
  x->hgt = MAX(Hgt(x->sml), Hgt(x->big)) + 1;
  y->hgt = MAX(Hgt(y->sml), Hgt(y->big)) + 1;
  return y;
}
l'utilisation des variables xb ou ys peut être évitée: 
Node *RotBig(Node *y) {
  Node *x = y->sml;
  y->sml = x->big;
  x->big = y;
  y->hgt = MAX(Hgt(y->sml), Hgt(y->big)) + 1;
  x->hgt = MAX(Hgt(x->sml), Hgt(x->big)) + 1;
  return x;
}

Node *RotSml(Node *x) {
  Node *y = x->big;
  x->big = y->sml;
  y->sml = x;
  x->hgt = MAX(Hgt(x->sml), Hgt(x->big)) + 1;
  y->hgt = MAX(Hgt(y->sml), Hgt(y->big)) + 1;
  return y;
}

L'introduction de ces corrections dans CodeS-SourceS: ArbreAVL: C-Insertion-Performance montre que ce sont vraiment des "améliorations".
 
 
Bonne lecture ...
 

Liens

WikipédiA: Arbre AVL
WikipediA: AVL tree
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: 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)