Gibt es eine binäre Suchbaum-Datenstruktur, die eine schlechte Gewichtsbalance vermeiden kann?

Dies ist eine Folgefrage von " Nicht alle Rot-Schwarz-Bäume sind ausgeglichen? " Und " AVL-Bäume sind nicht gewichtsausgeglichen? ". $\def\le{\leqslant}\def\ge{\geqslant}$

Definition: Für einen verwurzelten Baum $T$ und einen Scheitelpunkt $v \in V(T)$ sei $L_T(v)$ die Anzahl der Knoten im linken Teilbaum von $v$ und $N_T(v)$ die Anzahl der Knoten im verwurzelten Teilbaum bei $v$ . Wir sagen , daß $T$ ist $\mu$ -balanced , mit $0 \le \mu \le \frac{1}{2}$ , wenn für jeden Knoten $v \in V(T)$ die Ungleichung
$μ ⩽ \frac{L_{T} (v) + 1}{N_{T} (v) + 1} ⩽ 1 - μ$ $\mu \le \frac{L_T(v) + 1}{N_T(v) + 1} \le 1 - \mu$ gilt, und wenn $\mu$ minimal ist, unterliegt diese Ungleichung.

(Diese Bäume werden in einigen Literaturstellen anscheinend auch als gewichtsausgeglichene Bäume bezeichnet.) Ein Baum, der für einige $\mu'$ -ausgeglichen ist , wird, wie wir sagen werden, μ-unausgeglichen . $\mu' < \mu$

Die oben verlinkten Beiträge zeigen im Wesentlichen, dass weder für AVL-Bäume noch für Rot-Schwarz-Bäume ein $\mu$ Ausgleich für garantiert werden kann $\mu > 0$ : Das heißt, für einen solchen $\mu$ kann eine Folge von Eingaben bereitgestellt werden eingefügt werden, damit der resultierende Baum $\mu$ unausgeglichen ist.

Frage. Gibt es eine binäre Suchbaumstruktur mit den üblichen Merkmalen der Einfügung und Suchzeit von $O(\log n)$ und einigen $m > 0$ , so dass der Baum für einige immer $\mu$ ausgeglichen ist ? $\mu > m$

data-structures search-trees Niel de Beaudrap
quelle

Ich würde sagen, dass der Grund, warum ausgeglichene Bäume selten verwendet werden: Sie erfordern zu viel Overhead, wenn sie ausgeglichen werden, mit einem kleinen Gewinn. Betrachten Sie das Beispiel in dieser Antwort : Der Baum hat eine Höhe von . Der linke Teilbaum hat Knoten und der rechte Teilbaum hat Knoten, also hat er insgesamt . Wenn wir die gleiche Anzahl von Knoten in einen perfekt ausbalancierten Baum einfügen, hat dieser immer noch eine Höhe von . Da die Höhe die Betriebskosten bestimmt, gewinnen wir nichts, wir verbringen nur viel mehr Zeit damit, das Gleichgewicht wieder herzustellen.

μ

$\mu$

2 k + 2

$2k+2$

2^{k} - 1

$2^k-1$

2^{2 k + 1} - 1

$2^{2k+1}-1$

2^{2 k + 1} + 2^{k} - 1

$2^{2k+1}+2^k-1$

2 k + 2

$2k+2$

Petr Pudlák

@ PetrPudlák: In der Tat bin ich beim Lesen von binären Suchbäumen mit begrenztem Gleichgewicht (Nievergelt + Reingold) in Aryabhatas Antwort von der Seltsamkeit der Idee beeindruckt, durch die gesamte Datenstruktur zu suchen. Ich bin mir nicht sicher, unter welchen Umständen man so etwas tun möchte, was stattdessen weder eine einfachere noch eine ausgefeiltere Datenstruktur nahelegt. Wenn es einfach ist, den Pfad zum gesuchten Element zu finden, wie bei einer typischen Implementierung von BSTs in einem geordneten Satz, ist es die Größe, aber nicht das Gewicht, das zählt. aber als kombinatoriker bin ich neugierig.

Niel de Beaudrap

Ja, ich glaube es gibt (obwohl ich mich nicht an die Details des Papiers erinnere, um es zu bestätigen).

Dies ist das Originalpapier, das sich damit befasste:

Nievergelt J. und Reingold EM, " Binäre Suchbäume mit begrenztem Gleichgewicht ", Proceedings of the Fourth Annual ACM Symposium on Theory of Computing, S. 137-142, 1972

Hier ist eine Seite über Bäume mit Gewichtsausgleich, die anscheinend mehr Informationen enthält und deren Verwendung in funktionalen Sprachen erwähnt.

Dieses Papier: Über die durchschnittliche Anzahl von Ausgleichsvorgängen in gewichtsausgeglichenen Bäumen scheint die Anzahl von Ausgleichsvorgängen in gewichtsausgeglichenen Bäumen zu untersuchen.

Ich scheine mich auch daran zu erinnern, dass ein Knuths Art of ... -Buch einen Verweis auf das obige Reingold-Papier hatte (vielleicht in den Übungen).

Aryabhata
quelle

Gibt es eine binäre Suchbaum-Datenstruktur, die eine schlechte Gewichtsbalance vermeiden kann?

Antworten: