AVL-tree

#Definition #IntroProg #Informatik #MINTgrün #Studium

AVL-Bäume

Problem von Bäumen ist, dass ein binärer Suchbaum degeneriert (nicht balanciert) sein kann. Das hat zur folge, dass ein binary tree im worst case eine Liste ist. Deswegen gibt es AVL trees
wenn man sicherstellt, dass die Höhe der Teilbäume ungefähr gleich ist, dann ist die Höhe des Baumes O(log n)
AVL-Bäume wurde von Adelson-Velsky und Landis entwickelt
Ein binärer Baum heißt AVL-Baum, wenn für jeden Knoten gilt: Die Höhe seines linken und rechten Teilbaums unterscheidet sich höchstens um 1
Durch Rotationen wird aus einem binären Suchbaum ein AVL-Baum

Links- und Rechtsrotation

man stelle sich vor, dass die Elemente Murmeln und die Pointer Schnüre sind. Hält man einen balancierten Baum an der Wurzelmurmel fest, dann sind die Murmeln ganz unten etwa auf der selben höhe. ist das nicht so, so kann man die Kindmurmel der Wurzel auf der Seite des längeren teilbaumes anfassen, was dafür sorgt, dass der Baum balanciert wird.
konkreter gesagt muss man bei einer Linksrotation im oberen Beispiel, b als neuen rechten Kindknoten von x festlegen. y wird der Vater von x und das linke Kind von y wird x.

\begin{array}{ll} Linkrotation (x) \\ 1. & y \leftarrow r c [x] \\ 2. & r c [x] \leftarrow l c [y] \\ 3. & if l c [y] \neq nil then p [l c [y]] \leftarrow x \\ 4. & p [y] \leftarrow p [x] \\ 5. & if p [x] = nil then r o o t [T] \leftarrow y \\ 6. & else if x = l c [p [x]] then l c [p [x]] \leftarrow y \\ 7. & else r c [p [x]] \leftarrow y \\ 8. & l c [y] \leftarrow x \\ 9. & p [x] \leftarrow y \end{array}

Beinahe-AVL-Baum

Definition:

Ein Baum heißt beinahe-AVL-Baum, wenn die AVL-Eigenschaft in jedem Knoten außer der Wurzel erfüllt ist und sich die Höhe der Unterbäume der Wurzel um höchstens 2 unterscheidet.

\begin{array}{ll} Balance (y) \\ 1. & if h [l c [y]] > h [r c [y]] + 1 then \\ 2. & if h [l c [l c [y]]] < h [r c [l c [y]]] then \\ 3. & Linkrotation (l c [y]) \\ 4. & Rechtsrotation (y) \\ 5. & else if h [r c [y]] > h [l c [y]] + 1 then \\ 6. & if h [r c [r c [y]]] < h [l c [r c [y]]] then \\ 7. & Rechtsrotation (r c [y]) \\ 8. & Linkrotation (y) \end{array}

Fall 1: Einfache Rechtsrotation

!introprog-v11-baeume-avl, p.71

Fall 2: Doppelrotation

B ist der Verursacher
!introprog-v11-baeume-avl, p.73
Teile B in zwei Unterteile auf
!introprog-v11-baeume-avl, p.74
Linksrotation
!introprog-v11-baeume-avl, p.75
Rechtsrotation
!introprog-v11-baeume-avl, p.76

Operationen

Notes

Einfügen

\begin{aligned} AVL-Einfügen(t,x) \\ 1. & if t = nil then \\ 2. & t \leftarrow new node (x); h [t] \leftarrow 0; return \\ 3. & else if x < key [t] then AVL-Einfügen (lc [t], x) \\ 4. & else if x > key [t] then AVL-Einfügen (rc [t], x) \\ 5. & else return ▹ Schlüssel schon vorhanden \\ 6. & h [t] \leftarrow 1 + max {h [lc [t]], h [rc [t]]} \\ 7. & Balance (t) \end{aligned}

