ArbreAVL: A-Insertion (GitHub)
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:
L'interface main() est entièrement remplacée par celle que vous connaisez déjà.
Bonne lecture ...
WikipediA: AVL tree
CodeS-SourceS: ArbreAVL: A-Insertion (GeeksforGeeks)
GitHub: harish-r/AVL Tree.cpp
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 AVLWikipediA: AVL tree
CodeS-SourceS: ArbreAVL: A-Insertion (GeeksforGeeks)
GitHub: harish-r/AVL Tree.cpp
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.