close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Folien (Selbsttest, Rot-Schwarz-Baum, B-Baum) - SSW

EinbettenHerunterladen
Rot-Schwarz-Baum
• Was bedeuten die roten Kanten?
• Was bedeuten die schwarzen Kanten?
• Wie kann im Rot-Schwarz-Baum
gesucht werden?
• Wie kann man mehrere gleiche Werte
einfügen?
Rot-Schwarz-Baum
Einfügen von:HITCHHIKER
H
I
Rot-Schwarz-Baum
Einfügen von:HITCHHIKER
H
T
I
Rot-Schwarz-Baum
Einfügen von:HITCHHIKER
H
I
I
T
H
T
Rot-Schwarz-Baum
Einfügen von:HITCHHIKER
I
H
C
T
Rot-Schwarz-Baum
Einfügen von:HITCHHIKER
I
H
C
T
Rot-Schwarz-Baum
Einfügen von:HITCHHIKER
I
H
C
T
Rot-Schwarz-Baum
Einfügen von:HITCHHIKER
I
H
C
H
T
Rot-Schwarz-Baum
Einfügen von:HITCHHIKER
I
H
C
H
T
H
Rot-Schwarz-Baum
Einfügen von:HITCHHIKER
I
H
C
T
H
H
Rot-Schwarz-Baum
Einfügen von:HITCHHIKER
I
I
H
C
T
H
H
Rot-Schwarz-Baum
Einfügen von:HITCHHIKER
I
K
H
C
T
H
I
H
Rot-Schwarz-Baum
Einfügen von:HITCHHIKER
I
H
C
T
H
I
H
K
Rot-Schwarz-Baum
Einfügen von:HITCHHIKER
I
H
C
K
H
I
H
T
Rot-Schwarz-Baum
Einfügen von:HITCHHIKER
I
E
H
C
K
H
I
H
T
Rot-Schwarz-Baum
Einfügen von:HITCHHIKER
I
R
H
C
K
H
E
I
H
T
Rot-Schwarz-Baum
Einfügen von:HITCHHIKER
I
H
C
K
H
E
T
I
H
R
Rot-Schwarz-Baum
Einfügen von:HITCHHIKER
I
H
C
K
H
E
T
I
H
R
B-Baum
• Ist folgender Mehrwegbaum vom Grad 2?
10|20|30|
3| 5| 6|
13|17|15|
23|25|
|
Nein!
Die Schlüssel müssen im jedem Knoten aufsteigend
sortiert sein.
B-Baum
• Ist folgender Mehrwegbaum vom Grad 2?
10|20|30|
3| 5| 6|
13|15|17|
23|25|
|
Nein!
Der linke und rechte Teilbaum eines Schlüssels
darf nicht leer sein.
B-Baum
• Regeln
– Jeder Knoten hat mind. n (2), maximal 2n (4) Schlüssel (die
Wurzel darf weniger haben).
– Schlüssel im Knoten sind aufsteigend.
– Für jeden Schlüssel k in einem inneren Knoten gilt
• Der linke und rechte Teilbaum ist nicht leer.
• Alle Schlüssel im linken Teilbaum sind kleiner als k.
• Alle Schlüssel lm rechten Teilbaum sind größer als k.
– Alle Blätter sind in der selben Stufe.
• Gültiger B-Baum mit gleichen Werten:
6|15|23|
3| 5| |
10|13| |
17|20| |
25|30| |
B-Baum
• Einfügen von: 16, 27, 40, 2, 4, 1
• Löschen von: 17, 10
6|15|23|
3| 5| |
10|13| |
17|20| |
25|30| |
B-Baum
• Einfügen von: 16
6|15|23|
3| 5| |
10|13| |
17|20| |
25|30| |
6|15|23|
3| 5| |
10|13| |
16|17|20|
25|30| |
B-Baum
• Einfügen von: 27, 40, 2, 4
6|15|23|
3| 5| |
10|13| |
16|17|20|
25|30| |
6|15|23|
2|3|4|5
10|13| |
16|17|20|
25|27|30|40
B-Baum
• Einfügen von: 1
6|15|23|
2|3|4|5
10|13| |
16|17|20|
25|27|30|40
3|6|15|23
1|2| |
4|5| |
10|13| |
16|17|20|
25|27|30|40
B-Baum
• Löschen von: 17
3|6|15|23
1|2| |
4|5| |
10|13| |
16|17|20|
25|27|30|40
16|20|
25|27|30|40
3|6|15|23
1|2| |
4|5| |
10|13| |
|
B-Baum
• Löschen von: 10
3|6|15|23
1|2| |
10|13| |
4|5| |
16|20|
|
25|27|30|40
16|20|
|
25|27|30|40
3|15|23|
1|2| |
4|5|6|13
Document
Kategorie
Sport
Seitenansichten
3
Dateigröße
55 KB
Tags
1/--Seiten
melden