Kapitel-6-BSuchB

6 Binäre Suchbäume6.1 Definition Knotenmarkierte Bäume Sei T ein binärer Baum und KT die Knotenmenge von T. Eine Knotenmarkierung ist eine Abbildung : KT  D für irgendeinen geordneten Wertebereich D.6.2 Definition Binärer Suchbaum Ein knotenmarkierter binärer Baum T heißt ein binärer Suchbaum, gdw. für jeden Teilbaum T’ von T mit T’ = (Tl, x, Tr) gilt: y Tl: (y) < (x) und z Tr: (z) > (x)Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 1

In Worten:Für jeden Knoten x in T muss gelten: Alle Marken mi von Knoten yi im linken Teilbaum unter x in T sind kleiner als die Marke von x und alle Marken mj von Knoten zj im rechten Teilbaum unter x sind größer als die Marke von x.6.3 Beispiel Monatsnamen in einem binären Suchbaum. Ordnung: „lexikografische Ordnung“ Beim Einfügen in der jährlichen Reihenfolge entsteht folgender Suchbaum: Jan Feb MarApr Mai SepAug Jun OktDez Jul NovAlgorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 2

6.4 Implementierung der Dictionary-OperationenDeklaration der Baumstruktur:class suchBaum {         private Node root;            // Wurzelknoten     // Konstruktor und Methoden der Klasse suchBaum     … } class Node  // Schlüsselwert   {     public int key;  // Referenz auf linken Sohn       public Node left;  // Referenz auf rechten Sohn      public Node right; }  Definition der Dictionary-Operationenz.B. member: member gibt an, ob ein Schlüssel key im Baum t enthalten ist.public boolean member(int value)   {   Node elem = root;                 if (elem == null)                   return false;                 else                   if (elem.key == value)                     return true;                   else                     if (elem.key > value)                       return leftTree().member(value);                     else                       return rightTree().member(value);    }Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 3

Insert: Fügt Element wert als Schlüssel in den Baum t ein.Sprachliche Beschreibung für insert (wert): Suche nach x in t; Falls x bereits in t: Fertig. Falls x nicht in t Sei k der Knoten, bei dem member erfolglos endete, d.h. k.left = = NULL, falls wert < k.key oder k.right = = NULL, falls wert > k.key. Erzeuge einen neuen Knoten k’ für wert. Setze k’.key = wert; Setze k’.left = k’.right = NULL; Falls wert < k.key Setze k.left = k’ Sonst Setze k.right = k’;Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 4

Delete: ist komplexer als member und insert, da auch innere Knoten entfernt werden können.  die Suchbaumstruktur muss erhalten bleiben!Fallbetrachtungen für die Löschoperation:i) Löschen eines Blatts: k soll gelöscht werdenIst das zu löschende Blatt linker Sohn des inneren Knotens k: Setze k.left = NULL;Ist das Blatt rechter Sohn des inneren Knotens k: Setze k.right = NULL;Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 5

ii) Löschen eines inneren Knotens mit nur einem Sohn: k Soll gelöscht werden ‐ der zu löschende innere Knoten ist linker Knoten von k und hat nur einen linken Teilbaum Setze: k.left = k.left.left;Analog: ‐ der zu löschende innere Knoten ist linker Knoten von k und hat nur einen rechten Teilbaum Setze: k.left = k.left.right;Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 6

iii) Löschen eines inneren Knotens mit zwei Söhnen: k Soll gelöscht werdenLöschen geschieht in zwei Schritten: - Ersetze den Schlüssel des Knotens k durch den größten Schlüssel x im linken Teilbaum unter k oder den kleinsten Schlüssel x im rechten Teilbaum unter k. - Lösche den Knoten, der x enthält, aus dem entsprechenden Teilbaum (x ist immer Blatt oder innerer Knoten mit nur einem Sohn!).Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 7

6.5 Beispiel: „Zur Vorbereitung einer Serie über Persönlichkeiten des 20. Jahrhunderts wurden folgende Namen genannt:“ ChurchillBrandt Honecker Mandela Kennedy Rabin LiebknechtHoneckers Beitrag wird gestrichen; sein Eintrag wird alsogelöscht: ChurchillBrandt Mandela Kennedy Rabin LiebknechtAlgorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 8

Nach Ausstrahlung des Beitrags über Churchill wird dessenEintrag ebenfalls gestrichen:Schritt 1: Das Minimum des rechten Teilbaums wird an die Wurzel geschrieben. KennedyBrandt Mandela Kennedy Rabin LiebknechtSchritt 2: Das Minimum wird aus dem rechten Teilbaum gelöscht. KennedyBrandt Mandela Liebknecht RabinAlgorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 9

