Sind nicht alle rot-schwarzen Bäume ausgeglichen?

Intuitiv sollten "ausgeglichene Bäume" Bäume sein, bei denen die linken und rechten Unterbäume an jedem Knoten "ungefähr die gleiche" Anzahl von Knoten haben müssen.

Wenn wir davon sprechen, dass rot-schwarze Bäume * (siehe Definition am Ende) ausgeglichen sind, meinen wir natürlich, dass sie Höhe haben ausgeglichen sind, und in diesem Sinne sind sie ausgeglichen.

Angenommen, wir versuchen, die obige Intuition wie folgt zu formalisieren:

Definition: Ein binärer Baum heißt balanced, mit 0 ≤ μ ≤ $\mu$ , wenn für jeden KnotenNdie Ungleichung$0 \le \mu \leq \frac{1}{2}$$N$

$$\mu \le \frac{|N_L| + 1}{|N| + 1} \le 1 - \mu$$

gilt und für jedes gibt es einen Knoten, für den die obige Anweisung fehlschlägt. | N L | ist die Anzahl der Knoten im linken Unterbaum von N und | N | ist die Anzahl der Knoten unter dem Baum mit N als Wurzel (einschließlich der Wurzel).$\mu' \gt \mu$$|N_L|$$N$$|N|$$N$

Ich glaube, diese werden in einigen Literaturstellen zu diesem Thema als gewichtsausgeglichene Bäume bezeichnet.

Man kann zeigen, dass, wenn ein binärer Baum mit Knoten μ- ausgeglichen ist (für eine Konstante μ > 0 ), die Höhe des Baums O ist ( log n $n$$\mu$$\mu \gt 0$$\mathcal{O}(\log n)$ , wodurch die netten beibehalten werden.

Die Frage ist also:

Gibt es ein so dass jeder ausreichend große rot-schwarze Baum μ- ausgeglichen ist?$\mu \gt 0$$\mu$

Die Definition von Rot-Schwarz-Bäumen, die wir verwenden (von Einführung in Algorithmen von Cormen et al.):

Ein binärer Suchbaum, in dem jeder Knoten entweder rot oder schwarz gefärbt ist und

• Die Wurzel ist schwarz
• Alle NULL-Knoten sind schwarz
• Wenn ein Knoten rot ist, sind beide untergeordneten Knoten schwarz.
• Für jeden Knoten haben alle Pfade von diesem Knoten zu untergeordneten NULL-Knoten die gleiche Anzahl schwarzer Knoten.

Anmerkung: Wir zählen die NULL-Knoten in der Definition von balanced oben nicht. (Obwohl ich glaube, dass es keine Rolle spielt, wenn wir es tun).$\mu$

Anspruch : Rot-Schwarz - Bäume können willkürlich sein un- $\mu$ -balanced.

Beweisidee : Fülle den rechten Teilbaum mit so vielen Knoten wie möglich und den linken Teilbaum mit so wenig Knoten wie möglich für eine gegebene Anzahl von $k$ schwarzen Knoten auf jedem Wurzelblattpfad.

Beweis : Definieren Sie eine Folge $T_k$ von rot-schwarzen Bäumen, so dass $T_k$ auf jedem Pfad von der Wurzel zu einem beliebigen (virtuellen) Blatt $k$ schwarze Knoten hat . Definiere $T_k = B(L_k, R_k)$ mit

• $R_k$ der komplette Baum der Höhe$2k - 1$ mit der ersten, dritten, ... Stufe rot, die anderen schwarz und
• $L_k$ der vollständige Baum der Höhe$k-1$ mit allen Knoten, die schwarz gefärbt sind.

Es ist klar, dass alle $T_k$ rot-schwarze Bäume sind.

Zum Beispiel sind dies $T_1$ , $T_2$ bzw. $T_3$ :

^{[ Quelle ]}

^{[ Quelle ]}

^{[ Quelle ]}

Lassen Sie uns nun den visuellen Eindruck überprüfen, dass die rechte Seite im Vergleich zur linken Seite sehr groß ist. Ich werde keine virtuellen Blätter zählen. Sie haben keinen Einfluss auf das Ergebnis.

$T_k$$k-1$$2^k - 1$$2k - 1$$2^{2k}-1$$\mu$

$\qquad \displaystyle \frac{2^k}{2^k + 2^{2k}} = \frac{1}{1 + 2^k} \underset{k\to\infty}{\to} 0$

$\mu > 0$

Nein . Betrachten wir ein Rot-Schwarz-Baum mit der folgenden speziellen Struktur.

• $d$
• $2d$

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