Löschen aller Knoten in einem Binärbaum mit O (1) Hilfsspeicherplatz?

Question

Der Standardalgorithmus alle Knoten in einem binary tree zum Löschen verwendet eine postorder traversal über die Knoten in dieser Richtung:

if (root is not null) { 
    recursively delete left subtree 
    recursively delete right subtree 
    delete root 
} 

Dieser Algorithmus verwendet O (h) Hilfsspeicherraum, wobei h die Höhe des Baumes 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?

Answer 1

Es ist tatsächlich möglich, alle Knoten in einem Binärbaum mit O (n) und O (1) Hilfsspeicherplatz zu löschen, indem ein Algorithmus basierend auf tree rotations verwendet wird.

  u 
     /\ 
     v C 
     /\ 
     A B 

Eine Rechtsdrehung dieses Baumes u und die Ergebnisse in der folgenden Baum des Knotens v über dem Knoten zieht::

einen binären Baum mit der folgenden Form gegeben

 v 
    /\ 
     A u 
     /\ 
     B C 

Man beachte, dass Eine Baumrotation kann in O (1) -Zeit und -raum erfolgen, indem einfach die Wurzel des Baums in v geändert wird, das linke Kind von u als ehemaliges rechtes Kind von v festgelegt wird und vs rechtes Kind als u festgelegt wird.

Baumrotationen sind in diesem Zusammenhang nützlich, da eine Rechtsdrehung 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 wird, wenn der Baum wie folgt geformt:

 v 
     \ 
     A 

Dann können wir alle Knoten im Baum löschen, indem Sie den Knoten v löschte, dann alle Knoten in dem Baum A. Löscht Dies führt zu einem sehr einfachen Algorithmus für alle Knoten im Baum zu löschen:

while (root is not null) { 
    if (root has a left child) { 
     perform a right rotation 
    } else { 
     delete the root, and make the root's right child the new root. 
    } 
} 

Dieser Algorithmus eindeutig verwendet nur O (1) Stauraum, weil sie höchstens eine konstante Anzahl von Zeigern zu tun, um eine Drehung oder zu ändern, um die Wurzel und die Bedürfnisse 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) läuft und nur O (1) Raum verwendet. Wenn es hilft, habe ich a C++ implementation of this algorithm, 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!

Answer 2

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 verfügbaren 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 des DSW algorithm verwenden. Grundsätzlich den Baum in ein Rückgrat und dann löschen, wie Sie eine linked list. Raum O (1) und Zeit O (n). Sie sollten in jedem Lehrbuch oder online Vorträge von DSW finden.

Grundsätzlich DSW wird verwendet, um eine BST auszugleichen. Aber für Ihren Fall, sobald Sie das Rückgrat erhalten, anstatt zu balancieren, löschen Sie wie Sie eine verknüpfte Liste.