Wie um zu überprüfen, ob meine AVL-Baum Implementierung korrekt ist?
Jungs.
Ich denke, ich habe ein AVL-Baum-Implementierung, aber als AVL-Baum ist eine ziemlich komplexe Struktur, die ich brauche, um es zu testen. Die Frage ist also - wie kann ich es testen? Haben Sie irgendwelche Ideen?
Bis zu diesem moment habe ich die folgenden tests:
-
basic sanity-check - Prüfungen,
für jeden Knoten die Höhe entspricht max.
Höhe der Kind-Knoten + 1, das Gleichgewicht ist in [-1, 1], linken Kindes
key < dieser Knoten ist die Taste < Recht
Kind-Schlüssel, und es gibt keine
zirkuläre Referenzen (wie Links Kind
ein Knoten ist ein Knoten auf sich selbst); -
überprüfen Sie, dass die inorder-Traversierung auf einem AVL-Baum
(und auf einen binären Suchbaum in das ganze)
wird die Rückgabe von Werten aus den zugrundeliegenden Satz in Ordnung; -
überprüfen Sie, dass ein AVL-Baum der Höhe ist weniger streng als
1.44*log2(N+2)-1 (gibt N die Anzahl der Elemente) - bewiesen durch die AVL-Baum-Schöpfer; -
visuelle Kontrolle - funktioniert nicht gut, ich versuche, den Baum zu zeichnen (Stammknotens in der ersten Zeile, seine direkten Kinder auf die nächste Zeile, Kinder des Stammknotens direkten Kinder in der Dritten Zeile und so weiter), aber das funktioniert nur auf kleine Bäume, große Bäume, es wird ein komplettes Chaos;
-
(?????) Russische wikipedia sagt, dass es bewiesen experimentell, dass für zwei Einfügungen, eine Neugewichtung erforderlich und für fünf Umzüge auch ein rebalancing nötig ist, aber ist es wirklich so? Die englische wikipedia sagt nichts über es, und für meine AVL einer rebalancing-Bedarf für zwei Insertionen oder vier Umzüge, das ist nicht ganz das gleiche.
Vielleicht diese tests sind genug, aber wenn es noch mehr tests, nicht schwer zu implementieren, weshalb es nicht zu tun?
- 5 im Allgemeinen nicht wahr ist, so muss es unter einem bestimmten Umstand (im Durchschnitt für zufällige Daten?). Wählen Sie eine ausgewogene Struktur, wenn Sie duplizieren, dass der Baum durch das einfügen der Knoten der Tiefe 1. (wachsen des Baumes von der Wurzel zu den Blättern jeweils eine Ebene), der Baum wird nicht verlangen, ein neues Gleichgewicht.
- Ich überprüft mit meinem AVL-monte-carlo-test, der das Verhältnis von Einfügungen Einfügungen, die ins Gleichgewicht bringen 2:1 (~10% Fehler) und löscht, löscht, der auszugleichen ist 4:1 (innerhalb von ~5% Fehler) für 5 Millionen zufällige Vorgänge.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Eine wichtige Eigenschaft von AVL-Baum ist, dass jeder seiner sub-Bäumen ist auch ein AVL-Baum. Das bedeutet, dass für die grundlegende Szenarien sollten Sie eine Breite Abdeckung der AVL-Baum Funktionalität.
In anderen Worten, diese tests auf die kleinste Struktur, die es Ihnen erlaubt sind die wichtigsten:
Wenn Ihre Implementierung die tests besteht, wäre es wahrscheinlich übergeben, auf die größeren Bäume.
Beachten Sie, dass die Leistung und die Speichernutzung ist nicht getestet.
Im Geiste all diese Antworten, ich dachte, ich würde bieten ein paar konkreten Beispielen zu zeigen, dass der grundlegende Fall ist, ist nicht genug.
Einfügen - Links/Rechts Auszugleichen
Betrachten Sie die folgenden AVL-ausgeglichenen binären Bäumen für einen einfügen Betrieb:
Einfügen von entweder 8 oder 15 (zum Beispiel) in jeden dieser Bäume wird der Auslöser im wesentlichen die gleichen Links - /Rechts-re-balancing, aber die end-Ergebnisse sind signifikant unterschiedlich für jeden Baum und legen Sie Wert. Zu Witz, der Letzte Landeplatz der eingefügte Wert und der Restbetrag Faktoren von Knoten(4) und Knoten(20) sind völlig abhängig von den relativen Wert des rechten Kindes von unter-Knoten(4) - falls vorhanden. Eine Prüfung, die ausschließlich aus einer dieser Fälle nicht unbedingt beweisen die Richtigkeit von allen anderen. Hinweis: Knoten(4) muss zunächst ausgeglichen werden, für diese Fälle; eine anfängliche Ungleichgewicht im Knoten(4) letztlich hat das keine Auswirkungen auf Knoten(20).
Fall 1a: Legen Sie 15
Fall 2a: Legen Sie 15
Fall 3a: Einsatz 15
Fall 1b: Legen Sie 8
Fall 2b: Legen Sie 8
Fall 3b: Legen Sie 8
Komplexere Fälle waren ein problem für mich, wenn ich arbeiten war auf der Optimierung der Berechnung der balance-Faktoren (das heißt, die Anpassung der balance-Faktoren nur für die betroffenen Knoten anstatt der Neuberechnung der ganze Baum).
Löschen - Doppel-Rebalancing
Betrachten wir nun diese Bäume für eine löschen Betrieb:
Knoten löschen(1) von jedem dieser Bäume. Beachten Sie, dass Fall 1 wirksam erweist, Fall 2, aber nicht auf alle Fall 3.
Fall 1
Fall 2
Fall 3
Die viele Beispiele von AVL-Rotationen in Büchern und im internet, aber was ich fand, schien willkürlich und ohne einen Ort, schien zu zählen einfache Beispiele für alle 4 Fälle für einfügen und löschen.
Diese sind der einfachste test case, die ich gefunden habe für die 4 Arten von Rotationen. Um es einfach zu beschreiben, ich verwendet habe, ascii-Zeichen als Schlüssel, so dass ein Testfall kann ausgedrückt werden als ein string. Zum Beispiel der string "abc" wäre " einfügen "ein", " einfügen "b" und dann " einfügen "c".
Den vollständigen test cases, erstellen einige ziemlich kompliziert Bäume, so habe ich zwei test-Suiten. Die erste bewirkt, dass die Rotationen, die aber leer sind sub-Strukturen für die Knoten gedreht wird macht es einfach, um zu sehen, was tatsächlich passiert ist. Die zweite suite hat nicht-leeren Teilbäume vollständig testen Sie die rotation-code.
Scheint es zwei verschiedene nomanclature für sich dreht - was ich gelernt habe, als ein 2L-Drehung, einige Bücher nennen, eine rl-rotation und die 2R-rotation ist rufen Sie einen lr-rotation. Der text unten verwendet 2R/2L.
Dies sind die einfachen Testfälle für insert
"abc" für das einfügen des "c" benötigen Sie eine 1-LITER-rotation
"cba", auf das einfügen von "a" erfordert eine 1R-rotation
"acb" auf das einfügen von "b" benötigen Sie einen 2L-Drehung
"cab" auf das einfügen von "b" benötigen Sie eine 2R-rotation
Für löschen
"bcad", auf das löschen von "a" benötigen Sie eine 1-LITER-rotation
"cbda", auf die Streichung von "d" benötigen Sie eine 1R-rotation
"bdac" auf das löschen von "a" erfordert eine 2L-Drehung
"cadb" auf das löschen von "d" benötigen Sie eine 2R-rotation
Komplexere Testfälle müssen sub-Bäume, die meisten einfach nur einen einzelnen Knoten. Um diesen post kürzer, die einfügen und löschen von Testfällen kombiniert werden. Das löschen Beispiel wird das einfügen Beispiel durch das überspringen der Einfügung der Zeichen löschen. Zum Beispiel, indem die 2R einfach löschen oben genannten Fall "cadb" wird der insert-Fall "cab" durch das überspringen der Beilage "d". Eine Folge ist die doppelte drehen nachstehend aufgeführten Fällen bedürfen einfügen eines zusätzlichen Knotens zu halten, der Baum ausgeglichen nach dem einfügen der Knoten gelöscht werden. Dies führt in der insert-Fall nicht minimal.
"cbedfag" auf das löschen von "a" oder das auslassen von "a" und die Beilage "g" benötigen Sie eine 1 L-rotation an c
"ecfbdga" auf das löschen von "g" oder das auslassen von "g" und das einfügen von "a" erfordert eine 1R Drehung in e
"ecjadhkgilbf" auf das löschen von "b" oder das auslassen von "b" und das einfügen des "f" erfordert eine 2L-Drehung, bei j dann e. Die insert-Fall kann Optional überspringen einfügen von "d".
"hckbeiladfjg" auf das löschen von "j" oder das auslassen von "j" und die Beilage "g" erfordert eine 2R-rotation bei c, dann b. Die insert-Fall kann Optional überspringen einfügen von "l"
Verwenden Sie die Methoden 1 und 2 aus, die Frage zu prüfen, den Baum neu ausbalanciert, wie erforderlich (dh, stellen Sie sicher Baum ist noch in Ordnung und symmetrisch). Wenn Sie wollte wirklich sicher sein, konvertieren Sie den visual test-Fälle enthalten eine Liste von Tiefe und balance-Werte, der Letzte Baum, um zu überprüfen, während ein inorder traversal.
Wenn Sie wirklich wollen, um hammer zu Ihrer Implementierung sollten Sie einige black-box-tests mit vielen verschiedenen Einsatz -, um-und Abbau-um Muster. Hier sind einige Ideen in den Sinn kommen:
Sollten Sie testen nicht nur die Richtigkeit, sondern auch die Leistung, vorbehaltlich der oben genannten Muster, die erfordern, Aufbau große Datenmengen, so dass Sie sinnvoll Messen Sie die Leistung. Alles ist schnell mit 100 Elementen, aber mit 105 - Elemente, die den Unterschied zwischen O(N2) und O(N log N) wird enorm sein.
Sollten Sie auch testen, für schlecht Eingänge, z.B. durch hinzufügen oder entfernen der gleiche Wert zweimal (vorausgesetzt, Sie nicht zulassen, dass Duplikate).
Für insert und löschen, es gibt eine bestimmte Anzahl (etwa fünf für jeden, ich erinnere mich) der Baum von Operationen, die auftreten können.
Müssen Sie auf einen Baum unmittelbar vor diesen Operationen, so dass das hinzufügen eines weiteren Elements wird die Ursache bekannt ist, dass man diese Vorgänge auftreten.
Du dann untersuchen Sie den Baum - werfen Sie es aus. Es werden eine ziemlich einfache Struktur, nicht mehr als etwa zehn Elemente.
Wenn jeder insert - /delete-Vorgang korrekt funktioniert, müssen Sie validiert den entscheidenden Kern Verhalten von Ihrem Baum.
(Beachten Sie, eine der (ich glaube es war) insert-Operationen können nicht eingecheckt werden auf diese Weise - es ist ein Zwischenzustand existiert, vorübergehend).