Perfect Balanced Binary Search Tree

Question

Ich habe eine theoretische Frage über Balanced BST.

Ich möchte Perfect Balanced Tree erstellen, die 2^k - 1 Knoten hat, von einem normalen unbalanced BST. Die einfachste Lösung, die ich mir vorstellen kann, besteht darin, eine sortierte Array/Linked list zu verwenden und das Array rekursiv in Sub-Arrays zu unterteilen und daraus Perfect Balanced BST aufzubauen.

Allerdings muss ich in einem Fall von extrem großen Baumgrößen ein Array/List in der gleichen Größe erstellen, so dass diese Methode eine große Menge an Speicher verbrauchen wird.

Eine weitere Option ist die Verwendung von AVL Rotationsfunktionen, Einfügen Element für Element und Balancieren des Baumes mit Rotationen, abhängig vom Tree Balance Factor - drei Höhe der linken und rechten Teilbäume.

Meine Fragen sind, habe ich Recht mit meinen Annahmen? Gibt es eine andere Möglichkeit, eine perfekte BST aus dem unsymmetrischen BST zu erstellen?

Answer 1

Ich habe noch keine sehr gute Situation gefunden, um einen perfekt ausbalancierten Suchbaum zu benötigen. Wenn es Ihr Fall wirklich braucht, würde ich gerne davon erfahren. Normalerweise ist es besser und schneller, einen fast ausgeglichenen Baum zu haben.

Wenn Sie einen großen Suchbaum haben, ist das Wegwerfen aller vorhandenen Strukturen in der Regel keine gute Idee. Die Verwendung von Rotationsfunktionen ist eine gute Möglichkeit, einen ausgewogeneren Baum zu erhalten, während der größte Teil der vorhandenen Struktur erhalten bleibt. Normalerweise verwenden Sie jedoch eine geeignete Datenstruktur, um sicherzustellen, dass Sie niemals einen vollständig unausgeglichenen Baum haben. So genannte selbstausgleichende Bäume.

Es gibt zum Beispiel einen AVL-Baum, einen Rot-Schwarz-Baum oder einen Splay-Tree, die leicht verschiedene Varianten der Rotation verwenden, um den Baum im Gleichgewicht zu halten.

Wenn Sie wirklich einen völlig unausgeglichenen Baum haben, haben Sie möglicherweise ein anderes Problem. - In Ihrem Fall ist es wahrscheinlich der beste Weg, den AVL-Weg zu rotieren.

Answer 2

AVL und ähnliche Bäume sind nicht perfekt ausgeglichen, so dass ich nicht sicher bin, wie sie in diesem Zusammenhang nützlich sind.

Sie bauen können eine doppelt verknüpfte Liste aus Baumknoten, mit left und right Zeiger anstelle von forward und backward Zeiger. Sortieren Sie diese Liste und erstellen Sie den Baum rekursiv von unten nach oben, wobei Sie die Liste von links nach rechts auffrischen.

Einen Baum der Größe 1 zu bauen ist trivial: Den linken Knoten einfach von der Liste wegbeißen.

Nun, wenn Sie einen Baum von Größe N bauen können, können Sie auch einen Baum von Größe 2N+1 bauen: bauen, einen Baum von Größe N, dann einen einzelnen Knoten abbeißen, dann einem anderen Baum von N Größe bauen. Der einzige Knoten wird die Wurzel Ihres größeren Baumes sein, und die zwei kleineren Bäume werden seine linken und rechten Teilbäume sein. Da die Liste sortiert ist, ist der Baum automatisch ein gültiger Suchbaum.

Dies ist leicht für andere Größen als 2^k-1 zu ändern.

Update: da Sie von einem Suchbaum beginnen, können Sie eine sortierte Liste direkt von ihm in O(N) Zeit und O(log N) Raum (vielleicht sogar in O(1) Raum mit einem wenig Einfallsreichtum), bauen und den Baum von unten nach oben auch bauen in O(N) Zeit und O(log N) (oder O(1)) Platz.

Answer 3

Wenn Sie Speicher beschränkt sind, dann können Sie die Split-und Join-Operationen, die in einem AVL-Baum in O (log n) Zeit durchgeführt werden können, und ich glaube, konstanten Raum.

Wenn Sie auch die Auftragsstatistik pflegen konnten, dann können Sie auf Median teilen, die LHS und RHS perfekt machen und dann beitreten.

Der Pseudo-Code (für eine rekursive Version) wird

sein Dieses in O umgesetzt werden können (n) Zeit und O-Raum (n log), glaube ich.