Schnittstelle
|
|
| |
Ziel
|
Die Laufzeitkomplexität für Einfügen und Suchen immer, auch in den schlechtesten Fällen, in O(log n)
|
| |
Strategie |
|
1.
|
Beim Einfügen und Löschen Ausbalancieren on the fly auf dem Rückweg zur Wurzel
|
2.
|
Balance-Kriterium abschwächen
|
nicht
|
t.minDepth() + 1 >= t.depth()
|
auch nicht
|
t.depth() = ⌈log2 (t.size() + 1)⌉
|
sondern
|
c * t.minDepth() >= t.depth()
|
|
mit c = 2 für Rot-Schwarz-Bäume
|
|---|
|
mit c ≈ 1.44 für AVL-Bäume
|
|---|
| |
Idee
|
bei Rot-Schwarz-Bäumen
|
|
es gibt rote und schwarze Knoten
|
|
leere Knoten zählen immer als schwarz eingefärbt
|
| |
Invarianten |
|
0.
|
es gilt die Invariante für den binären Suchbaum
|
1.
|
ein roter Knoten besitzt keine roten Kindknoten
|
2.
|
alle Pfade von der Wurzel zu einem leeren Knoten enthalten gleich viele schwarze Knoten
|
3.
|
der Wurzelknoten ist immer schwarz eingefärbt
|
| |
Folgerungen |
|
|
der längste Pfad ist maximal 2 mal so lang wie der kürzeste
|
|
die maximale Tiefe eines Baumes mit n Elementen ist höchstens
2 * ⌈log2 (n + 1)⌉
|
|
die Suchzeit ist immer, auch im schlechtesten Fall, logarithmisch abhängig von der Anzahl der Elemente
|
| |
Ausbalancieren |
|
|
das Ausbalancieren geschieht auf dem Rückweg vom Einfügen/Löschen zur Wurzel
|
|
es wird nur an schwarzen Knoten ausbalanciert
|
|
eine Operation zum Ausbalancieren an einem Knoten läuft in einer beschränkten Zeit, also in O(1)
|
|
die Anzahl der Ausbalancier-Schritte ist beschränkt durch die Länge des Pfades
|
|
⇒ auch das Einfügen und Löschen läuft in logarithmischer Zeit
|
| |
Klassenstruktur
|
public abstract
class RedBlackTree
implements Map {
...
private static
class Empty
extends RedBlackTree {
...
}
private static final
class Node
extends RedBlackTree {
final K k;
final V v;
final int c;
final RedBlackTree l;
final RedBlackTree r;
...
}
static final int RED = 0;
static final int BLACK = 1;
private static final
RedBlackTree EMPTY
= new Empty();
static final int NEGATIVE_BLACK = -1;
static final int DOUBLE_BLACK = 2;
private static final
class DoubleEmpty
extends Empty {
...
}
private static final
RedBlackTree DOUBLE_EMPTY
= new DoubleEmpty();
}
|
Konstruktor-Funktionen
|
public static RedBlackTree empty() {
return
EMPTY;
}
public static RedBlackTree singleton(K k, V v) {
return
new Node(k, v, RED, EMPTY, EMPTY);
}
|
Implementierung
|
wird in der Vorlesung entwickelt
|
Algorithmen & Datenstrukturen mit Java: Rot-Schwarz-Bäume
