ArbreAVL: B-Insertion (AmélioréBis)
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:
// 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 ...
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
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
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.