Comment vérifier si mon arbre AVL de la mise en œuvre est correcte?

les gars.
Je pense que j'ai créé un arbre AVL de mise en œuvre, mais comme Arbre AVL est une structure assez complexe, j'ai besoin de le tester. Donc la question est - comment puis-je le tester? Avez-vous des idées?
Jusqu'à ce moment, j'ai les tests suivants:

de base sanity check - vérifie que
pour chaque nœud de la hauteur est égale à max.
taille de l'enfant noeuds + 1, l'équilibre est dans [-1, 1], à gauche de l'enfant
touche < de ce nœud de clé < droit
l'enfant est la clé, et il n'y a pas
les références circulaires (comme la gauche de l'enfant
d'un nœud est un nœud lui-même);
vérifier que afinde traversée sur un arbre AVL
(et sur un arbre de recherche binaire dans l'ensemble)
seront les valeurs de retour de l'ensemble sous-jacent dans l'ordre;
vérifier qu'un arbre AVL de hauteur est strictement inférieur à
1.44*log2(N+2)-1 (N est le nombre d'éléments) - prouvé par AVL arbres créateurs;
contrôle visuel - ne fonctionne pas, j'essaie de dessiner un arbre (rootnode dans la première ligne, ses enfants directs sur la ligne suivante, les enfants de rootnode directe des enfants sur la troisième ligne et ainsi de suite), mais qui ne fonctionne que sur de petits arbres, de grands arbres, il devient un désordre complet;
(?????) Wikipédia en russe dit qu'il est prouvé expérimentalement, que pour deux insertions d'un rééquilibrage nécessaire et pour cinq déménagements également un rééquilibrage nécessaire, mais est-ce vraiment le cas? Version anglaise de wikipédia ne dit rien à ce sujet, et pour mon AVL un rééquilibrage nécessaire pour les deux insertions ou pour quatre déménagements, ce qui n'est pas tout à fait la même.

Peut-être que ces tests sont suffisants, mais si il y a plus de tests, pas difficile à mettre en œuvre, pourquoi ne pas le faire?

5 en général n'est pas vrai, alors il doit être, dans certaines circonstances (en moyenne pour les données aléatoires?). Chercher l'équilibre de toute l'arbre, si vous double arbre en insérant les nœuds de profondeur 1er (pousser l'arbre de la racine vers les feuilles d'un niveau à la fois), l'arbre ne sera pas besoin d'un rééquilibrage.
J'ai vérifié avec mon AVL monte-carlo test, le ratio des inserts inserts rééquilibrage est de 2:1 (~10% d'erreur) et les suppressions d'supprime ce rééquilibrage est de 4:1 (~5% d'erreur) pour 5 millions de dollars des opérations aléatoires.

OriginalL'auteur Graf | 2010-10-17

2

Une propriété clé d'un arbre AVL est que chacun de ses sous-arbres d'un arbre AVL. Cela signifie que couvrant les scénarios de base qui devraient vous donner une large couverture de l'AVL arbres fonctionnalité.

En d'autres termes, ces tests effectués sur les plus petit arbre de la structure qui leur permet sont les plus importantes:
- La création d'une nouvelle arborescence.
- Insertion de la première valeur.
- L'insertion d'une plus grande valeur.
- L'insertion d'une valeur plus petite.
- L'insertion d'une valeur qui provoque LL Rotation.
- De même pour les autres rotations.
- Même pour la Suppression.
- Toutes les variantes de Trouver les valeurs.
Si votre mise en œuvre passe ces tests, il serait probablement passer sur des arbres de grande taille.
Noter que le rendement et l'utilisation de la mémoire n'est pas testé ici.

J'aime bien ton idée sur les tests de tous les possibles rotations (LL, LR, LR, RR) - 4 cas pour insert, 4 cas pour l'enlèvement.

OriginalL'auteur dahunter

Dans l'esprit de toutes ces réponses, je pensais que je voudrais fournir quelques exemples concrets pour montrer que le cas de base n'est pas assez.

Insérez - Gauche/Droite Rééquilibrer

De considérer les éléments suivants AVL équilibrée des arbres binaires, pour un insérer opération:

  20+       20+           __20+__
 /        / \          /      \
4         4    26       4         26
         /\           /\       / \
        3   9         3+  9    21    30
                     /  /\
                    2   7   11

L'insertion d'un 8 ou 15 (par exemple) dans l'un de ces arbres vont déclencher essentiellement la même Gauche/Droite de ré-équilibrage, mais les résultats sont significativement différents pour chaque arbre et de la valeur d'insertion. À savoir, la destination finale à la place de la valeur insérée et le solde final des facteurs de nœud(4) et le noeud(20) sont entièrement dépendants de la valeur relative du droit de l'enfant de moins de nœud(4) - le cas échéant. Un test exclusivement de l'un quelconque de ces cas n'ont pas nécessairement de prouver l'exactitude de toutes les autres. Note: node(4) doit d'abord être équilibré pour ces cas; un déséquilibre initial dans le nœud(4) en fin de compte n'a pas d'effet sur le nœud(20).

Cas 1a: Insérez 15

  20+      20++         20++      15
 /       /           /        / \
4     => 4-     =>   15+     => 4    20
          \         /
           15      4

Cas 2a: Insérez 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érez 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 plus complexes, ont été un problème pour moi quand j'ai travaillé sur l'optimisation du calcul des facteurs d'équilibre (qui est, le réglage de la balance des facteurs uniquement pour les nœuds plutôt que de recalculer l'ensemble de l'arborescence).

Supprimer - Double Rééquilibrage

Considérons maintenant ces arbres pour un 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

Supprimer le nœud(1) à partir de chacun de ces arbres. Notez que le Cas 1 efficacement prouve le Cas 2, mais pas à tous les Cas 3.

Cas 1

  2          2            4
 /\          \          /\
1   4    =>    4    =>  2   5
   /\        /\        \
  3   5      3   5        3

Cas 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 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

Ceci est extrêmement utile pour la construction des cas de test - vous méritez plus upvotes!

OriginalL'auteur Griffin

5

Les exemples sont légion de AVL rotations dans les livres et sur internet, mais ce que j'ai trouvé semble arbitraire et pas un seul endroit semblait exemples simples pour tous les 4 cas pour d'insertion et de suppression.

Ces sont les plus simples des cas de test que je pouvais venir pour les 4 types de rotations. Pour le rendre facile à décrire, j'ai utilisé des caractères ascii comme la clé pour un cas de test peut être exprimé comme une chaîne de caractères. Par exemple, la chaîne "abc" insérer "un", insérer "b" et insérer "c".

Le test complet cas de créer certains assez compliqué arbres j'ai donc créé deux suites de test. La première des causes les rotations, mais a vide sous-arbres pour les nœuds qui pivote, le rendant facile pour voir ce qui s'est réellement passé. La deuxième suite est non vide de sous-arbres de tester pleinement la rotation de code.

Il semble y avoir deux différents nomanclature pour tourne - ce que j'ai appris qu'un 2L de rotation, quelques livres appeler un rl de la rotation et de l'2R rotation est l'appel d'un lr de rotation. Le texte ci-dessous utilise 2R/2L.

Ces cas de test pour insérer

"abc", sur la pochette de "c" exigera un 1L de rotation
```
a                   b
 \                 /\
  b   == 1L ==>   a   c
   \
    c
```
“abc”, sur la pochette de “une” exigera un 1R rotation
```
    c               b
   /              /\
  b   == 1R ==>   a   c
 /
a 
```
"pbr" sur la pochette de "b" nécessiteront un 2L de rotation
```
a                  b
 \                /\
  c   == 2L ==>  a   c
 /
b
```
“cab” sur la pochette de “b” nécessiteront un 2R rotation
```
  c                b
 /               /\
a     == 2R ==>  a   c
 \
  b
```
Pour supprimer

“bcad”, sur la suppression de “une” exigera un 1L de rotation
```
  b                   c
 x \                 /\
a   c   == 1L ==>   b   d
     \
      d
```
“cbda”, sur la suppression du “d” exigera un 1R rotation
```
    c                  b
   /x                /\
  b   d  == 1R ==>   a   c
 /
a 
```
“bdac” sur la suppression de “une” exigera un 2L de rotation
```
  b                  c
 x \                /\
a   d   == 2L ==>  b   d
   /
  c
```
“cadb” sur la suppression de “d” exigera un 2R rotation
```
  c                  b
 /x                /\
a   d   == 2R ==>  a   c
 \
  b
```
La plus complexe des cas de test ont des sous-arbres, la plupart n'être qu'un seul nœud. Pour faire ce post, plus courte, de l'insertion et de suppression des cas de test sont combinés. L'exemple d'effacement devient l'insérer par exemple le saut de l'insertion de la supprimer de caractère. Par exemple, à l'aide de l'2R simple de supprimer les cas ci-dessus “cadb” devient l'insert cas, “cab” par le saut de l'insertion de “d”. Une conséquence de cela est la double rotation de cas ci-dessous nécessitent l'insertion d'un nœud supplémentaire pour garder l'arbre équilibré après l'insertion d'un nœud à supprimer. Cela se traduit dans l'insert cas de ne pas être minime.

“cbedfag” sur la suppression de “un” ou sauter “un” et l'insertion de “g” exigera un 1L de rotation à c
```
      c                 e
     /\               /\
    b   e  == 1R ==>  c   f
   x   /\           /\   \
  a   d   f         b   d   g
           \
            g
```
“ecfbdga” sur la suppression de “g” ou ignorant “g” et l'insertion de “une” exigera un 1R rotation à e
```
      - e -                 c
     /    \               /\
    c       f  == 1R ==>  b   e
   /\     x             /  /\
  b   d   g             a   d   f
 /
a
```
“ecjadhkgilbf” sur la suppression de “b” ou ignorant “b” et l'insertion de “f” exigera un 2L de rotation à alors j. e. L'insert cas peut éventuellement ignorer 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 ignorant “j” et l'insertion de “g” exigera un 2R rotation à c puis b. L'insert cas peut éventuellement ignorer 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 à partir de la question afin de vérifier l'arbre rééquilibré que nécessaire (c'est à dire, vérifier arbre est toujours en ordre et équilibrée). Si vous voulez être vraiment sûr, convertir le visuel des cas de test pour inclure une liste de la profondeur et de l'équilibre des valeurs de la finale de l'arbre à vérifier lors d'une afinde traversée.

