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
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.