6.6 Komplexität der Operationen Alle Operationen insert und delete verlaufen analog zur Operation member. delete und insert benötigen zusätzlich maximal noch einmal den gleichen Aufwand, um die Adresse des Vorgängerknotens zu bestimmen, bzw. um das Minimum (bzw. Maximum) im darunter liegenden rechten (bzw. linken) Teilbaum zu suchen. Die Komplexität für alle diese Operationen ist damit gleich der Komplexität der member-Operation.Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 10

 Die member-Operation arbeitet rekursiv den Baum ab: Bei jedem Aufruf verringert sich die Höhe des Teilbaumes, für den sie aufgerufen wird. Damit kann sie maximal „Länge des längsten Pfades-mal“ aufgerufen werden, bis ein Ergebnis berechnet wird. Die mittlere Pfadlänge beim Aufbau eines binären Such- baums mit n Knoten ist O(log n). Die mittlere (d.h. die durchschnittliche) Komplexität der Dictionary Operationen für den binären Suchbaum ist somit O(log n). Dabei setzt man voraus, dass alle möglichen Eingabe- permutationen gleichverteilt sind.Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 11

 Der durchschnittliche Aufwand für den Aufbau eines binären Suchbaums mit n Elementen ist damit O( n log n ). Die worst-case Komplexität für den Aufbau des Suchbaums ist O(n2). Beispiel:Brandt Churchill Honecke Kennedy„Degenerierter Liebknecht Suchbaum“ Mandela RabinAlgorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 12

6.7 AVL - Bäumesind benannt nach Adelson-Velskii und Landis (1962).AVL-Bäume sind höhenbalancierte Bäume.6.7.1 Definition AVL-Bäume Ein AVL-Baum ist  ein binärer Suchbaum,  bei dem für jeden Knoten x gilt: Die Höhen des linken und des rechten Teilbaumes unter x unterscheiden sich maximal um 1.Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 13

6.7.2 Beispiele: AVL-Bäume der Höhe 0: 1: 2:Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 14

6.7.3 Die Operation Insert und DeleteErhalten der Balancierung eines AVL-Baumes durch „Rebalancieren“.Dazu:Jeder Knoten x erhält einen Balancefaktor bal(x): bal(x): = Höhe des rechten Teilbaums unter x - Höhe des linken Teilbaums unter x.In einem AVL-Baum T gilt: Für jeden Knoten x KT ist bal(x)  {-1, 0, +1}Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 15

Beispiel: Aufbau eines AVL-Baums für die Monatsnamen: Jan +1 -1 Feb Mar -20 Apr Mai -1 Jun 0Rotation Jan 0  -1 Feb Mai 00 Apr 0 Jun Mar 0Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 16

Jan 0 -2 Feb Mai -1+1 Apr -1 Jun Mar 0 0 Aug 0 JulDoppelrotation  Jan +1 0 Aug Mai -10 Apr 0 Feb -1 Jun Mar 0 0 JulAlgorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 17

Jan +2 0 Aug Mai +10 Apr 0 Feb -1 Jun Mar +2 0 Jul -1 Sep 0 OktDoppelrotation Jan +1  0 Aug Mai 0Apr 0 Feb -1 Jun Okt 00 0 Jul Mar Sep 00Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 18

Jan +2 0 Aug Mai +1Apr 0 Feb -1 Jun Okt -10 0 Jul +1 Mar Sep 0Rotation 0 Nov  Mai 0 Jan 0 Okt -1 0 Aug -1 Jun +1 Sep 0 0 Jul0 MarApr 0 Feb 0 NovAlgorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 19

Mai -1 Jan -1 Okt -1 +1 Aug -1 Jun +1 Sep 0 0 Jul0 MarApr -1 Feb 0 Nov0 DezAlgorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 20

Diskussion der Rebalancierungsoperationen:1. Balancierung nach einer Insert - OperationSei x der tiefste Knoten im Baum, für den die AVL-Eigen-schaft nach dem Einfügen eines neuen Elements verletzt ist.Fall 1: bal(x) = +2 bal(y) = +1, für den rechten Sohn y von xx +2 y0 Rotation y +1 xA AB C BC Wurde eingefügtAlgorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 21

Fall 2: bal(x) = +2 bal(y) = -1, für den rechten Sohn y von xx +2 Rotation y -2 y -1 xA BC B C A !In diesem Fall führt die Rotation nicht zu einerRebalancierung!Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 22

Stattdessen: Betrachte Teilbaum B genauer. x +2 -1 -1 y zA C B1 B2Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 23

Lösung: Doppelrotation „rechts - links“:1. Rotation um y: +1 z x +2 y A B1 B2 C2. Rotation um z: z0x +1 y B1 B2 CAAlgorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 24

Zweite Möglichkeit für die Gestalt des Teilbaums B: x +2 -1 y +1 zAC B1 B2Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 25

Lösung wie zuvor: Doppelrotation „rechts - links“:1. Rotation um y und2. Rotation um z: z0-1 0 x y B1 B2 CAFazit:Nach einer insert - Operation genügt höchstens  eine Rotation oder  eine Doppelrotationum die Balance im AVL-Baum wiederherzustellen!Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 26

