Rot-Schwarz-Bäume (VL 11) Flashcards
Die fünf Eigenschaften eines Rotschwarzbaumes
1) Jeder Knoten rot oder schwarz
2) Wurzel ist schwarz
3) Pfade enden in externen Knoten / null-Zeigern mit Farbe schwarz
4) Jeder nicht-externe Knoten hat genau zwei Kinder
5) Alle Pfade, die im Knoten x starten und bis zum Ende gehen, haben die selbe Schwarzhöhe
Schwarzhöhe eines externen Blattes
bh(null) = 0
Definition Schwarzhöhe bh(x)
Anzahl schwarzer Knoten bis zu einem externen Blatt (Knoten x selbst ausgenommen!!)
Schwarzhöhe eines RBT =
= BH der Wurzel
Mindeste und maximale Anzahl der inneren Knoten eines Rot-Schwarz-Baumes t mit Schwarzhöhe h
mind. (2^h)-1 innere Knoten
max. (4^h)-1 innere Knoten
RBT mit n inneren Knoten hat höchstens Höhe…
2*lg(n+1)
Zeitkomplexität bei den Operationen Suchen, Minimum bestimmen, Nachfolger bestimmen, etc.
Θ(log(n))
Sehr grobes Vorgehen beim Einfügen in einen RBT
1) Wie beim binären Suchbaum einen geeigneten Platz finden
2) Neuen Knoten zunächst rot färben
3) Mögliche Farbverletzung beheben (3 Fälle)
Drei mögliche Farbverletzungsfälle beim Einfügen in einen RBT
1) Großvater schwarz, Onkel rot
2) Großvater schwarz, Onkel schwarz, eingefügter Knoten ist inneres Kind
3) Großvater schwarz, Onkel schwarz, eingefügter Knoten ist äußeres Kind
Farbverletzung beim Einfügen in einen RBT: Vorgehen Fall 1
Vater und Onkel schwarz färben, Großvater rot, anschließend iterativ mögliche Rot-Rot-Verletzungen weiter oben behandeln,
Großvater wird wie eingefügter Knoten behandelt
Farbverletzung beim Einfügen in einen RBT: Vorgehen Fall 2
Um Vaterknoten nach außen rotieren, um Fall 3 zu erhalten
Farbverletzung beim Einfügen in einen RBT: Vorgehen Fall 3
1) Ist der eingefügte Knoten links bzw rechts vom Großvaterknoten, um den Großvaterknoten nach rechts bzw links rotieren.
2) Ursprünglichen Großvater rot, urspr. Vater schwarz färben
3) falls der Ursprüngliche Vater die Wurzel war, diesen Knoten wieder schwarz färben
