Comment vérifier si ma mise en œuvre de l'arbre AVL est correct?
https://stackoverflow.com/questions/3955680
-
08-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
les gars. Je pense avoir créé une mise en œuvre d'arbre AVL, mais comme AVL Tree est une structure assez complexe, je dois le tester. La question est - comment puis-je tester? Avez-vous des idées? Up Je dois ce moment les tests suivants:
-
vérification de la santé mentale de base - vérifie que pour chaque noeud est égale à la hauteur max. hauteur des nœuds enfants + 1, l'équilibre est en [-1, 1], de l'enfant gauche clé
-
vérifier que afinde sur traversal un arbre AVL (Et sur un arbre de recherche binaire dans l'ensemble) renverra les valeurs de l'ensemble pour sous-jacent;
-
vérifier qu'une hauteur d'arbre AVL est strictement inférieur à 1,44 * log2 (N + 2) -1 (y N est le nombre d'éléments) - prouvé par les créateurs d'arbre AVL;
-
contrôle visuel - ne fonctionne pas très bien, je tente de dessiner un arbre (rootNode dans la première ligne, ses enfants directs sur la ligne suivante, Childen de childen direct rootNode sur la troisième ligne et ainsi de suite) , mais qui ne fonctionne que sur les petits arbres, pour les grands arbres, il devient un désordre complet;
-
(?????) wikipedia russe dit qu'il est expérimentalement prouvé, que pour deux insertions d'un rééquilibrage nécessaire et pour cinq déménagements aussi un rééquilibrage nécessaire, mais est-il vraiment? Anglais wikipedia dit rien, et pour mon AVL un rééquilibrage nécessaire pour deux insertions ou pour quatre déménagements, ce qui est pas tout à fait la même chose.
Peut-être que ces tests sont assez, mais s'il y a des tests plus, pas difficile à mettre en œuvre, pourquoi ne pas le faire?
La solution
Une propriété clé d'un arbre AVL est que chacun de ses sous-arbres est aussi un arbre AVL. Cela signifie que couvrant les scénarios de base devraient vous donner une large couverture de la fonctionnalité d'arbre AVL.
En d'autres termes, ces tests effectués sur la structure plus petit arbre qui leur permet sont les plus importants:
- Création d'une arborescence.
- Insertion de la première valeur.
- Insertion d'une plus grande valeur.
- Insertion d'une valeur plus petite.
- Insertion d'une valeur qui provoque LL rotation.
- Idem pour les autres rotations.
- Idem pour la suppression.
- Toutes les variantes de valeurs Trouver.
Si votre mise en œuvre passe ces tests, il les passera probablement des grands arbres. Notez que la performance et l'utilisation de la mémoire ne sont pas testés ici.
Autres conseils
Dans l'esprit de toutes ces réponses, je pensais que je fournir un couple des exemples concrets pour démontrer que le cas de base ne suffit pas.
Insertion - Gauche / Droite rebalancement
Considérez ce qui suit AVL arbres binaires équilibrés pour un insérer opération:
20+ 20+ __20+__
/ / \ / \
4 4 26 4 26
/ \ / \ / \
3 9 3+ 9 21 30
/ / \
2 7 11
Insertion soit 8 ou 15 (par exemple) dans l'un de ces arbres déclenchera essentiellement le même rééquilibrage gauche / droite, mais les résultats finaux sont significativement différentes pour chaque arbre et insérer la valeur. À savoir, le lieu de destination finale de la valeur introduite et les facteurs de solde final de noeud (4) et le noeud (20) sont entièrement dépendant de la valeur relative de l'enfant droit sous le noeud (4) - le cas échéant. Un test uniquement de l'un de ces cas ne prouve pas nécessairement l'exactitude de tous les autres. Remarque: noeud (4) doit d'abord être équilibré pour ces cas; un déséquilibre initial dans le noeud (4) a finalement pas d'effet sur le noeud (20).
Cas 1a: Insérer 15
20+ 20++ 20++ 15
/ / / / \
4 => 4- => 15+ => 4 20
\ /
15 4
Cas 2a: Insérer 15
20+ 20++ 20++ 9
/ \ / \ / \ / \
4 26 => 4- 26 => 9+ 26 => 4+ 20
/ \ / \ / \ / / \
3 9 3 9- 4+ 15 3 15 26
\ /
15 3
Cas 3a: Insérer 15
__20+__ _20++_ __20++_ ___9___
/ \ / \ / \ / \
4 26 => 4- 26 => 9+ 26 => 4+ __20__
/ \ / \ / \ / \ / \ / \ / \ / \
3+ 9 21 30 3+ 9- 21 30 4+ 11- 21 30 3+ 7 11- 26
/ / \ / / \ / \ \ / \ / \
2 7 11 2 7 11- 3+ 7 15 2 15 21 30
\ /
15 2
Cas 1b: Insérer 8
20+ 20++ 20++ 8
/ / / / \
4 => 4- => 8+ => 4 20
\ /
8 4
Cas 2b: Insérer 8
20+ 20++ 20++ 9
/ \ / \ / \ / \
4 26 => 4- 26 => 9++ 26 => 4 20-
/ \ / \ / / \ \
3 9 3 9+ 4 3 8 26
/ / \
8 3 8
Cas 3b: Insérer 8
__20+__ _20++_ __20++_ ___9___
/ \ / \ / \ / \
4 26 4- 26 9+ 26 4 _20-
/ \ / \ / \ / \ / \ / \ / \ / \
3+ 9 21 30 => 3+ 9+ 21 30 => 4 11 21 30 => 3+ 7- 11 26
/ / \ / / \ / \ / \ / \
2 7 11 2 7- 11 3+ 7- 2 8 21 30
\ / \
8 2 8
Les cas les plus complexes ont été un problème pour moi quand je travaillais sur l'optimisation du calcul des facteurs d'équilibre (qui est, ajustement des facteurs d'équilibre que pour les nœuds concernés plutôt que recalculant l'arbre entier).
Supprimer - Double Rééquilibrage
Considérons maintenant ces arbres pour Supprimer opération:
2 ___6___ ___5___
/ \ / \ / \
1 4 2 9 2 8
/ \ / \ / \ / \ / \
3 5 1 4 8 B 1 3 7 A
/ \ / / \ \ / / \
3 5 7 A C 4 6 9 B
\ \
D C
noeud de suppression (1) à partir de chacun de ces arbres. Notez que le cas 1 démontre effectivement le cas 2, mais pas du tout le cas 3.
Cas 1
2 2 4
/ \ \ / \
1 4 => 4 => 2 5
/ \ / \ \
3 5 3 5 3
Cas n ° 2
___6___ ___6___ ___6___
/ \ / \ / \
2 9 2 9 4 9
/ \ / \ \ / \ / \ / \
1 4 8 B => 4 8 B => 2 5 8 B
/ \ / / \ / \ / / \ \ / / \
3 5 7 A C 3 5 7 A C 3 7 A C
\ \ \
D D D
Cas n ° 3
___5___ ___5___ ___5___ ____8____
/ \ / \ / \ / \
2 8 2 8 3 8 _5_ A
/ \ / \ \ / \ / \ / \ / \ / \
1 3 7 A => 3 7 A => 2 4 7 A => 3 7 9 B
\ / / \ \ / / \ / / \ / \ / \
4 6 9 B 4 6 9 B 6 9 B 2 4 6 C
\ \ \
C C C
Les exemples ne manquent pas de rotations AVL dans les livres et sur Internet, mais ce que je trouvais semblait arbitraire et pas un seul endroit semblait inclure des exemples simples pour les 4 cas pour insérer et supprimer.
Ce sont les cas de test le plus simple que je pourrais trouver pour les 4 types de rotations. Pour le rendre facile à décrire, je l'ai utilisé des caractères ascii comme la clé pour un test peut être exprimé sous forme de chaîne. Par exemple, la chaîne « abc » serait insérer « un », insérer « b » et insérer « c ».
Les cas de test complet créer des arbres assez compliqué donc j'ai créé deux suites de tests. Les causes premières des rotations, mais a sous-arbres vides pour les noeuds étant mis en rotation le rendant facile à voir ce qui est arrivé. La deuxième suite a des sous-arbres non vides pour tester pleinement le code de rotation.
Il semble y avoir deux nomanclature différent pour tourne - ce que j'appris en rotation 2L, certains livres appellent une rotation de droite à gauche et la rotation 2R est d'appeler une rotation de gauche à droite. Le texte ci-dessous utilisations 2R / 2L.
Ce sont les cas de tests simples pour insérer
"abc", sur l'insert de "c" nécessitera une rotation 1L
a b
\ / \
b == 1L ==> a c
\
c
« CBA », sur l'insert de « un » nécessitera une rotation 1R
c b
/ / \
b == 1R ==> a c
/
a
"PBR" sur l'insert de "b" nécessitera une rotation 2L
a b
\ / \
c == 2L ==> a c
/
b
« cab » sur l'insert de « b » nécessitera une rotation 2R
c b
/ / \
a == 2R ==> a c
\
b
Pour suppression
« bcad », sur la suppression de « un » nécessitera une rotation 1L
b c
x \ / \
a c == 1L ==> b d
\
d
« CBDA », sur la suppression de « d » nécessitera une rotation 1R
c b
/ x / \
b d == 1R ==> a c
/
a
« BDAC » sur la suppression de « un » nécessitera une rotation 2L
b c
x \ / \
a d == 2L ==> b d
/
c
« CADB » sur la suppression de « d » nécessitera une rotation 2R
c b
/ x / \
a d == 2R ==> a c
\
b
Les cas de tests plus complexes ont des sous-arbres, la plupart étant juste un seul nœud. Pour ce poste plus court, l'insert et cas de test de suppression sont combinés. L'exemple de suppression devient l'exemple d'insertion en sautant l'insertion du caractère de suppression. Par exemple, en utilisant le cas de suppression simple, 2R « CADB » devient le cas d'insertion « cabine » en sautant l'insert de « d ». Une conséquence de ceci est le double cas rotate ci-dessous nécessitent l'insertion d'un nœud supplémentaire pour garder l'arbre équilibré après l'insertion du nœud à supprimer. Il en résulte dans le cas d'insertion ne pas être minimal.
« cbedfag » sur la suppression de « un » ou de sauter « un » et l'insert de « g » nécessitera une rotation de 1 litre à c
c e
/ \ / \
b e == 1R ==> c f
x / \ / \ \
a d f b d g
\
g
« ecfbdga » sur la suppression de « g » ou de sauter « g » et l'insert de « a » besoin d'une rotation 1R à e
- e - c
/ \ / \
c f == 1R ==> b e
/ \ x / / \
b d g a d f
/
a
« ecjadhkgilbf » sur la suppression de « b » ou sauter « b » et l'insert de « f », il faudra une rotation de 2L à j puis e. Le boîtier d'insertion peut éventuellement passer l'insertion de « d ».
- e - —- h —-
/ \ / \
c j - e- j
/ \ / \ == 2L ==> / \ / \
a d h k c g i k
x / \ \ / \ / \
b g i l a d f l
/
f
« hckbeiladfjg » sur la suppression de « j » ou sauter « j » et l'insert de « g », il faudra une rotation 2R à c puis b. Le boîtier d'insertion peut éventuellement passer l'insertion de « l »
- h - - e -
/ \ / \
c k c - h -
/ \ / \ == 2R ==> / \ / \
b e i l b d f k
/ / \ x / \ / \
a d f j a g i l
\
g
Utiliser des méthodes 1 et 2 de la question pour vérifier l'arbre rééquilibré au besoin (c.-à-vérifier l'arbre est encore en ordre et équilibré). Si vous voulez être vraiment sûr, convertir les cas de tests visuels pour inclure une liste des valeurs de profondeur et l'équilibre de l'arbre final de vérifier lors d'un parcours infixe.
Si vous voulez vraiment marteler votre implémentation, vous devriez faire quelques tests boîte noire avec beaucoup de différents motifs d'ordre d'enlèvement insertion d'ordre et. Voici quelques idées qui viennent à l'esprit:
- Ordre aléatoire
- Ordre croissant
- Prix décroissant
- entrelacent les deux flux, l'un avec l'augmentation, l'une avec l'ordre décroissant
- Démarrer avec des valeurs et diverger similaires
- Retour aux extrémités et se rencontrent au milieu
- Retour aux extrémités et croix aux extrémités opposées
- Random-promenade avec vers le haut, vers le bas et les préjugés neutres
- Mélangez des insertions et des suppressions dans les combinaisons des motifs ci-dessus.
Vous devriez non seulement la correction de test, mais aussi la performance, sous réserve des motifs ci-dessus, qui peuvent nécessiter la construction des ensembles de données largish, afin que vous puissiez véritablement mesurer la performance. Tout est rapide avec 100 éléments, mais avec 10 5 éléments, la différence entre O (N 2 ) et O ( N log N ) sera énorme.
Vous devez également tester pour les mauvaises entrées, par exemple, ajout ou suppression de la même valeur deux fois (en supposant que vous ne permettez pas de doublons).
Pour insérer et supprimer, il y a un certain nombre particulier (environ cinq pour chacun, je me souviens) des opérations d'arbres qui peuvent se produire.
Vous avez besoin de mettre en place un arbre juste avant une de ces opérations telles que l'ajout d'un autre élément particulier provoquera une connue de ces opérations se produire.
Vous en inspectant l'arbre - dump it out. Ce sera un arbre assez simple, pas plus que sur les dix éléments.
Si chaque insertion / opération de suppression fonctionne correctement, vous avez validé le comportement de noyau vital de votre arbre.
(Note, l'un des (je pense qu'il a été) insérer des opérations ne peuvent pas être vérifiés de cette manière - c'est un état intermédiaire qui existe temporairement).
