04AdvancedDataStructures.pdf

Algorithmen und Datenstrukturen 21.PMarc Fischlin, SS 2024 04 Fortgesch...

Algorithmen und Datenstrukturen 21.PMarc Fischlin, SS 2024 04 Fortgeschrittene Datenstrukturen 13. Oktober 2010 | Dr.Marc Fischlin | Kryptosicherheit | 1  Binäre Suchbäume Rot-Schwarz-Bäume Binäre Suchbäume Operation Laufzeit* Einfügen (h) Können wir 𝒉 = 𝑶(log 𝒏) Löschen (h) garantieren? Suchen (h) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 2 Rot-Schwarz-Bäume in Java Quelle: Wikipedia Class TreeMap in Java 22 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 3 Anwendung: Linux Completely Fair Scheduling verwendet Rot-Schwarz-Bäume, (2) addiere zuge- um Worst-Case-Laufzeit 𝑂 log 𝑛 wiesene Zeit zu erreichen key = virtual run time 23 6500 eines Prozesses in Nanosekunden 17 4817 24 7415 (3) füge mit aktualisierter Zeit wieder ein (1) nächsten Prozess holen 9 2367 22 5617 25 8256 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 4 Rot-Schwarz-Bäume Ein Rot-Schwarz-Baum ist ein binärer Suchbaum, so dass gilt: (1) Jeder Knoten hat die Farbe rot oder schwarz, 23 (2) Die Wurzel ist schwarz*, (3) Wenn ein Knoten rot ist, sind 17 24 seine Kinder schwarz („Nicht-Rot-Rot“-Regel), (4) Für jeden Knoten hat jeder 9 22 25 Pfad im Teilbaum zu einem Blatt oder Halbblatt die gleiche Anzahl von schwarzen Knoten zusätzlicher Knoten-Eintrag („gleiche Anzahl schwarz“). x.color=red oder black *sofern Baum nicht leer Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 5 Bestimmte Farben ⇔ rote Knoten haben genau 0 oder 2 Kinder Halbblätter im Rot-Schwarz-Baum sind schwarz 23 Wenn Halbblatt rot wäre, dann wäre (einziges) Kind schwarz. 17 24 24 =0 9 22 25 25 ≥𝟏 Dann gäbe es im kinderlosen Pfad keinen schwarzen Knoten, im anderen aber mindestens einen schwarzen Knoten. Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 6 „Schwarzhöhe“ eines Knoten Die Schwarzhöhe eines Knoten SH=2 x ist die (eindeutige) Anzahl von 23 schwarzen Knoten auf dem Weg zu einem Blatt oder Halbblatt im Teilbaum des Knoten SH=1 SH=1 17 24 9 22 25 SH=1 SH=1 SH=0 Für leeren Baum setzt man SH 𝑛𝑖𝑙 = 0 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 7 Höhe eines Rot-Schwarz-Baums Ein Rot-Schwarz-Baum mit 𝑛 Knoten hat maximale Höhe ℎ ≤ 2 ∙ log 2 (𝑛 + 1). 23 Intuition: (1) In jedem Unterteilbaum gleiche Anzahl schwarzer Knoten auf jedem Pfad (2) Maximal zusätzlich gleiche Anzahl roter Knoten auf diesem Pfad (3) Daher einigermaßen ausbalanciert und Höhe 𝑂(log 𝑛) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 8 Höhe eines Rot-Schwarz-Baums: Beweis (I) Ein Rot-Schwarz-Baum mit 𝑛 Knoten hat Zeige zuerst: maximale Höhe ℎ ≤ 2 ∙ log 2 (𝑛 + 1). Teilbaum in Knoten x hat mindestens 2𝑆𝐻(𝑥) − 1 Knoten Beweis per Induktion: Leerer Baum hat 𝑛 = 0 Knoten und mind. 2𝑆𝐻(𝑥) − 1 = 20 − 1 = 0 Knoten. Teilbäume haben Schwarzhöhe 𝑆𝐻(𝑥) oder 𝑆𝐻(𝑥) − 1, x je nachdem ob x rot oder schwarz. Induktionsvoraussetzung: Also jeweils mind. 2𝑆𝐻 𝑥 −1 − 1 Knoten in Teilbäumen. Insgesamt mindestens (2𝑆𝐻 𝑥 −1 − 1) + (2𝑆𝐻 𝑥 −1 − 1) + 1 = 2𝑆𝐻 𝑥 −1 Knoten im Teilbaum von x. ≥ 2𝑆𝐻 𝑥 −1 −1 ≥ 2𝑆𝐻 𝑥 −1 −1 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 9 Höhe eines Rot-Schwarz-Baums: Beweis (II) Ein Rot-Schwarz-Baum mit 𝑛 Knoten hat Zeige zuerst: maximale Höhe ℎ ≤ 2 ∙ log 2 (𝑛 + 1). Teilbaum in Knoten x hat mindestens 2𝑆𝐻(𝑥) − 1 Knoten Sei ℎ Höhe der Baumes mit Wurzel r und 𝑛 Knoten. Dann 𝑆𝐻 r ≥ ℎ/2 , da maximal die Hälfte der Knoten auf längstem Pfad rot. Dann 𝑛 ≥ 2ℎ/2 − 1 bzw. log 2 (𝑛 + 1) ≥ ℎ/2. ∎ Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 10  Kann ein Rot-Schwarz-Baum nur aus schwarzen Knoten bestehen? Wie sieht er dann aus? Gibt es für jedes 𝑛 einen Rot-Schwarz-Baum, der die obere Schranke 2 ∙ log 𝑛 + 1 für die Höhe auch (fast) erreicht? Wie sieht ein Algorithmus aus, der überprüft, ob ein BST auch ein Rot-Schwarz-Baum ist? Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 11 Implementierungen mittels Sentinel T.sent T.root.parent=T.sent nil T.sent.key=nil 23 T.sent.color=black T.sent.parent=T.sent T.sent.left=T.sent T.sent.right=T.sent 17 24 Beispiel: x.parent.parent.left 9 22 25 immer wohldefiniert Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 12 Einfügen oder 1. Finde Elternknoten y wie im BST x 2. Färbe neuen Knoten z rot 3 3. Stelle RS-Baum-Bedingung wieder her A y 1 z C 2 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 13 Einfügen: Rotation oder oder rotateLeft(T,x) x y A y x C rotateRight(T,y) B C A B Achtung: Rot-Schwarz-Baum-Bedingungen sind nach Rotation evtl. verletzt Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 14 Rotation: Algorithmus (I) rotateLeft(T,x) //x.right!=nil oder 1 y=x.right; 2 x.right=y.left; x 3 IF y.left != nil THEN 4 y.left.parent=x; 5 y.parent=x.parent; 6 IF x.parent==T.sent THEN 7 T.root=y A y 8 ELSE 9 IF x==x.parent.left THEN 10 x.parent.left=y 11 ELSE 12 x.parent.right=y; B C 13 y.left=x; 14 x.parent=y; Laufzeit = Θ(1) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 15 Rotation: Algorithmus (II) rotateLeft(T,x) //x.right!=nil oder 1 y=x.right; 2 x.right=y.left; x 3 IF y.left != nil THEN 4 y.left.parent=x; 5 y.parent=x.parent; 6 IF x.parent==T.sent THEN 7 T.root=y A 1-4 y 8 ELSE 9 IF x==x.parent.left THEN 10 x.parent.left=y 11 ELSE 12 x.parent.right=y; B C 13 y.left=x; 14 x.parent=y; Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 16 Rotation: Algorithmus (III) rotateLeft(T,x) //x.right!=nil oder 1 y=x.right; 2 x.right=y.left; x 5-12 3 IF y.left != nil THEN 4 y.left.parent=x; 5 y.parent=x.parent; 6 IF x.parent==T.sent THEN 7 T.root=y A y 8 ELSE 9 IF x==x.parent.left THEN 10 x.parent.left=y 11 ELSE 12 x.parent.right=y; B C 13 y.left=x; 14 x.parent=y; Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 17 Rotation: Algorithmus (IV) rotateLeft(T,x) //x.right!=nil 13-14 oder 1 y=x.right; 2 x.right=y.left; x 3 IF y.left != nil THEN 4 y.left.parent=x; 5 y.parent=x.parent; 6 IF x.parent==T.sent THEN 7 T.root=y A y 8 ELSE 9 IF x==x.parent.left THEN 10 x.parent.left=y 11 ELSE 12 x.parent.right=y; B C 13 y.left=x; 14 x.parent=y; Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 18  insert(T,z) Einfügen //z.left==z.right==nil; 1 x=T.root; px=T.sent; Funktioniert wie beim 2 WHILE x != nil DO binären Suchbaum 3 px=x; (mit Sentinel) 4 IF x.key > z.key THEN 5 x=x.left 6 ELSE 7 x=x.right; 8 z.parent=px; 9 IF px==T.sent THEN 10 T.root=z 11 ELSE 12 IF px.key > z.key THEN Änderung: 13 px.left=z Farbe des neuen Knoten auf 14 ELSE rot setzen, dann 15 px.right=z; RSB-Bedingung 16 z.color=red; wieder herstellen 17 fixColorsAfterInsertion(T,z); Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 19  fixColorsAfterInsertion(T,z) Aufräumen 1 WHILE z.parent.color==red DO 2 IF z.parent==z.parent.parent.left THEN 3 y=z.parent.parent.right; 4 IF y!=nil AND y.color==red THEN 5 z.parent.color=black; 6 y.color=black; 7 z.parent.parent.color=red; 8 z=z.parent.parent; 9 ELSE 10 IF z==z.parent.right THEN 11 z=z.parent; 12 rotateLeft(T,z); 13 z.parent.color=black; 14 z.parent.parent.color=red; 15 rotateRight(T,z.parent.parent); 16 ELSE 17 … //exchange left and right 18 T.root.color=black; Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 20 Aufräumen: Idee für einfache Bäume (I) 20 20 20 19 22 19 22 19 22 18 18 z 18 z z Schwarzhöhe des Achtung: Zweiter Schritt geht Baumes bleibt erhalten hier nur, weil 20 Wurzel ist Wenn Teilbaum, dann stattdessen „rekursiv in Knoten 20 aufräumen“ Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 21 Aufräumen: Idee für einfache Bäume (II) 20 20 19 19 19 18 20 z 18 18 z z Schwarzhöhe des Baumes bleibt erhalten Selbst wenn Teilbaum, dann kein weiteres Aufräumen nötig Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 22  fixColorsAfterInsertion(T,z) Aufräumen (I) z nicht Wurzel, 1 WHILE z.parent.color==red DO nicht Kind der Wurzel 2 IF z.parent==z.parent.parent.left THEN 3 y=z.parent.parent.right; 4 IF y!=nil AND y.color==red THEN 5 z.parent.color=black; 6 y.color=black; 7 z.parent.parent.color=red; 23 8 z=z.parent.parent; 9 ELSE 10 IF z==z.parent.right THEN 17 24 17 11 z=z.parent; 12 rotateLeft(T,z); 9 20 13 25 5-7 z.parent.color=black; 9 20 z 8 14 z.parent.parent.color=red; 15 rotateRight(T,z.parent.parent); 19 22 y 161-3 ELSE 19 22 y 17 … //exchange left and right z 18 T.root.color=black; z 18 18 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 23  fixColorsAfterInsertion(T,z) Aufräumen (II) 1 WHILE z.parent.color==red DO nächste 2 IF z.parent==z.parent.parent.left THEN WHILE-Iteration 3 y=z.parent.parent.right; 4 IF y!=nil AND y.color==red THEN … 9 ELSE 10 IF z==z.parent.right THEN 9-11 11 z=z.parent; 23 12 rotateLeft(T,z); 23 z 1 z.parent.color=black; 2 y 1-3 z.parent.parent.color=red; 17 24 20 3 rotateRight(T,z.parent.parent); z 4 ELSE 9 20 z 5 12 25 … //exchange left and 17 right 22 6 T. 19 22 9 19 1 root.color=bla 18 18 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 24  fixColorsAfterInsertion(T,z) Aufräumen (III) … WHILE-Schleife 9 ELSE z.parent.color=red 10 IF z==z.parent.right THEN hier im Beispiel 11 z=z.parent; danach beendet 12 rotateLeft(T,z); 13 z.parent.color=black; 14 z.parent.parent.color=red; 23 15 rotateRight(T,z.parent.parent); 1 … //exchange left and 20 right 20 24 z 2 T. z 17 22 25 13-15 17 23 1 root. 9 19 9 19 22 24 Beachte: color=bla 18 18 T.root.color=black; 18 25 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 25 Aufräumen: Schleifeninvariante (I) Schleifeninvariante: 1. z.color==red 2. Wenn z.parent Wurzel, dann z.parent.color==black 3. Wenn der aktuelle Baum kein Rot-Schwarz-Baum ist, dann weil z als Wurzel die Farbe rot hat, oder weil „Nicht-Rot-Rot-Regel“ für z,z.parent verletzt ist.* *anderen Regeln: Schwarzhöhe und jeder Knoten rot oder schwarz Gilt zu Beginn, da 1. neuer Knoten z zunächst auf rot gesetzt wird, 2. Wurzel im Baum zu Beginn schwarz ist, 3. „Schwarzhöhen“-Regel und „Rot-oder-Schwarz“-Regel von neuem roten Knoten z nicht verletzt wird, und alle anderen Knoten „Nicht-Rot-Rot“-Regel erfüllen Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 26  … 4 IF y!=nil AND y.color==red THEN Aufräumen: Schleifeninvariante 5 (II) z.parent.color=black; y!=nil&y.color==red 6 y.color=black; 7 z.parent.parent.color=red; Schleifeninvariante: 8 z=z.parent.parent; … 1. z.color==red 2. Wenn z.parent Wurzel, dann z.parent.color==black 3. Wenn der aktuelle Baum kein Rot-Schwarz-Baum ist, dann weil z als Wurzel die Farbe rot hat, oder weil „Nicht-Rot-Rot-Regel“ für z,z.parent verletzt ist. 1. znew wird 17 17 wieder rot (7/8) 2. Farbe von 9 20 9 20 znew znew.parent ändert sich nicht 19 22 19 22 3. Schwarzhöhen- Regel bleibt erhalten y y und nur znew wird rot z 18 18 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 27  9 ELSE 10 IF z==z.parent.right THEN Aufräumen: Schleifeninvariante 11 (III) z=z.parent; y==nil|y.color==black12 rotateLeft(T,z); 13 z.parent.color=black; Schleifeninvariante: 14 z.parent.parent.color=red; 15 rotateRight(T,z.parent.parent); 1. z.color==red 2. Wenn z.parent Wurzel, dann z.parent.color==black 3. Wenn der aktuelle Baum kein Rot-Schwarz-Baum ist, dann weil z als Wurzel die Farbe rot hat, oder weil „Nicht-Rot-Rot-Regel“ für z,z.parent verletzt ist. z 20 23 17 20 z=znew 9 20 z 10-12 17 22 19 22 9 19 18 18 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 28  9 ELSE 10 IF z==z.parent.right THEN Aufräumen: Schleifeninvariante 11 (IIV) z=z.parent; y==nil|y.color==black12 rotateLeft(T,z); 13 z.parent.color=black; Schleifeninvariante: 14 z.parent.parent.color=red; 15 rotateRight(T,z.parent.parent); 1. z.color==red 2. Wenn z.parent Wurzel, dann z.parent.color==black 3. Wenn der aktuelle Baum kein Rot-Schwarz-Baum ist, dann weil z als Wurzel die Farbe rot hat, oder weil „Nicht-Rot-Rot-Regel“ für z,z.parent verletzt ist. 23 1. znew wird wieder rot, da 20 20 z.parent.color==red znew znew in WHILE-Schleife 17 22 17 23 2. Farbe von znew.parent wegen 13 schwarz 9 19 13-15 9 19 22 3. SH-Regel erhalten und neues rotes znew wird Kind schwarzes Knotens 18 18 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 29 Aufräumen: Terminierung Terminierung  Korrektheit Schleifeninvariante: 1. z.color==red 2. Wenn z.parent Wurzel, dann z.parent.color==black 3. Wenn der aktuelle Baum kein Rot-Schwarz-Baum ist, dann weil z als Wurzel die Farbe rot hat, oder weil „Nicht-Rot-Rot-Regel“ für z,z.parent verletzt ist. fixColorsAfterInsertion(T,z) 1 WHILE z.parent.color==red DO … 18 T.root.color=black; Wenn WHILE-Schleife terminiert, dann weil z.parent.color==black. Wenn kein RB-Baum, dann wäre z als Wurzel rot, aber 18 setzt schwarz (und dies kann andere Rot-Schwarz-Baum-Bedingungen nicht verletzen). Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 30  fixColorsAfterInsertion(T,z) Aufräumen: Laufzeit 1 WHILE z.parent.color==red DO 2 IF z.parent==z.parent.parent.left THEN Entweder z geht 3 y=z.parent.parent.right; zwei Level nach oben, 4 IF y!=nil AND y.color==red THEN oder WHILE-Schleife 5 z.parent.color=black; terminiert 6 y.color=black; 7 z.parent.parent.color=red; 8 z=z.parent.parent; maximal 𝑂(ℎ) 9 ELSE viele Iterationen 10 IF z==z.parent.right THEN mit jeweils konstanter 11 z=z.parent; Laufzeit 12 rotateLeft(T,z); 13 z.parent.color=black; 14 z.parent.parent.color=red; 15𝑛) Laufzeit = 𝑂 ℎ = 𝑂(log rotateRight(T,z.parent.parent); 16 ELSE 17 … //exchange left and right 18 T.root.color=black; Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 31 Löschen analog zum binären Suchbaum, aber: Fixup oder oder y erbt die z Farbe von z y l r l r … … s Y s Wenn y schwarz y war, müssen Farben angepasst werden y rot dagegen nil L R L R Y einfach zu lösen! Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 32  Löschen: Fixup bei y.color==black In jedem Knoten: Δ 𝑆𝐻 = SH(linker Teilbaum)−SH(rechter Teilbaum) a Δ 𝑆𝐻 = −1 Beispiel: (rechtslastige) Δ 𝑆𝐻 = 0 Ungleichheit in Knoten a fixen. Δ 𝑆𝐻 = 0 x b Anderer Fall Δ𝑆𝐻 = +1 analog. Fallunterscheidung nach L R Farbkombination der Knoten. Beachte: Beim Löschen kann SH in Knoten nur sinken, also war Wenn x rot, dann schwarz setzen; ursprüngliche SH in a um 1 höher daher nur Fall x schwarz zu betrachten. Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 33 Löschen: Fixup Fallunterscheidung Algorithmen im Anhang oder Fall I: a schwarz, b rot Δ 𝑆𝐻 = −1 a Fall IIa: a rot, b schwarz, c,d nicht rot Fall IIb: a schwarz, b schwarz, x b c,d nicht rot Fall III: a beliebig, b schwarz, c rot, d nicht rot L R c d Fall IV: a beliebig, b schwarz, c beliebig, d rot x==nil zulässig A B C D nicht rot = schwarz oder nil Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 34  wird zu Fall IIa, III oder IV; Löschen: Fixup (Fall I) nie zu Fall IIb oder oder Δ 𝑆𝐻 = −1 a b Δ 𝑆𝐻 = −1 a und b tauschen x b a Farben d gleiche SH gleiche L R c d x SH c C D A B C D L R A B Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 35  Wenn a rot, dann auf schwarz setzen Löschen: Fixup (Fall IIa) und damit ursprüngliche SH erreicht oder oder Δ 𝑆𝐻 = −1 Δ 𝑆𝐻 = 0 a a x b x b gleiche SH gleiche SH L R c d L R c d A B C D A B C D Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 36  Wenn a schwarz, dann Vaterknoten Δ 𝑆𝐻 = ±1; Löschen: Fixup (Fall IIb) verfahre rekursiv mit a als neuem x oder oder Δ 𝑆𝐻 = −1 Δ 𝑆𝐻 = 0 a a x b x b gleiche SH gleiche SH L R c d L R c d A B C D A B C D Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 37 Löschen: Fixup (Fall III) wird zu Fall IV oder oder Δ 𝑆𝐻 = −1 Δ 𝑆𝐻 = −1 a a c und b gleiche SH gleiche SH x b x c tauschen Farben b L R c d L R d A B C D A B C D Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 38 Löschen: Fixup (Fall IV) ursprüngliche oder oder SH wie zuvor Δ 𝑆𝐻 = −1 a erbt Farbe von a b Δ 𝑆𝐻 = 0 Δ 𝑆𝐻 = 0 gleiche SH x b a gleiche SH d L R c d x c C D A B C D L R A B Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 39 Löschen: Laufzeiten y suchen hat (wie beim binären Suchbaum) Laufzeit 𝑂 ℎ = 𝑂(log 𝑛) Fixup geht nur in Fall IIb in Rekursion, dann aber einen Level höher (In Fall I wird a zwar einen Level tiefer rotiert, aber dann bricht Rekursion nach Fällen IIa, III oder IV danach ab) In jeder Rekursion konstante Laufzeit, also Gesamtlaufzeit 𝑂 ℎ = 𝑂(log 𝑛) Gesamtlaufzeit Löschen= 𝑂 ℎ = 𝑂(log 𝑛) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 40 Worst-Case-Laufzeiten Rot-Schwarz-Bäume Operation Laufzeit Einfügen (log n) Löschen (log n) Suchen (log n) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 41  Wie vereinigen Sie zwei Rot-Schwarz-Bäume T0 und T1 mit gleicher Schwarzhöhe, wenn x0.key z.key THEN 5 x=x.left 6 ELSE 7 x=x.right; 8 z.parent=px; 9 IF px==T.sent THEN 10 T.root=z 11 ELSE 12 IF px.key > z.key THEN 13 px.left=z 14 ELSE Änderung: 15 px.right=z; 16 fixBalanceAfterInsertion(T,z); evtl. Rebalancieren Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 56 Einfügen: Beispiel −𝟐 −1 23 23 0 0 0 −1 insert(T,11) 17 34 17 34 0 0 +1 0 9 22 9 22 0 11 erfordert Rebalancieren, evtl. weiter oben im Baum Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 57 Rebalancieren: Fall I oder oder x 𝑩(𝒙) = +𝟐 y 𝑩 𝒚 ≤𝟏 A y x z rotateLeft(T,x) 𝑩 𝒛 ≤𝟏 B z D ⋱ A B C C D Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 58 Rebalancieren: Fall I (Analyse I) oder oder x 𝑩(𝒙) = +𝟐 𝑩(𝒚) = 𝟎 y 𝑩(𝒛) ≤ 𝟏 𝑩 𝒚 ≤𝟏 𝑩(𝒙) ≤ 𝟏 A y x z rotateLeft(T,x) 𝑩 𝒛 ≤𝟏 B z D ⋱ A B C für die Höhen der Teilbäume gilt: C D ℎ𝐶 , ℎ𝐷 ≤ ℎ𝐵 ≤ ℎ𝐴 , wegen AVL ℎ𝐶 ≤ ℎ𝐷 , da sonst kein Höhenzuwachs in z ℎ𝐷 = ℎ𝐴 − 1, da nur dann 𝐵(𝑥) = +2 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 59 Rebalancieren: Fall I (Analyse II) oder oder x 𝑩(𝒙) = +𝟐 𝑩(𝒚) = 𝟎 y 𝑩(𝒛) ≤ 𝟏 𝑩 𝒚 ≤𝟏 𝑩(𝒙) ≤ 𝟏 A y x z rotateLeft(T,x) 𝑩 𝒛 ≤𝟏 B z D ⋱ A B C Im neuen Baum gilt damit: ℎ𝐶 , ℎ𝐷 ≤ ℎ𝐵 ≤ ℎ𝐴 C D ℎ𝐴 − 1 ≤ ℎ𝐵 ≤ ℎ𝐴 ℎ𝐶 ≤ ℎ𝐷 ℎ𝐷 = ℎ𝐴 − 1 ℎ𝑧 = ℎ𝐷 + 2 = ℎ𝐴 + 1 ℎ𝑥 = ℎ𝐴 + 1 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 60 Rebalancieren: Fall I (Analyse III) oder oder x 𝑩(𝒙) = +𝟐 𝑩(𝒚) = 𝟎 y 𝑩(𝒛) ≤ 𝟏 𝑩 𝒚 ≤𝟏 𝑩(𝒙) ≤ 𝟏 A y x z rotateLeft(T,x) 𝑩 𝒛 ≤𝟏 B z D ⋱ A B C Höhe(nach Einfügen und Rotation) C D = Höhe(vor Einfügen) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 61 Rebalancieren: Fall II (erste Rotation) oder oder x 𝑩(𝒙) = +𝟐 x 𝑩 𝒚 ≤𝟏 A y A z rotateRight(T,y) 𝑩 𝒛 ≤𝟏 z B C y ⋰ ℎ𝐶 , ℎ𝐷 ≤ ℎ𝐵 ≤ ℎ𝐴 C D D B ℎ𝐶 ≤ ℎ𝐷 ℎ𝐷 = ℎ𝐴 − 1 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 62  Höhe auch hier unverändert Rebalancieren: Fall II (zweite Rotation) oder oder x 𝑩(𝒛) = 𝟎 z 𝑩(𝒚) ≤ 𝟏 𝑩(𝒙) ≤ 𝟏 A z x y rotateLeft(T,x) C y B A C D Im neuen Baum gilt damit: ℎ𝐶 , ℎ𝐷 ≤ ℎ𝐵 ≤ ℎ𝐴 D B ℎ𝐴 − 1 ≤ ℎ𝐶 ≤ ℎ𝐴 ℎ𝐶 ≤ ℎ𝐷 ℎ𝐷 = ℎ𝐴 − 1 ℎ𝑦 = ℎ𝐷 + 2 = ℎ𝐴 + 1 ℎ𝑥 = ℎ𝐴 + 1 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 63 Rebalancieren: Fälle III+IV oder x 𝑩 𝒙 = −𝟐 x 𝑩 𝒙 = −𝟐 y A y A analog mit analog mit Rechts-Rotation Links-Rotation z B z B und dann Rechts-Rotation C D C D Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 64 Einfügen: Laufzeit insert(T,z) //z.left==z.right==nil; Gesamtlaufzeit 𝑂 ℎ = 𝑂(log 𝑛) 1 x=T.root; px=T.sent; 2 WHILE x != nil DO 3 px=x; Laufzeit = 𝑂(ℎ) 4 IF x.key > z.key THEN 5 x=x.left 6 ELSE 7 x=x.right; 8 z.parent=px; 9 IF px==T.sent THEN Laufzeit = 𝑂(ℎ), 10 T.root=z 11 ELSE da Suche nach 12 IF px.key > z.key THEN unbalanciertem Knoten 13 px.left=z Richtung Wurzel in 𝑂(ℎ), 14 ELSE und Rebalancieren 15 px.right=z; nur einmal nötig 16 fixBalanceAfterInsertion(T,z); Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 65 Löschen analog zum binären Suchbaum, aber: oder oder Rebalancierung Laufzeit 𝑂 ℎ = 𝑂(log 𝑛) evtl. bis hinauf z y in die Wurzel notwendig l r l r … … s Y s y nil L R L R Y Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 66 Worst-Case-Laufzeiten AVL-Bäume Operation Laufzeit Einfügen (log n) Löschen (log n) Suchen (log n) AVL-Bäume bessere (theoretische) Konstanten als Rot-Schwarz-Bäume, je nach Daten und Operationen aber in der Praxis nur unwesentlich schneller Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 67  Splay-Bäume (selbst-organisierende Datenstrukturen) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 68 Selbst-Organisierende Listen Ansatz: einmal angefragte Werte werden voraussichtlich noch öfter angefragt head search(L,37) 5 12 37 47 nach vorne verschieben head 37 5 12 47 bekannte Variante für Bäume: Splay Trees Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 69 Anwendung: SQUID SQUID: Web-Cache-Proxy Quelle: www.squid-cache.org/ Speichert Access Control Listen (ACL) für http-Zugriffe als Splay-Tree 2018/03/17 18:29:45| WARNING: (B) '127.0.0.1' is a subnetwork of (A) '127.0.0.1' 2018/03/17 18:29:45| WARNING: because of this '127.0.0.1' is ignored to keep splay tree searching predictable 2018/03/17 18:29:45| WARNING: You should probably remove '127.0.0.1’ from the ACL named 'localhost' Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 70 Splay-Operation Splay-Bäume bilden Untermenge der BST r z Suchen oder Einfügen A B L R Spüle gesuchten oder neu eingefügten Knoten an die Wurzel splay(T,z)= Folge von Zig-, Zig-Zig- und Zig-Zag-Operationen Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 71 Zig-Zag-Operation =Rechts-Links- oder Links-Rechts-Rotation oder oder x z 2 zigZag(T,z) A y x y 1 z D A B C D B C Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 72 Zig-Zig-Operation =Links-Links- oder Rechts-Rechts-Rotation oder oder x z 1 zigZig(T,z) A y y D 2 z x B C C D A B Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 73 Zig-Operation =einfache Links- oder Rechts-Rotation r z 1 zig(T,z) B z r D C D B C (Falls z direkt unter der Wurzel hängt) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 74  Splay-Operation Gesamtlaufzeit 𝑂 ℎ splay(T,z) 1 WHILE z != T.root DO Laufzeit: 2 IF z.parent.parent==nil THEN Bei jeder Iteration 3 zig(T,z); wird z mindestens 4 ELSE einen Level 5 IF z==z.parent.parent.left.left OR nach oben rotiert z==z.parent.parent.right.right THEN 6 zigZig(T,z); 7 ELSE zigZig(T,z) 8 zigZag(T,z); 1 IF z==z.parent.left THEN 2 rotateRight(T,z.parent.parent); 3 rotateRight(T,z.parent); 4 ELSE 5 rotateLeft(T,z.parent.parent); zig und 6 rotateLeft(T,z.parent); zigZag analog Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 75 Beispiel (I) splay(T,→6) 8 8 7 7 3 3 zigZig 4 6 5 5 6 4 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 76 Beispiel (II) splay(T,→6) 8 8 7 6 3 3 7 zigZag 6 5 5 4 4 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 77 Beispiel (III) splay(T,→6) 8 6 6 3 8 3 7 5 7 zig 5 4 4 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 78 Suchen search(T,k) 1 x=T.root; 2 WHILE x != nil AND x.key != k DO 3 IF x.key < k THEN Laufzeit 𝑂 ℎ 4 x=x.right 5 ELSE Alternativ: „splaye“ dann 6 x=x.left; letzten besuchten Knoten bei erfolgloser Suche 7 IF x==nil THEN nach oben 8 return nil 9 ELSE 10 splay(T,x); 11 return T.root; Laufzeit 𝑂 ℎ Gesamtlaufzeit 𝑂 ℎ Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 79 Einfügen 1. Suche analog zum Einfügen bei BST Einfügepunkt 2. Spüle eingefügten Knoten x per Splay-Operation nach oben r x Splay A B L R Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 80 Beispiel insert(T,2) 2 1 6 3 3 8 6 3 2 5 7 splay(T,2) 5 8 2 4 4 7 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 81 Einfügen: Laufzeit 1. Position im BST suchen 𝑂(ℎ) 2. splay(T,x) 𝑂(ℎ) Gesamtlaufzeit 𝑂 ℎ Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 82 Löschen (I) 1. Spüle gesuchten Knoten x per Splay-Operation nach oben r x Splay A B L R 2. Lösche x Wenn einer der beiden L R Teilbäume leer, dann fertig Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 83 Löschen (II) 3. Spüle den „größten“ Knoten y in L per Splay-Operation nach oben Splay y L R L* R y kann keinen rechtes Kind 4. Hänge R an y an y haben, da größter Wert in L L* R Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 84 Beispiel delete(T,5) 4 3 4 3 splay(L,4) 3 5 2 6 3 6 1 5 8 4 8 splay(T,5) 4 7 7 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 85 Löschen: Laufzeit 1. splay(T,x) 𝑂(ℎ) 2. x löschen 𝑂(1) 3. Max-Knoten y in L bestimmen und splay(L,y) 𝑂 ℎ + 𝑂 ℎ = 𝑂(ℎ) 4. Anhängen 𝑂(1) Gesamtlaufzeit 𝑂 ℎ Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 86 Laufzeit Splay-Bäume Amortisierte Laufzeit: Laufzeit pro Operation über mehrere Operationen hinweg Operationen: Suchen, Löschen, Einfügen Für 𝑚 ≥ 𝑛 Operationen auf einem Splay-Baum mit maximal 𝑛 Knoten ist die Worst-Case-Laufzeit 𝑂(𝑚 ∙ log 2 𝑛), also 𝑂(log 2 𝑛) pro Operation. Zusätzlich: Oft gesuchte Elemente werden sehr schnell gefunden Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 87  Ändern Sie den Algorithmus zur Suche bei Splay-Bäumen so ab, dass auch bei erfolgloser Suche der letzte besuchte Knoten nach oben gespült wird. Könnte man statt des Maximums in L beim Löschen auch das Minimum in R nehmen? Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 88  (Binäre Max-)Heaps Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 89 Binärer Max-Heap Achtung: Heaps sind keine BSTs, 17 linke Kinder können größere Werte als rechte Kinder 14 8 haben! 9 6 7 1 4 3 2 Ein binärer Max-Heap ist ein binärer Baum, der (1) „bis auf das unterste Level vollständig und im Bei Min-Heaps untersten Level von links gefüllt ist“ und sind die Werte in Elternknoten (2) Für alle Knoten x ≠ T.root gilt: jeweils kleiner x.parent.key ≥ x.key Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 90 Ein Haufen Eigenschaften 17 14 8 Da Baum (fast) vollständig, gilt 9 6 7 1 h ≤ log 𝑛 4 3 2 Maximum des Heaps steht in der Wurzel Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 91  Heaps durch Arrays speichere Anzahl 0 17 Knoten in H.size (leerer Heap H.size==0) 1 14 2 8 Duale Sichtweise als Pointer 3 9 4 6 7 5 6 1 oder als Array: 𝑗 j.parent = −1 2 7 4 8 3 2 9 j.left = 2 j + 1 − 1 j.right = 2 j + 1 0 1 2 3 4 5 6 7 8 9 17 14 8 9 6 7 1 4 3 2 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 92 Einfügen 17 14 8 9 6 7 1 4 3 2 11 Vertausche nach oben, bis Max-Eigenschaft wieder erfüllt Position durch Baumstruktur vorgegeben Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 93 Einfügen: Algorithmus 17 14 8 9 11 7 1 Laufzeit 𝑂 ℎ = 𝑂(log 𝑛) insert(H,k) //als (unbeschränktes) Vertausche nach oben, Array 4 3 2 11 bis Max-Eigenschaft wieder erfüllt 1 H.size=H.size+1; 2 H.A[H.size-1]=k; Position durch 3 i=H.size-1; Baumstruktur 4 WHILE i>0 AND H.A[i] > H.A[i.parent] vorgegeben 5 SWAP(H.A,i,i.parent); 6 i=i.parent; Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 94 Lösche Maximum 17 14 8 9 11 7 1 4 3 2 6 1. Ersetze Maximum durch „letztes“ Blatt 2. Stelle Max-Eigenschaften wieder her, indem Knoten nach unten gegen das Maximum der beiden Kinder getauscht wird (heapify) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 04 Fortgeschrittene Datenstrukturen | 95  extract-max(H) //als (unbeschränktes) Array Lösche Max: Algorithmen 1 IF isEmpty(H) THEN 17 2 return error ‘underflow‘ 3 ELSE 4 max=H.A; 14 8 5 H.A=H.A[H.size-1]; 6 H.size=H.size-1; 7 heapify(H,0); Laufzeit 𝑂 ℎ = 𝑂(log 𝑛) 9 8 7 6 return max; 1 heapify(H,i) //als (unbeschränktes) Array 1 4 maxind=i; 3 2 11 2 IF i.left