ArbreAVL: A-Insertion (GeeksforGeeks)

Soyez le premier à donner votre avis sur cette source.

Vue 410 fois - Téléchargée 19 fois

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.
 

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 AVL
WikipediA: AVL tree
GeeksforGeeks: AVL Tree | Set 1 (Insertion)
 

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.