ArbreAVL: A-Insertion (GeeksforGeeks)
Description
Bonjour,
Comme pour les arbres rouge et noir, je me permets de présenter d'abord quelques codes sur l'introduction de nœuds dans un arbre AVL, téléchargés de sites web de "bonne renommée".
Par la suite, je pense également comparer de ces logiciels entre eux.
Cela nous permettra aussi de mieux différencier les arbres rouge et noir des arbres AVL.
Dans un arbre AVL (auteurs Adelson-Velsky et Landis), pour chaque nœud, la différence entre les hauteurs des deux sous-arbres right et left est au maximum 1:
-1 <= Height(right) - Height(left) <= 1.
Pour des questions de rapidité, on maintient dans chaque nœud une information sur ces hauteurs.
Certaines implémentations mémorisent (par exemple GeeksforGeeks) la hauteur de chaque nœud, et d'autres enregistrent la différence des hauteurs des enfants.
Est-ce que les deux méthodes sont à peu près équivalentes ?
Pour ce qui concerne l'implémentation de GeeksforGeeks, le programme main() qui est précédé du commentaire
/* Driver program to test above function*/
est à mon avis manifestement trop rudimentaire !
Comme précédemment, j'ai donc remplacé main() par ma propre interface qui permet de nous familiariser avec les particularités des arbres AVL, et peut-être même de l'utiliser pour mettre au point votre propre programme sur les arbres AVL.
Sur demande, la visualisation de l'arbre AVL (jusqu'à mille nœuds) apparait instantanément sur la console.
Pour chaque nœud, en plus de la valeur de la clé, j'indique entre parenthèses la "hauteur" stockée dans height.
La fonction Height() peut y être adaptée:
Bonne lecture ...
WikipediA: AVL tree
GeeksforGeeks: AVL Tree | Set 1 (Insertion)
Comme pour les arbres rouge et noir, je me permets de présenter d'abord quelques codes sur l'introduction de nœuds dans un arbre AVL, téléchargés de sites web de "bonne renommée".
Par la suite, je pense également comparer de ces logiciels entre eux.
Cela nous permettra aussi de mieux différencier les arbres rouge et noir des arbres AVL.
Dans un arbre AVL (auteurs Adelson-Velsky et Landis), pour chaque nœud, la différence entre les hauteurs des deux sous-arbres right et left est au maximum 1:
-1 <= Height(right) - Height(left) <= 1.
Pour des questions de rapidité, on maintient dans chaque nœud une information sur ces hauteurs.
Certaines implémentations mémorisent (par exemple GeeksforGeeks) la hauteur de chaque nœud, et d'autres enregistrent la différence des hauteurs des enfants.
Est-ce que les deux méthodes sont à peu près équivalentes ?
Pour ce qui concerne l'implémentation de GeeksforGeeks, le programme main() qui est précédé du commentaire
/* Driver program to test above function*/
est à mon avis manifestement trop rudimentaire !
Comme précédemment, j'ai donc remplacé main() par ma propre interface qui permet de nous familiariser avec les particularités des arbres AVL, et peut-être même de l'utiliser pour mettre au point votre propre programme sur les arbres AVL.
Sur demande, la visualisation de l'arbre AVL (jusqu'à mille nœuds) apparait instantanément sur la console.
Pour chaque nœud, en plus de la valeur de la clé, j'indique entre parenthèses la "hauteur" stockée dans height.
Tester un arbre AVL
A ma connaissance, comme pour les arbres rouge et noir, aucun cite web ne met à disposition un test de "conformité" de l'arbre AVL traité.La fonction Height() peut y être adaptée:
struct Node {
int key;
struct Node *left;
struct Node *right;
int height;
// ...
int Height() {
int leftH = 0, rightH = 0;
if (left) {
if (key <= left->key) return -1;
leftH = left->Height();
}
if (right) {
if (key >= right->key) return -1;
rightH = right->Height();
}
if (leftH == -1 || rightH == -1) return -1; // not sorted
int d = rightH-leftH; // return -2: difference too big
if (leftH == -2 || rightH == -2 || d < -1 || d > 1) return -2;
int h=1+MAX(leftH, rightH);
if (leftH == -3 || rightH == -3 || height != h) return -3; // height wrong
return h;
}
}; Dans la nouvelle interface, ce test est fait après chaque insertion.
Bonne lecture ...
Liens
WikipédiA: Arbre AVLWikipediA: AVL tree
GeeksforGeeks: AVL Tree | Set 1 (Insertion)
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.