Anhang: AVL-Bäume & Heaps

Die Sweep-Algorithmen brauchen zwei Datenstrukturen: einen balancierten Suchbaum für den Status und eine Prioritätswarteschlange für die Ereignisse. Die Folien wiederholen dafür AVL-Bäume und Heaps (Folien 45–73).

AVL-Bäume

Definitionen (Folie 45)

• Ein Suchbaum ist balanciert, wenn seine Höhe $O(\log n)$ ist. Dann laufen alle Wörterbuch-Operationen (Suchen, Einfügen, Löschen) in $O(\log n)$.
• Ein binärer Suchbaum ist ein AVL-Baum, wenn sich in jedem Knoten die Höhen der beiden Teilbäume um höchstens 1 unterscheiden.
• Ein AVL-Baum hat höchstens Höhe ca. $1{,}44\log_2 n$.
• Name: Adelson-Velskij und Landis (1962).

Balance eines Knotens = Höhe(rechts) − Höhe(links). Ein leerer Teilbaum hat Höhe $-1$, ein Blatt Höhe $0$. Im AVL-Baum ist die Balance überall $\in\{-1,0,+1\}$.

Rebalancieren durch Rotationen (Folien 47–51)

Nach Einfügen oder Löschen kann irgendwo Balance $\pm2$ entstehen. Vier Fälle:

Fall	Situation	Rotation
A1	linkslastig ($-2$), linkes Kind hat Balance $-1$ oder $0$	Rechtsrotation
A2	linkslastig ($-2$), linkes Kind hat Balance $+1$	Links-Rechts (Doppelrotation)
B1	rechtslastig ($+2$), rechtes Kind hat Balance $0$ oder $+1$	Linksrotation
B2	rechtslastig ($+2$), rechtes Kind hat Balance $-1$	Rechts-Links (Doppelrotation)

Merkregel: Zeigen Knoten und Kind in dieselbe Richtung (beide links- oder beide rechtslastig), reicht eine einfache Rotation. Zeigen sie in entgegengesetzte Richtungen („Knick“), braucht man eine Doppelrotation: erst das Kind gerade ziehen, dann den Knoten rotieren.

Prinzip (Folie 52)

1. Einfügen / Löschen wie im normalen binären Suchbaum.
2. Vom geänderten Knoten nach oben zur Wurzel laufen und unbalancierte Teilbäume per Rotation reparieren.

• Beim Einfügen reicht höchstens eine (ggf. doppelte) Rotation.
• Beim Löschen können mehrere Rotationen entlang des Pfads nötig sein.

Code (Folien 55–60)

struct Node { int height; KeyType key; ValueType val; Node *left, *right; };

int getHeight(const Node* p)  { return p ? p->height : -1; }
int getBalance(const Node* p) { return p ? getHeight(p->right) - getHeight(p->left) : 0; }

void rotateRight(Node*& p) {        // Vor.: p->left != 0
    Node* q  = p->left;
    p->left  = q->right;
    q->right = p;
    p->height = std::max(getHeight(p->left), getHeight(p->right)) + 1;
    q->height = std::max(getHeight(q->left), getHeight(q->right)) + 1;
    p = q;
}
// rotateLeft analog
void rotateLeftRight(Node*& p) { rotateLeft(p->left);   rotateRight(p); }
void rotateRightLeft(Node*& p) { rotateRight(p->right); rotateLeft(p);  }

void balance(Node*& p) {
    if (!p) return;
    p->height = std::max(getHeight(p->left), getHeight(p->right)) + 1;
    if (getBalance(p) == -2) {
        if (getBalance(p->left) <= 0) rotateRight(p);     // A1
        else                          rotateLeftRight(p); // A2
    } else if (getBalance(p) == +2) {
        if (getBalance(p->right) >= 0) rotateLeft(p);      // B1
        else                           rotateRightLeft(p); // B2
    }
}

bool insert(KeyType key, ValueType& v, Node*& p) {
    bool result;
    if (!p) { p = new Node{0, key, v, nullptr, nullptr}; result = true; }
    else if (key < p->key) result = insert(key, v, p->left);
    else if (key > p->key) result = insert(key, v, p->right);
    else                   result = false;           // Schlüssel existiert schon
    if (result) balance(p);                           // auf dem Rückweg rebalancieren
    return result;
}

Operation	Laufzeit
Rotationen, balance	$O(1)$
search, insert, remove	$O(\log n)$

Heaps

Definition (Folien 62–63)

(Max-)Heap-Eigenschaft: In jedem Knoten $k$ gilt $k.\text{key} \ge k.\text{left.key}, k.\text{right.key}$. (Min-Heap analog mit $\le$.)

Ein Heap ist ein Binärbaum, der

1. in jedem Knoten die Heap-Eigenschaft erfüllt,
2. auf allen Ebenen außer der letzten vollständig gefüllt ist,
3. dessen letzte Ebene linksbündig gefüllt ist.

Folgen (Folie 64): Das Maximum steht in der Wurzel, und die Höhe ist $\Theta(\log n)$.

Unterschied zum Suchbaum: Der Suchbaum kann beliebige Schlüssel schnell finden, der Heap nur das Maximum (bzw. Minimum). Das reicht für die Ereignisstruktur, denn man braucht immer nur das nächste Ereignis.

Als Array (Folie 65)

Ein Heap lässt sich in-situ im Array $a[1..n]$ speichern: Die Kinder von $a[i]$ stehen in $a[2i]$ und $a[2i+1]$, der Elternknoten in $a[\lfloor i/2\rfloor]$.

Aufbau: build_heap und heapify (Folien 66–71)

void heapify(Node a[], int n, int i) {        // a[1..n]
    int max = i, li = 2 * i, re = li + 1;
    if (li <= n && a[li].key > a[max].key) max = li;
    if (re <= n && a[re].key > a[max].key) max = re;
    if (i != max) { std::swap(a[i], a[max]); heapify(a, n, max); }
}

void build_heap(Node a[], int n) {
    for (int i = n / 2; i > 0; --i) heapify(a, n, i);   // a[n/2+1..n] sind Blätter
}

heapify(i) setzt voraus, dass beide Teilbäume von $i$ schon Heaps sind. Ist $a[i]$ kleiner als ein Kind, wird es mit dem größeren Kind getauscht und sinkt weiter nach unten. Deshalb läuft build_heap von unten nach oben.

Laufzeit (Folien 72–73)

• heapify: Rekursion $T(n)\le T(2n/3)+\Theta(1)$ (der linke Teilbaum hat höchstens $2n/3$ Knoten, wenn die letzte Ebene genau halb voll ist). Mit dem Master-Theorem: $T(n)=O(\log n)$. Alternativ: $O(h)$ für einen Knoten der Höhe $h$.
• build_heap: Die naive Abschätzung $n\cdot O(\log n)$ ist zu grob. Es gibt höchstens $\lceil n/2^{h+1}\rceil$ Knoten der Höhe $h$, also $\sum_{h=0}^{\lfloor\log n\rfloor}\frac{n}{2^{h+1}}\,O(h) = O\Big(n\sum_{h=0}^{\infty}\frac{h}{2^{h+1}}\Big) = O(n),$ weil $\sum_{h\ge0} h/2^{h} = 2$.

Einen Heap baut man also in linearer Zeit, Einfügen und Maximum-Entfernen kosten je $O(\log n)$.