ArbreAVL: A-Insertion (GitHub)

Soyez le premier à donner votre avis sur cette source.

Vue 285 fois - Téléchargée 23 fois

Description

Bonjour,

GitHub me donne l'occasion de présenter une deuxième implémentation concernant le domaine étudié.

Comme la première, elle est "classique" et les résultats devraient être assez semblables.

Il m'a fallu utiliser un petit "truc" pour pouvoir "facilement" accéder à la structure struct node {..};, utilisée principalement dans gras>Display</gras>:
J'ai "simplement" sorti cette structure de la classe BST.

Comme d'habitude, les lignes de code modifiées de
   GeeksforGeeks: AVL Tree | Set 1 (Insertion)
se reconnaissent par le commentaire //WV dans les colonnes 70 à 73.

Attention: GitHub enregistre la hauteur - 1 dans la variable height de chaque nœud.
La fonction de Height(), qui teste également la cohérence de l'arbre AVL, à été adaptée:
  int Height() {                                                     //WV
    int leftH = 0, rightH = 0;                                       //WV
    if (left) {                                                      //WV
      if (data <= left->data) return -1;                             //WV
      leftH = left->Height();                                        //WV
    }                                                                //WV
    if (right) {                                                     //WV
      if (data >= right->data) return -1;                            //WV
      rightH = right->Height();                                      //WV
    }                                                                //WV
    if (leftH == -1 || rightH == -1) return -1; // not sorted        //WV
    int d = rightH-leftH; // return -2: difference too big           //WV
    if (leftH == -2 || rightH == -2 || d < -1 || d > 1) return -2;   //WV
    int h=1+MAX(leftH, rightH); // return -3: height wrong           //WV
    if (leftH == -3 || rightH == -3 || height != h-1) return -3;     //WV
    return h;                                                        //WV
  }                                                                  //WV

L'interface main() est entièrement remplacée par celle que vous connaisez déjà.
 
 
Bonne lecture ...
 

Liens

WikipédiA: Arbre AVL
WikipediA: AVL tree
CodeS-SourceS: ArbreAVL: A-Insertion (GeeksforGeeks)
GitHub: harish-r/AVL Tree.cpp
 

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.