logarithmische Laufzeit: O(h) = O(log n)

Löschen

\begin{aligned} AVL-Löschen(t,x) \\ 01. & if t = nil then return ▹ x nicht im Baum \\ 02. & else if x < key [t] then AVL-Löschen (lc [t], x) \\ 03. & else if x > key [t] then AVL-Löschen (rc [t], x) \\ 04. & else if lc [t] = nil then ersetze t durch rc [t] \\ 05. & else if rc [t] = nil then ersetze t durch lc [t] \\ 06. & else u = MaximumSuche (lc [t]) \\ 07. & Kopiere Informationen von u nach t \\ 08. & AVL-Löschen (lc [t], key [u]) \\ 09. & if t \neq nil then h [t] = 1 + max {h [lc [t]], h [rc [t]]} \\ 10. & Balance (t) \end{aligned}

Beweis für Höhe

Satz:

Für jeden AVL-Baum der Höhe $h \geq 0$ mit n Knoten gilt: $(3 / 2)^{h} \leq n \leq 2^{h + 1} - 1$

Beweis: durch Fallunterscheidung

a) $n \leq 2^{h + 1} - 1$ (obere Schranke)
- AVL-Baum ist Binärbaum
- Ein vollständiger Binärbaum hat eine maximale Anzahl Knoten unter allen Binärbäumen der Höhe h
- N(h) = Anzahl Knoten eines vollständigen Binärbaums der Höhe h
- $N (h) = 1 + 2 + 3 + 4 \dots + 2^{k} = \sum_{i = 0}^{h} 2^{i} = 2^{h + 1} - 1$

b) $(3 / 2)^{h} \leq n$ (untere Schranke)
- Beweis per Induktion über die Struktur von AVL-Bäumen
- (I.A.) Wir betrachten alle AVL-Bäume der Höhe $0$ und $1$ .
  - $h = 0$ : Der Baum hat einen Knoten. Es gilt $(3 / 2)^{h} = 1 \leq 1$ .
  - $h = 1$ : Der Baum hat 2 oder 3 Knoten. Es gilt $(3 / 2)^{h} = 3 / 2 \leq 2 \leq 3$ .
- (I.V.) Für jeden AVL-Baum der Höhe $j, 0 \leq j \leq h$ , gilt der Satz.
- (I.S.) Sei $h \geq 1$ . Betrachte AVL-Baum $T$ der Höhe $h + 1$ mit Wurzel $v$ .
  - Seien $A, B$ linker bzw. rechter Teilbaum von $v$ .
  - $A$ oder $B$ (oder beide) hat Tiefe $h$ .
  - Wegen AVL-Eigenschaft haben $A$ und $B$ Tiefe mindestens $h - 1 \geq 0$ .
  - Da $T$ ein AVL-Baum ist, sind auch $A$ und $B$ AVL-Bäume.
  - Wir können (I.V.) anwenden, da $A$ und $B$ AVL-Bäume der Tiefe $\geq 0$ sind
  - Es gibt drei Fälle:
    1. $A, B$ haben Höhe $h$
    2. $A$ hat Höhe $h$ und $B$ hat Höhe $h - 1$
    3. $A$ hat Höhe $h - 1$ und $B$ hat Höhe $h$
  - Sei $T (h)$ die minimale Anzahl Knoten in einem AVL-Baum der Tiefe $h$ .
  - Nach (I.V.) gilt in allen drei Fällen

\begin{aligned} T (h + 1) & \geq T (h) + T (h - 1) + 1 & \geq {(\frac{3}{2})}^{h} + {(\frac{3}{2})}^{h - 1} + 1 \\ \geq (1 + \frac{3}{2}) \cdot {(\frac{3}{2})}^{h - 1} & \geq {(\frac{3}{2})}^{2} \cdot {(\frac{3}{2})}^{h - 1} & = {(\frac{3}{2})}^{h + 1} . \end{aligned}