Bonjour,
En mettant au point le programme "ArbreAVL: B-Insertion (AmélioréBis)", j'avais fait des "impressions intermédiaires" de quelques variables.
A ma grande surprise, j'ai alors constaté que les hauteurs des nœuds "hgt" évoluaient systématiquement par incrémentation ou décrémentation.
J'ai donc pu remplacer les appels à
int Hgt(Node *n) {
return MAX((n->sml) ? n->sml->hgt : 0, (n->big) ? n->big->hgt : 0) + 1;
}
par de simples incréments.
(A part le premier:
n->hgt = Hgt(n);
substitué par
P->hgt = max(sh, bh) + 1;
).
Ecrivons la fonction
int Hgt(Node *n) ci dessus de manière plus conventionnelle et plus facilement traductible en d'autres langages que
C ou
C++:
int Hgt(Node *n) {
int sh, bh;
if (n->sml != 0) sh = n->sml->hgt; else sh = 0;
if (n->big != 0) bh = n->big->hgt; else bh = 0;
return max(sh, bh);
}
on constate qu'elle est en fait assez "compliquée", c'est-à-dire relativement "lente".
Ce changement m'a semblé assez important et original pour qualifier ce code d'insertion AVL de "personnel":
Node *Insert(Node *P, int k) { // insert new Node(k) in subtree P
if (P == 0) return new Node(k);
if (k < P->key) P->sml = Insert(P->sml, k);
else if (k > P->key) P->big = Insert(P->big, k);
else return P; // double
Node *Q, *R;
int sh = (P->sml) ? P->sml->hgt : 0, bh = (P->big) ? P->big->hgt : 0;
P->hgt = max(sh, bh) + 1;
if (bh + 1 < sh) {
Q = P->sml; // ┌── Q ┌── Q
if (k > Q->key) { // (k)│ │ │ │
R = Q->big; // │ │ ┌── s │ └── s
Q->big = R->sml; // │ └── R ===> ── R
R->sml = Q; // │ └── b │ ┌── b
Q->hgt -= 1; // ── P └── P
} else R = Q; // (k) (k)
P->sml = R->big; // ┌── R ===> ── R
R->big = P; // │ └──Z │ ┌── Z
// ── P └── P
} else if (bh > sh + 1) {
Q = P->big; // ── P ┌── P
if (k < Q->key) { // │ ┌── s │ └── s
R = Q->sml; // │ ┌── R ===> ── R
Q->sml = R->big; // │ │ └── b │ ┌── b
R->big = Q; // (k)│ │ │ │
Q->hgt -= 1; // └── Q └── Q
} else R = Q; // ── P ┌── P
P->big = R->sml; // │ ┌── Z │ └── Z
R->sml = P; // └── R ===> ── R
// (k) (k)
} else return P; // returns the new root
P->hgt -= 2;
R->hgt = P->hgt + 1;
return R;
}
La comparaison sous
CodeS-SourceS: ArbreAVL: C-Insertion-Performance
montre que cette fois, l'amélioration est plus nette.
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: 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.