ArbreAVL: B-Insertion (AmélioréBis)

Soyez le premier à donner votre avis sur cette source.

Vue 15 fois - Téléchargée 3 fois

Description

Bonjour,

Avec les arbres rouge et noir, après une insertion, c'était finalement avantageux de ne pas forcément utiliser des rotations pour la restauration nécessaire.

Le cas a l'air un peu moins évident pour les arbres AVL, mais essayons quand même.

Dans CodeS-SourceS: ArbreAVL: B-Insertion (Amélioré), remplaçons chaque appel à une rotation pas son code correspondant:
int Hgt(Node *n) {
  return MAX((n->sml) ? n->sml->hgt : 0, (n->big) ? n->big->hgt : 0) + 1;
}

Node *Insert(Node *n, int k) { // insert new Node(k) in subtree n
  if (n == 0) return new Node(k);
  if (k < n->key) n->sml = Insert(n->sml, k);
  else if (k > n->key) n->big = Insert(n->big, k);
  else return n; // double
  Node *x, *y;
  n->hgt = Hgt(n);
  int bal = ((n->sml) ? n->sml->hgt : 0) - ((n->big) ? n->big->hgt : 0);
  if (bal > 1) {
    if (k > n->sml->key) {
      x = n->sml;
      y = x->big;
      x->big = y->sml;
      y->sml = x;
      x->hgt = Hgt(x);
      // y->hgt = Hgt(y);
      n->sml = y;
    } else y = n->sml;
    n->sml = y->big;
    y->big = n;
    n->hgt = Hgt(n);
    y->hgt = Hgt(y);
    return y;
  } else if (bal < -1) {
    if (k < n->big->key) {
      x = n->big;
      y = x->sml;
      x->sml = y->big;
      y->big = x;
      x->hgt = Hgt(x);
      // y->hgt = Hgt(y);
      n->big = y;
    } else y = n->big;
    n->big = y->sml;
    y->sml = n;
    n->hgt = Hgt(n);
    y->hgt = Hgt(y);
    return y;
  }
  return n; // returns the new root
}
Observez les deux instructions mises en commentaire:
   // y->hgt = Hgt(y);
Elles apparaissent dans les rotations, mais ne sont pas nécessaires ici.
En effet, la "même" instruction sera effectuée quelques lignes plus loin.

En consultant ArbreAVL: C-Insertion-Performance, que je vais mettre à jour, on constate tout de même une amélioration de quelques % du temps d'exécution.

Remarque: Dans l'affichage de l'arbre AVL, je montre pour chaque noeud en plus de la hauteur hgt la différence des hauteurs des enfants qui peut être '-', ' ' ou '+'.
 
 
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: C-Insertion-Performance
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.