Ich habe eine theoretische Frage zu Balanced BST .
Ich möchte Perfect Balanced Tree mit 2^k - 1 nodes aus einem normalen unbalanced BST erstellen. Die einfachste Lösung, die ich mir vorstellen kann, ist eine sortierte Array/Linked list zu verwenden und das Array rekursiv in Sub-Arrays zu unterteilen und Perfect Balanced BST daraus zu erstellen.
Bei extrem großen Tree-Größen muss ich jedoch Array/List in derselben Größe erstellen, damit diese Methode viel Speicher belegt.
Eine weitere Option ist die Verwendung von AVL Rotationsfunktionen, Einfügen von Element für Element und Balancieren des Baums mit Rotationen in Abhängigkeit vom Baumbalancenfaktor - drei Höhe der linken und rechten Teilbäume.
Meine Fragen sind, habe ich Recht mit meinen Annahmen? Gibt es eine andere Möglichkeit, ein perfektes BST aus unbalanciertem% co_de% zu erstellen?
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 normalerweise 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-Baum, 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 vielleicht ein anderes Problem. - In Ihrem Fall ist es wahrscheinlich der beste Weg, den AVL-Weg zu rotieren.
AVL und ähnliche Bäume sind nicht perfekt ausgeglichen, also bin ich mir nicht sicher, wie sie in diesem Zusammenhang nützlich sind.
Sie können eine doppelt verknüpfte Liste von Baumknoten erstellen, indem Sie die Zeiger left und right anstelle von forward und backward verwenden. Sortieren Sie diese Liste und erstellen Sie den Baum rekursiv von unten nach oben, wobei Sie die Liste von links nach rechts auffrischen.
Es ist trivial, einen Baum der Größe 1 zu bauen: Einfach den ganz linken Knoten von der Liste wegbeißen.
Wenn Sie jetzt einen Baum der Größe N erstellen können, können Sie auch einen Baum der Größe 2N+1 erstellen: Erstellen Sie einen Baum der Größe N , beißen Sie dann einen einzelnen Knoten ab und erstellen Sie einen weiteren Baum der Größe %Code%. 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 N zu ändern.
Update: Da Sie von einem Suchbaum starten, können Sie eine sortierte Liste direkt daraus in 2^k-1 time und O(N) space (vielleicht sogar in O(log N) space mit ein wenig Einfallsreichtum) erstellen und das Baum von unten nach oben auch in O(1) time und O(N) (oder O(log N) ) Leerzeichen.
Wenn Sie Speicherbeschränkungen haben, können Sie die Split- und Join-Operationen verwenden, die in einer AVL-Struktur in O (log n) -Zeit durchgeführt werden können, und ich glaube, dass der konstante Platz.
Wenn Sie auch die Auftragsstatistik pflegen konnten, dann können Sie den Median teilen, LHS und RHS perfekt machen und dann beitreten.
Der Pseudocode (für eine rekursive Version) ist
%Vor%Dies kann in O (n) Zeit und O (log n) Raum implementiert werden, glaube ich.
Tags und Links algorithm c binary-search-tree linked-list avl-tree