Nicht alle rotschwarzen Bäume sind ausgeglichen?

Question

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

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

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

Definition: Ein binärer Baum heißt $ mu $ -Alanced, mit $ 0 le mu leq frac {1} {2} $, wenn für jeden Knoten $ n $ die Ungleichheit, die Ungleichheit

$$ mu le frac {| n_l | + 1} {| n | + 1} le 1 - mu $$

Hält und für jeden $ mu ' gt mu $ 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 root (einschließlich der Wurzel).

Ich glaube, diese werden genannt Gewichtsausgleich Bäume in einigen Literatur zu diesem Thema.

Man kann zeigen, dass, wenn ein binärer Baum mit $ n $ Knoten $ mu $ -Galanciert ist (für eine konstante $ mu gt 0 $), die Höhe des Baumes $ mathcal {o} ( log n ) $, so die netten Sucheigenschaften beibehalten.

Die Frage ist also:

Gibt es einige $ mu gt 0 $, so dass jeder große rot-schwarze Baum $ mu $ -Galanced ist?

---

Die Definition von rotschwarzen Bäumen, die wir verwenden (aus Einführung zu Algorithmen von Cormen et al.):

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

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

HINWEIS: Wir zählen die Nullknoten in der Definition von $ mu $ -Galanced oben nicht. (Obwohl ich glaube, dass es keine Rolle spielt, wenn wir das tun).

Answer 1

Beanspruchen: Rotschwarzbäume können willkürlich un-$ mu $-ausgewogen.

Beweisidee: Füllen Sie den rechten Unterbaum mit so vielen Knoten wie möglich und die linke mit so wenigen Knoten wie möglich für eine bestimmte Zahl $ k $ von schwarzen Knoten auf jedem Wurzelblattweg.

Nachweisen: Definieren Sie eine Sequenz $ T_k $ von rot-schwarzen Bäumen so dass $ T_k $ hat $ k $ Schwarze Knoten auf jedem Weg von der Wurzel zu jedem (virtuellen) Blatt. Definieren $ T_k = b (l_k, r_k) $ mit

• $ R_k $ Der komplette Baum der Höhe $ 2k - 1 $ mit dem ersten, dritten, ... ebenen rot, den anderen schwarz und
• $ L_k $ Der komplette Baum der Höhe $ k-1 $ mit allen Knoten schwarz gefärbt.

Klar, alles $ T_k $ sind rot-schwarze Bäume.

Zum Beispiel sind diese $ T_1 $, $ T_2 $ und $ T_3 $, beziehungsweise:

---

^[Quelle]

---

^[Quelle]

---

^[Quelle]

---

Lassen Sie uns nun den visuellen Eindruck der rechten Seite überprüfen riesig im Vergleich zur linken. Ich werde keine virtuellen Blätter zählen; Sie wirken sich nicht auf das Ergebnis aus.

Der linke Unterbaum von $ T_k $ ist vollständig und hat immer Größe $ k-1 $ und enthält daher $ 2^k - 1 $ Knoten. Der richtige Subtree hingegen ist vollständig und hat die Höhe $ 2k - 1 $ und so enthält $ 2^{2K} -1 $ Knoten. Jetzt die $ mu $-Balchenwert für die Wurzel ist

$ qquad displayStyle frac {2^k} {2^k + 2^{2k}} = frac {1} {1 + 2^k} Underset {k to to to { to} 0 $

was beweist, dass es keine gibt $ mu> 0 $ wie gewünscht.

Answer 2

Nein. Betrachten Sie einen rotschwarzen Baum mit der folgenden speziellen Struktur.

• Der linke Subtree ist ein kompletter binärer Baum mit Tiefe $ d $, bei dem jeder Knoten schwarz ist.
• Der rechte Subtree ist ein vollständiger binärer Baum mit Tiefe $ 2d $, in dem jeder Knoten in ungerade Tiefe rot ist und jeder Knoten in gleichmäßiger Tiefe schwarz ist.

Es ist unkompliziert zu überprüfen, ob dies ein gültiger rotschwarzer Baum ist. Aber die Anzahl der Knoten im rechten Subtree ($ 2^{2d+1} -1 $) ist ungefähr das Quadrat der Anzahl der Knoten im linken Teilbaum ($ 2^{d+1} -1 $).