Sind nicht alle rot-schwarzen Bäume ausgeglichen?

30

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 μ 1μ , wenn für jeden KnotenNdie Ungleichung0μ12N

μ|NL|+1|N|+11μ

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).μ>μ|NL|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μμ>0O(logn) , wodurch die netten beibehalten werden.

Die Frage ist also:

Gibt es ein so dass jeder ausreichend große rot-schwarze Baum μ- ausgeglichen ist?μ>0μ


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).μ

Aryabhata
quelle
@Aryabhata: Was ist mit der Eindeutigkeit ( ) in Ihrer Bearbeitung? Mir geht es gut mit der Tatsache, dass 1μ>μ ausgeglichen impliziert113 ausgeglichen. Ich denke nicht, dass Sie dasgenaueμfinden müssen, umzu beweisen, dass die HöheO(logn) ist. Vermisse ich etwas? 14 μO(logn)
Jmad
Darüber hinaus benötigen Sie eine negative Aussage für jeden ein Gegenbeispiel Kette mit einem Baum zu schaffen , . Jede unendliche Kette, deren Knotengröße nicht abnimmt, würde ausreichen, nicht wahr? nN
Raphael
@jmad: Ohne den -Edit ist jeder Baum trivial 0- ausgeglichen und daher haben wir keine triviale Antwort auf die Frage. Das wollte ich vermeiden. μ0
Aryabhata
@Raphael: Ich verstehe nicht. Die Knotengröße des Baum ist n . Sie sagen, es spielt keine Rolle, welchen Baum wir für R B n und dieses μ n0 auswählen ? Scheint mir nicht offensichtlich, und darum geht es in der Frage! nthnRBnμn0
Aryabhata
1
In einer früheren Version dieser Frage wurde behauptet, dass die Laufzeit eines rekursiven Algorithmus in einem rot-schwarzen Baum, der bei jedem Schritt einen linearen Arbeitsaufwand leistet, nicht unbedingt . Diese Behauptung war falsch; Höhenausgleich impliziert, dass die Tiefe eines n- Knoten-Rot-Schwarz-Baums O ( log n ) ist . Wenn Sie also auf jeder Ebene des Baums O ( n ) arbeiten, ist die Gesamtarbeit O ( n log n ) . O(nlogn)nO(logn)O(n)O(nlogn)
JeffE

Antworten:

31

Anspruch : Rot-Schwarz - Bäume können willkürlich sein un- μ -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 Tk von rot-schwarzen Bäumen, so dass Tk auf jedem Pfad von der Wurzel zu einem beliebigen (virtuellen) Blatt k schwarze Knoten hat . Definiere Tk=B(Lk,Rk) mit

  • Rk der komplette Baum der Höhe2k1 mit der ersten, dritten, ... Stufe rot, die anderen schwarz und
  • Lk der vollständige Baum der Höhek1 mit allen Knoten, die schwarz gefärbt sind.

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

Zum Beispiel sind dies T1 , T2 bzw. T3 :


T_1
[ Quelle ]


T_2
[ Quelle ]


T_3
[ 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.

Tkk12k12k122k1μ

2k2k+22k=11+2kk0

μ>0

Raphael
quelle
14

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

  • d
  • 2d

22d+112d+11

JeffE
quelle
22d+1+2d+11n
1
n
@JeffE: Grundsätzlich wäre die Gegenbeispielkette dann eher eine "dichte" Untermenge als eine "spärliche" Untermenge. Vielleicht werde ich die Formulierung der Frage ändern.
Aryabhata