Balancieren eines ternären Suchbaum

Question

Wie geht ein über ‚Ausgleich‘ einen ternären Suchbaumes? Die meisten tst Implementierungen tun Adresse Ausgleich nicht, aber in einer optimalen Reihenfolge empfiehlt Einfügen (die ich nicht kontrollieren kann.)

Answer 1

Der Artikel in Dr. Dobbs über Ternary Search Trees sagt: D.D. Sleator und R.E. Tarjan beschreibt theoretische Ausgleichsalgorithmen für ternäre Suchbäume in "Self-Einstellung Binary Search Trees" (Journal of the ACM, Juli 1985). Sie können Online-Versionen dieses Papiers mit Ihrer bevorzugten Suchmaschine finden.

Answer 2

Eine einfache Optimierung ist es eine rot-schwarz-Baum zu machen, die einige Worst-Case-Szenarien zu vermeiden. TSTs sind wirklich nur binäre Bäume, wo der Wert eines gegebenen Knotens eine andere TST ist. Also, das „mittlere“ Kind eines Knotens ist nicht wirklich Teil des Baumes, der auf jeder Ebene ausgeglichen werden, da es ohnehin nicht zu einem anderen Elternteil bewegen kann.

Damit wird sichergestellt, dass jede Ebene des Trie in log (R) Zeit durchlaufen wird, obwohl Sie wahrscheinlich besser machen könnte sogar unter Berücksichtigung der Größe der Subtries an jedem Knoten. Das sieht allerdings viel komplizierter sein!

Answer 3

Eine Verallgemeinerung des binären Suchbaum ist der B-Baum , die funktioniert Fanouts überall von 2 bis einschl. Das ist nicht der einzige Weg, es zu tun, aber es ist ein allgemeiner.

Etwa so, wie es funktioniert, ist, wenn ein Einsatz oder löschen würde den Baum aus dem Gleichgewicht setzt, ist es ein Element stiehlt oder einen Raum von einem benachbarten Knoten. Wenn auch das nicht genug ist, den Baum im Gleichgewicht zu halten, durch seine Höhe verändert werden, um Platz zu machen.

Answer 4

lesen Sie diesen Artikel:

„Selbst Einstellen von Ternary Search versucht, über Conditional Rotationen und Randomized Heuristik“ durch "Ghada Hany Badr * und B. John Oommen †"

es wird Ihnen zu verstehen helfen, sich selbst einstellende und ausgleichend TSTs.