Balancing ein Nicht-BST

Question

Bei einem kürzlichen Test in Algorithmen Kurs habe ich eine Aufgabe, um Methoden zu verwenden, um einen AVL-Baum neu zu balancieren, um einen bestimmten Binärbaum auszugleichen. Das Problem ist, was ist, wenn dieser Baum nicht BST ist? Macht es Sinn, Rotationen zu verwenden? Ich meine, du könntest sie benutzen, aber es scheint keine Möglichkeit zu geben, einen solchen Baum zu balancieren, bevor er "repariert" wird. macht es zu einem BST.

Wenn dies möglich ist, gibt es eine Situation, in der dies nützlich wäre? Ich kann keine wirkliche Logik dahinter finden, außer Verwirrung zu stiften.

Answer 1

Das hängt wirklich davon ab, was der Baum darstellt. Baumdrehungen sind eine natürliche Idee, wenn es um binäre Suchbäume geht, da sie eine Möglichkeit darstellen, den Baum neu zu gestalten, während die binäre Sucheigenschaft erhalten bleibt. Bei anderen Bäumen ist dies möglicherweise nicht möglich. Zum Beispiel ist in einer k-d tree, die etwas wie eine BST wirkt, aber in höheren Dimensionen arbeitet, Rotationen nicht möglich, da die Ebene eines Knotens im Baum bestimmt, wie Vergleiche mit diesem Knoten funktionieren. Es ist jedoch möglich, k-d-Bäume neu zu verteilen, indem ein Teilbaum entfernt und von Grund auf neu aufgebaut wird. (Diese Idee kann auch in regulären BSTs verwendet werden; für Einzelheiten siehe scapegoat tree).

In einigen anderen Baumstrukturen, wie z. B. Parse-Bäumen, macht die Idee einer Rotation überhaupt keinen Sinn, da der Baum eine Hierarchie und nicht eine Ordnung codiert. In diesen Fällen kann ein Baum fundamental unausgeglichen sein, weil er versucht, etwas darzustellen, das selbst fundamental unausgeglichen ist.

Also im Allgemeinen, nein, es gibt keine Möglichkeit, Baumrotationen auf Nicht-BSTs zu verallgemeinern, obwohl es unter bestimmten Umständen möglich ist, über mehr und weniger ausgeglichene Bäume zu sprechen.

Answer 2

Der wahre Sinn der Verwendung von BST liegt in O (Logn) suchen und ersetzen jedes Element. Wenn der Baum nicht binär ist, dann sind Suche und Ersetzung teuer, deshalb verwenden wir AVL, um als BST zu balancieren, was im schlimmsten Fall zur Linked List wird.

Die Anwendungen umfassen auch Speicherverwaltung, manchmal auch Prozessterminierung. Und viele mehr.