2. Balancierung nach einer Delete – OperationSei x der tiefste Knoten im Baum, für den die AVL-Eigen-schaft nach dem Löschen eines neuen Elements verletzt ist.Fall 1 und 2: bal(x) = +2 Fall 1: bal(y) = 0 oder Fall 2: bal(y) = +1 für rechten Sohn y von xx +2 y -1 y0 +1 Rotation xA B1 C C A B1 B2 B2 Wurde gelöschtB2 Ist im Fall 1 vorhanden, im Fall 2 nichtFür den Teilbaum wird die Balance durch eine Rotationerreicht.Ist B2 nicht vorhanden (also im Fall 2), dann hat sich dieHöhe des Teilbaums um 1 verringert.Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 27

Fall 3: bal(x) = +2 bal(y) = -1 für den rechten Sohn y von xFall 3.1: bal(z) = -1 für den linken Sohn z von y +2 -1 x y -1 zA B1 B2 C Wurde gelöschtAlgorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 28

Lösung wie beim Einfügen: Doppelrotation „rechts - links“: z0 +1 xy B1 B2 CADie Höhe des Teilbaums hat sich um 1 verringert.Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 29

Fall 3.2: bal(x) = +2 bal(y) = -1 bal(z) = 0 für den rechten Sohn y von x für den linken Sohn z von y +2 -1 x y 0 z A B1 B2 C Wurde gelöschtLösung: Doppelrotation „rechts - links“: z0 0 xyA B1 B2 CDie Höhe des Teilbaums hat sich um 1 verringert.Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 30

Fall 3.3: bal(x) = +2 bal(y) = -1 bal(z) = +1 für den rechten Sohn y von x für den linken Sohn z von y +2 -1 x y +1 z AC B1 B2 Wurde gelöschtLösung: Doppelrotation „rechts - links“: z0 0 xyA B1 B2 CDie Höhe des Teilbaums hat sich um 1 verringert.Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 31

Fazit: In den jeweiligen Teilbäumen wird die Balance durch höchstens eine Rotation oder eine Doppelrotation wiederhergestellt. In den Fällen, in denen sich dadurch die Höhe des Teil- baums verringert, müssen auch für die Vorgänger des Knotens x auf dem Weg vom Knoten x zur Wurzel hin Anpassungen vorgenommen werden:  Es muss mindestens der Balancefaktor geändert werden;  Unter Umständen sind dann auch Rebalancierungen für diese Knoten erforderlich.Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 32

Beispiel: Delete (3) 20 10 34 5 14 27 493 12 17 24 31 44 53 16 22 26 33 60 21Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 33

6.7.4 Komplexität der OperationenDie Operationen Delete, Member und Insert hängen von derHöhe h des jeweiligen Baumes ab.Die Komplexität der Operationen ist also O(h).Wie groß ist die maximale Höhe eines AVL-Baumes mit nKnoten?Gesucht: minimale Anzahl der Knoten in einem AVL-Baum der Höhe h.Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 34

 Ein AVL-Baum der Höhe 2 hat mindestens 4 Knoten. Einen AVL-Baum der Höhe h+2 mit minimaler Anzahl von Knoten erhält man, indem man zwei AVL-Bäume mit minimaler Anzahl von Knoten der Höhe h und der Höhe h+1 wie folgt zusammenfügt:Höhe h+1 Höhe h Höhe h+2Sei N(h) die minimale Anzahl von Knoten eines AVL-Baumes der Höhe h, dann gilt: N(h+2) = N(h+1) + N(h) +1, d.h. N(h) = 1 + N(h-1) + N(h-2)und sei Fi die i-te Fibonacci-Zahl  N(h) = Fh+3 -1Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 35

Es gilt: Fh = 1 1 5 )h1  1  5 )h1 ) (*) (( ( 52 2(Beweis: durch Induktion)Der zweite Term in Gleichung (*),(12 5 ) ist vom Betragkleiner als 1 und wird daher mit wachsendem h schnellkleiner.Damit gilt: 1 5 (12 5 )h  0.7236  1.618h Fh  2 * 5In einem AVL-Baum der Höhe h mit N Knoten gilt dann: N > Fh+3  3.065  1.618hDamit ist h  1 log 3.065 log N  2 log 1.618 2 log 1.618 22 h  1.44  log2 NAlgorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 36

6.7.5 Satz Ein AVL-Baum mit n Knoten hat eine Höhe von O(log2 n), genauer, h  1.44  log2 n. Er ist damit um maximal 44 % höher als ein vollständiger binärer Suchbaum. AVL-Bäume realisieren damit die Operationen Insert, Delete und Member in Zeit O(log2 n). Der Platzbedarf ist O(n).AVL-Bäume sind damit ein optimales Verfahren (worst case-effiziente Implementierung) zur Realisierung der Dictionary-Operationen auf binären Bäumen.Algorithmen und Datenstrukturen Binäre Suchbäume Kapitel 6 / 37