|
>
3.1 Knoten und Tiefen
Knoten 1 3 7
Tiefe 0 1 2
Baum b.B. b.B. balancierter Baum
Anmerkung:
balancierter Baum: kurzes Suchen
unbalancierter Baum: langes Suchen
(bei vorsortierten Daten)
2^(T+1) = K+1
T-1 = ld (K+1) -1
T= ld (K+1)-1
3.2 AVL Baum
Erfunden von drei russischen Mathematikern (AVL steht für die drei Anfangsbuchstaben der Nachnamen der Mathematiker). Ein AVL Baum ist ein Baum, bei dem jeder einzelne Knoten eine Tiefendifferenz von 1 hat.
3.3 Degenerierter Baum
Bei einem Degenerierten Baum ist die Struktur vollig unbalanciert. Jeder Knoten hat nur rechte bzw. linke Nachfoger.
Beispiel: das Wort W-U-R-M-L-I-E-D ist degeneriert.
Aber auch: S-O-N-N-I-G
3.4 Baum
Beim 2-3-4 Baum hat man nmax 3 Zahlen, die daraus folgend in maximal 4 Einteilungen unterteilt werden können.
3.5 Lazy Deletion
Ausgehend von der Grundlage, kleinere Kinder eines Knotens werden linke, größere jeweils rechts angeornet, ergibt sich folgendes Verfahren zum füllen der Lücke, an der ein Knoten gelöscht wurde. An Stelle des gelöschten Knotens können nur die Schwarz markierten Knoten stehen.
|
