Jungs. Ich denke, ich habe eine AVL-Tree-Implementierung erstellt, aber da AVL Tree eine ziemlich komplexe Struktur ist, muss ich es testen. Die Frage ist also - wie kann ich es testen? Hast du irgendwelche Ideen? Bis zu diesem Zeitpunkt habe ich folgende Tests:
grundlegende Vernunftprüfung - prüft das für jede Knotenhöhe gleich max. Höhe der Kindknoten + 1, Balance ist in [-1, 1], linkes Kind Schlüssel & lt; der Schlüssel dieses Knotens & lt; Recht Kindes Schlüssel, und es gibt keine Zirkelverweise (wie linkes Kind eines Knotens ist ein Knoten selbst);
Überprüfen Sie, ob in einem AVL-Baum eine Inorder-Traversierung stattfindet (und auf einem binären Suchbaum im Ganzen) gibt Werte aus der zugrunde liegenden Menge in der Reihenfolge zurück;
Überprüfen Sie, ob die Höhe eines AVL-Baums streng kleiner ist als 1.44 * log2 (N + 2) -1 (dort ist N die Anzahl der Elemente) - von AVL-Baum-Erstellern bewiesen;
visual check - funktioniert nicht so gut, ich versuche einen Baum zu zeichnen (rootnode in der ersten Zeile, seine direkten Kinder in der nächsten Zeile, childen von rootnode's direkten childen in der dritten Zeile usw.) , aber das funktioniert nur auf kleinen Bäumen, bei großen Bäumen wird es zu einem völligen Durcheinander;
(?????) Russische Wikipedia sagt, dass es experimentell bewiesen ist, dass für zwei Insertionen ein Rebalancing benötigt wird und für fünf Umzüge auch ein Rebalancing benötigt wird, aber ist es wirklich so? Englisch wikipedia sagt nichts darüber, und für meine AVL ein Rebalancing benötigt für zwei Insertionen oder für vier Umzüge, die nicht ganz gleich ist.
Vielleicht sind diese Tests genug, aber wenn es noch weitere Tests gibt, die nicht schwer zu implementieren sind, warum nicht?
Eine Schlüsseleigenschaft eines AVL-Baums ist, dass jeder seiner Unterbäume ebenfalls ein AVL-Baum ist. Das bedeutet, dass Sie bei der Abdeckung der Basisszenarien die AVL-Tree-Funktionalität umfassend abdecken sollten.
Mit anderen Worten, diese Tests, die an der kleinsten Baumstruktur durchgeführt werden, sind die wichtigsten:
Wenn Ihre Implementierung diese Tests besteht, würde sie sie wahrscheinlich an größeren Bäumen weitergeben. Beachten Sie, dass Leistung und Speichernutzung hier nicht getestet werden.
Betrachten Sie die folgenden AVL-ausgeglichenen binären Bäume für eine einfügen -Operation:
%Vor%Das Einfügen von entweder 8 oder 15 (zum Beispiel) in einen dieser Bäume löst im Wesentlichen den gleichen Links / Rechts-Ausgleich aus, aber die Endergebnisse sind für jeden Baum und den Einfügewert signifikant unterschiedlich. Der finale Landeplatz des eingefügten Wertes und der Endabgleichsfaktoren von Knoten (4) und Knoten (20) hängen nämlich vollständig von dem relativen Wert des rechten untergeordneten Knotens unter Knoten (4) ab - falls vorhanden. Ein Test, der nur in einem dieser Fälle durchgeführt wird, beweist nicht unbedingt die Richtigkeit anderer. Hinweis: Knoten (4) muss für diese Fälle zunächst ausgeglichen sein; ein anfängliches Ungleichgewicht in Knoten (4) hat letztlich keine Auswirkung auf Knoten (20).
Fall 1a: Fügen Sie 15
ein %Vor%Fall 2a: Fügen Sie 15
ein %Vor%Fall 3a: Fügen Sie 15
ein %Vor%Fall 1b: Einfügen 8
%Vor%Fall 2b: Fügen Sie 8
ein %Vor%Fall 3b: Einfügen 8
%Vor%Die komplexeren Fälle waren ein Problem für mich, als ich daran arbeitete, die Berechnung der Balance-Faktoren zu optimieren (das heißt, die Balance-Faktoren nur für betroffene Knoten anzupassen, anstatt den gesamten Baum neu zu berechnen).
Betrachten Sie nun diese Bäume für eine Operation delete :
%Vor%Lösche Knoten (1) von jedem dieser Bäume. Beachten Sie, dass Fall 1 tatsächlich Fall 2, nicht aber Fall 3, beweist.
Fall 1
%Vor%Fall 2
%Vor%Fall 3
%Vor%Es gibt viele Beispiele von AVL-Rotationen in Büchern und im Internet, aber was ich gefunden habe, schien willkürlich und kein Ort schien einfache Beispiele für alle 4 Fälle für Einfügen und Löschen zu enthalten.
Dies sind die einfachsten Testfälle, die ich für die 4 Arten von Rotationen erstellen könnte. Um es einfach zu beschreiben, habe ich ASCII-Zeichen als Schlüssel verwendet, so dass ein Testfall als String ausgedrückt werden kann. Zum Beispiel wäre die Zeichenfolge "abc" einfügen "a", einfügen "b" und fügen Sie dann "c" ein.
Die vollständigen Testfälle erzeugen einige ziemlich komplizierte Bäume, also habe ich zwei Testsuiten erstellt. Die erste verursacht die Rotationen, hat aber leere Unterbäume für die Knoten, die gedreht werden, was es einfach macht zu sehen, was tatsächlich passiert ist. Die zweite Suite enthält nicht leere Unterbäume, um den Rotationscode vollständig zu testen.
Es scheint zwei verschiedene Nomanklaturen für Rotationen zu geben - was ich als 2L Rotation gelernt habe, einige Bücher nennen eine Rotation von r1 und die Rotation von 2R ist eine lr Rotation. Der folgende Text verwendet 2R / 2L.
Dies sind die einfachen Testfälle für das Einfügen
"abc", auf der Einfügung von "c" erfordert eine 1L-Drehung
%Vor%"cba", auf der Einfügung von "a" erfordert eine 1R-Rotation
%Vor%"acb" auf der Einfügung von "b" erfordert eine 2L-Drehung
%Vor%"cab" auf dem Einsatz von "b" erfordert eine 2R-Drehung
%Vor%Zum Löschen
"bcad", beim Löschen von "a" wird eine 1L-Drehung benötigt
%Vor%"cbda", beim Löschen von "d" wird eine 1R-Drehung benötigt
%Vor%"bdac" beim Löschen von "a" erfordert eine 2L-Drehung
%Vor%"cadb" beim Löschen von "d" erfordert eine 2R-Drehung
%Vor%Die komplexeren Testfälle haben Teilbäume, meist nur ein einziger Knoten. Um diesen Beitrag zu verkürzen, werden die Testfälle Einfügen und Löschen kombiniert. Das Löschbeispiel wird zum Einfügebeispiel, indem die Einfügung des Löschzeichens übersprungen wird. Zum Beispiel wird die Verwendung des einfachen 2R-Löschvorgangs über "cadb" zum Einsatzfall "cab", indem die Einfügung von "d" übersprungen wird. Eine Konsequenz daraus ist, dass die Fälle mit doppeltem Drehen einen zusätzlichen Knoten einfügen müssen, um den Baum nach dem Einfügen des zu löschenden Knotens im Gleichgewicht zu halten. Dies führt dazu, dass der Einfügefall nicht minimal ist.
"cbedfag" beim Löschen von "a" oder das Überspringen von "a" und das Einfügen von "g" erfordert eine 1L-Drehung bei c
%Vor%"ecfbdga" beim Löschen von "g" oder Überspringen von "g" und das Einfügen von "a" erfordert eine 1R-Drehung bei e
%Vor%"ecjadhkgilbf" beim Löschen von "b" oder beim Überspringen von "b" und der Einfügung von "f" erfordert eine 2L-Drehung bei j, dann e. Der Einschub kann optional das Einfügen von "d" überspringen.
%Vor%"hckbeilafjg" beim Löschen von "j" oder Überspringen von "j" und das Einfügen von "g" erfordert eine 2R-Drehung bei c, dann b. Der Einfügefall kann optional das Einfügen von "l"
überspringen %Vor%Verwenden Sie die Methoden 1 und 2 aus der Frage, um zu überprüfen, ob der Baum wie gewünscht neu ausbalanciert wurde (dh, der Baum ist immer noch in der richtigen Reihenfolge und ausgeglichen). Wenn Sie wirklich sicher sein möchten, konvertieren Sie die visuellen Testfälle so, dass sie eine Liste der Tiefen- und Balancewerte des letzten Baums enthalten, die während eines Inorder-Traversals überprüft werden.
Wenn Sie Ihre Implementierung wirklich hämmern wollen, sollten Sie einige Black-Box-Tests mit vielen verschiedenen Einfügungs- und Entfernungsreihenfolgen durchführen. Hier einige Ideen, die Ihnen einfallen:
Sie sollten nicht nur die Korrektheit testen, sondern auch die Leistung, abhängig von den obigen Mustern, die den Aufbau größerer Datenmengen erfordern, damit Sie die Leistung sinnvoll messen können. Alles ist schnell mit 100 Elementen, aber mit 10 5 Elementen, der Unterschied zwischen O (N 2 ) und O ( N
Sie sollten auch auf schlechte Eingaben prüfen, z. B. zweimal den gleichen Wert hinzufügen oder entfernen (vorausgesetzt, dass Sie keine Duplikate zulassen).
Für Einfügen und Löschen gibt es eine bestimmte Anzahl von Baumoperationen, die auftreten können (ungefähr fünf für jeden, ich erinnere mich).
Sie müssen einen Baum unmittelbar vor einer dieser Operationen so einrichten, dass das Hinzufügen eines anderen bestimmten Elements einen bekannten dieser Vorgänge verursacht.
Sie prüfen dann den Baum - lassen Sie ihn raus. Es wird ein ziemlich einfacher Baum sein, nicht mehr als etwa zehn Elemente.
Wenn jede Einfüge- / Löschoperation korrekt ausgeführt wird, haben Sie das wichtige Kernverhalten Ihrer Struktur bestätigt.
(Beachten Sie, dass eine der (ich glaube es war) Einfügeoperationen auf diese Weise nicht überprüft werden kann - es ist ein Zwischenzustand, der vorübergehend existiert.)
Tags und Links algorithm testing data-structures avl-tree