OriginalL'auteur
2

Si vous voulez vraiment le marteau de votre application, vous devriez faire un peu de "boîte noire" des tests avec différents lots de l'insertion de l'ordre et de retrait de la commande tendances. Voici quelques idées qui vous viennent à l'esprit:
- Ordre aléatoire
- Ordre croissant
- Ordre décroissant
- Interleave deux ruisseaux, l'un avec l'augmentation de l', l'un avec l'ordre décroissant
  - Commencer avec des valeurs similaires et divergent
  - Début à la fin et se rencontrent au milieu
  - Début à la fin et de la croix aux extrémités opposées
- De marche aléatoire avec vers le haut, vers le bas et neutre biais
- Mélanger des insertions et des suppressions dans les combinaisons de ces tendances.
Vous ne devriez pas seulement un test de justesse, mais aussi la performance, sous réserve de ce qui précède, des modèles qui peuvent nécessiter la construction largish ensembles de données, de sorte que vous pouvez véritablement à la mesure de la performance. Tout est plus rapide avec 100 éléments, mais avec 10⁵, la différence entre O(N²) et O(N journal N) sera énorme.

Vous devez également tester pour de mauvaises entrées, par exemple, en ajoutant ou en supprimant la même valeur à deux reprises (en supposant que vous ne laissez pas de doublons).

J'aime votre idée sur la mesure de la performance.

OriginalL'auteur Marcelo Cantos
1

Pour insérer et supprimer, il y a un nombre particulier (environ cinq pour chaque, je me souviens) de l'arbre des opérations qui peuvent se produire.

Vous devez configurer un arbre immédiatement avant l'une de ces opérations telles que l'ajout d'un autre élément particulier qui va provoquer une connu une de ces opérations.

Vous ensuite inspecter l'arbre de vidage. Ça va être assez simple arbre, pas plus d'une dizaine d'éléments.

Si chaque insérer/supprimer une opération fonctionne correctement, vous aurez validé le noyau vital de comportement de votre arbre.

(Remarque, l'un des (je crois que c'était) les opérations d'insertion ne peuvent pas être contrôlés de cette façon - c'est un état intermédiaire qui existe de façon temporaire).

OriginalL'auteur

Vous devez vous connecter pour publier un commentaire.