Der Standardalgorithmus zum Löschen aller Knoten in einem Binärbaum verwendet ein postorder traversal über die Knoten entlang dieser Linien:
%Vor%Dieser Algorithmus verwendet O (h) Hilfsspeicherplatz, wobei h die Höhe des Baums ist, aufgrund des Speicherplatzes, der erforderlich ist, um die Stapelrahmen während der rekursiven Aufrufe zu speichern. Es läuft jedoch in der Zeit O (n), weil jeder Knoten genau einmal besucht wird.
Gibt es einen Algorithmus zum Löschen aller Knoten in einem Binärbaum, der nur O (1) zusätzlichen Speicherplatz verwendet, ohne die Laufzeit zu beeinträchtigen?
Es ist tatsächlich möglich, alle Knoten in einem binären Baum mit O (n) und O (1) Hilfsspeicherplatz zu löschen, indem ein Algorithmus verwendet wird, der auf Baumrotationen .
Gegeben sei ein Binärbaum mit folgender Form:
%Vor%Eine Rechtsdrehung dieses Baumes zieht den Knoten v über den Knoten u und ergibt den folgenden Baum:
%Vor%Beachten Sie, dass eine Baumrotation in O (1) Zeit und Raum erfolgen kann, indem Sie einfach die Wurzel des Baums in v ändern, indem Sie das linke Kind von v als ehemaliges rechtes Kind von v setzen und vs rechtes Kind als u setzen .
Baumdrehungen sind in diesem Kontext nützlich, da eine rechte Drehung die Höhe des linken Teilbaums des Baums immer um eins verringert. Dies ist wegen einer cleveren Beobachtung nützlich: Es ist extrem einfach, die Wurzel des Baums zu löschen, wenn es kein linkes Subchild mehr hat. Insbesondere, wenn der Baum wie folgt geformt ist:
%Vor%Dann können wir alle Knoten in dem Baum löschen, indem wir den Knoten v löschen und dann alle Knoten in seinem Unterbaum A löschen. Dies führt zu einem sehr einfachen Algorithmus zum Löschen aller Knoten in dem Baum:
%Vor%Dieser Algorithmus verwendet eindeutig nur O (1) Speicherplatz, da er höchstens eine konstante Anzahl von Zeigern benötigt, um eine Rotation durchzuführen oder den Stamm zu ändern, und der Platz für diese Zeiger kann über alle Iterationen der Schleife wiederverwendet werden.
Darüber hinaus kann gezeigt werden, dass dieser Algorithmus auch in O (n) Zeit läuft. Intuitiv ist es möglich, dies zu sehen, indem man sich anschaut, wie oft eine gegebene Kante gedreht werden kann. Beachten Sie zunächst, dass bei jeder Ausführung einer Rechtsdrehung eine Kante, die von einem Knoten zu ihrem linken Kind führt, in eine rechte Kante konvertiert wird, die vom ehemaligen Kind zurück zu seinem Elternteil verläuft. Als nächstes beachten Sie, dass wir, sobald wir eine Rotation durchführen, die den Knoten u zum rechten Kind des Knotens v bewegt, nie wieder den Knoten u berühren werden, bis wir Knoten v und den gesamten linken Teilbaum von v gelöscht haben. Als Ergebnis können wir die Anzahl der gesamten Rotationen begrenzen, die jemals ausgeführt werden, indem wir beachten, dass jede Kante in dem Baum höchstens einmal mit ihrem Elternteil rotiert wird. Folglich gibt es höchstens O (n) -Drehungen, von denen jede O (1) -Zeit und genau n Löschungen benötigt. Dies bedeutet, dass der Algorithmus in der Zeit O (n) ausgeführt wird und nur O (1) -Raum verwendet.
Falls es hilft, habe ich eine C ++ - Implementierung dieses Algorithmus zusammen mit einer viel eingehenderen Analyse des Verhaltens des Algorithmus. Es enthält auch formelle Beweise für die Richtigkeit aller Schritte des Algorithmus.
Hoffe, das hilft!
Lassen Sie mich mit einem ernsten Scherz beginnen: Wenn Sie die Wurzel einer BST auf Null setzen, löschen Sie effektiv alle Knoten in der Baumstruktur (der Garbage Collector stellt den Speicherplatz zur Verfügung). Während der Wortlaut Java-spezifisch ist, gilt die Idee für andere Programmiersprachen. Ich erwähne das nur für den Fall, dass Sie bei einem Vorstellungsgespräch oder einer Prüfung waren.
Ansonsten müssen Sie nur eine modifizierte Version von DSW algorithm verwenden. Im Grunde verwandeln Sie den Baum in ein Backbone und löschen Sie dann wie ein linked list . Raum O (1) und Zeit O (n). Sie sollten in jedem Lehrbuch oder online über DSW sprechen.
Grundsätzlich wird DSW verwendet, um eine BST auszugleichen. Aber für Ihren Fall, sobald Sie das Rückgrat erhalten, anstatt zu balancieren, löschen Sie wie eine verknüpfte Liste.
Algorithmus 1 , O (n) Zeit und O (1) Space: Löschen Sie den Knoten sofort, es sei denn, er hat beide untergeordneten Elemente. Andernfalls gehen Sie zum linken Knoten, um die Links zu reversieren, um sicherzustellen, dass alle Knoten erreichbar sind - der Knoten ganz links wird zum neuen Root:
%Vor%Algorithmus 2 , O (n) Zeit und O (1) space: Durchqueren Sie die Knotentiefe zuerst und ersetzen Sie untergeordnete Links durch Links zu Eltern. Jeder Knoten wird auf dem Weg nach oben gelöscht:
%Vor%Tags und Links algorithm data-structures big-o binary-tree space-complexity