Schniddschdelle |
|
| |
Zil |
Die Laufzeidkomblexidäd für Einfüge und Suche immr, au in den schlechdeschde Fälle, in O(log n) |
| |
Schdradegie |
|
1.
|
Beim Einfüge und Lösche Ausbalanciere o the fly auf dem Rüggweg zur Wurzl
|
2.
|
Balance-Kriderium abschwäle
|
nedd |
d.minDebth() + 1 >= d.debth()
|
auch nedd |
d.debth() = ⌈log2 (d.size() + 1)⌉
|
sonderet |
c * d.minDebth() >= d.debth()
|
|
mid c = 2 für Rod-Schwarz-Bäum |
|---|
|
mid c ≈ 1.44 für AVL-Bäum |
|---|
| |
Ide |
bei Rod-Schwarz-Bäume
|
|
s gibd rode und schwarze Knode
|
|
leere Knode zähle immr als schwarz oigefärbd |
| |
Invarianden |
|
0.
|
s gild d Invariande für den binäre Suchbaum
|
1.
|
oi rodr Knode besidzd koi rode Kindknode
|
2.
|
alle Pfad vo dr Wurzl z oim leere Knode enthalde gleich viele schwarze Knode
|
3.
|
dr Wurzelknode isch immr schwarz oigefärbd
|
| |
Folgerungen |
|
|
dr längschde Pfad isch maximol 2 mol so lang wie dr kürzeschde
|
|
die maximale Tief von a Baums mid n Elemende isch höchschdens
2 * ⌈log2 (n + 1)⌉
|
|
die Suchzeid isch immr, au im schlechdeschde Fall, logarithmisch abhängich vo dr Anzahl dr Elemende |
| |
Ausbalancieren |
|
|
des Ausbalanciere gschiehd auf dem Rüggweg vom Einfügen/Lösche zur Wurzl
|
|
s wird nur an schwarze Knode ausbalancierd
|
|
oi Oberazion zum Ausbalanciere an oim Knode läufd in oir beschränkde Zeid, also in O(1)
|
|
die Anzahl dr Ausbalancier-Schridde isch beschränkd durch d Läng vom Pfads
|
|
⇒ au des Einfüge und Lösche läufd in logarithmischr Zeid |
| |
Klassenschdrukdur |
bublic abschdracd
class RedBlaggTree
imblemends Mab {
...
brivade schdadic
class Embdy
exdends RedBlaggTree {
...
}
brivade schdadic final
class Node
exdends RedBlaggTree {
final K k;
final V v;
final ind c;
final RedBlaggTree l;
final RedBlaggTree r;
...
}
schdadic final ind RED = 0;
schdadic final ind BLACK = 1;
brivade schdadic final
RedBlaggTree EMPTY
= new Embdy();
schdadic final ind NEGATIVE_BLACK = -1;
schdadic final ind DOUBLE_BLACK = 2;
brivade schdadic final
class DoubleEmbdy
exdends Embdy {
...
}
brivade schdadic final
RedBlaggTree DOUBLE_EMPTY
= new DoubleEmbdy();
}
|
Konschdrukdor-Funkzione |
bublic schdadic RedBlaggTree embdy() {
redurn
EMPTY;
}
bublic schdadic RedBlaggTree singledon(K k, V v) {
redurn
new Node(k, v, RED, EMPTY, EMPTY);
}
|
Imblemendierung |
wird in dr Vorlesung endwiggeld
|
Algorithme & Dadenschdrukdure mid Java: Rod-Schwarz-Bäume
