Lektion 2.4

Binäre Suchbäume

45 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • Bäume mit den Begriffen Wurzel, Kind, Blatt, Tiefe und Höhe beschreiben,

  • die Suchbaumeigenschaft prüfen und an einem Gegenbeispiel erklären, warum sie global gilt,

  • in einem binären Suchbaum suchen, einfügen und in allen drei Fällen löschen,

  • beweisen, dass der Inorder-Durchlauf die Schlüssel sortiert ausgibt,

  • begründen, warum alle Operationen O(h)O(h) kosten und warum hh bis zu n−1n-1 werden kann.

Vorausgesetzt: Laufzeit messen: Operationen zählen und O-Notation, Rekursion und Rekurrenzgleichungen, Arrays und verkettete Listen, Hashtabellen

Ein Online-Shop verwaltet die Artikelnummern seines Lagers. Ständig kommen Artikel hinzu und fallen weg, und ständig wird gefragt: Ist Nummer 48 21348\,213 da? Welche Nummern liegen zwischen 40 00040\,000 und 50 00050\,000? Welches ist die nächstgrößere Nummer?

Ein sortiertes Array sucht mit binärer Suche in O(log⁡n)O(\log n), verschiebt beim Einfügen aber bis zu nn Einträge. Eine verkettete Liste fügt an bekannter Stelle in O(1)O(1) ein, findet die Stelle aber erst nach O(n)O(n) Schritten. Eine Hashtabelle sucht im Mittel in O(1)O(1), kennt aber keine Reihenfolge, also weder den nächstgrößeren Schlüssel noch Bereiche.

Die Idee: Man legt die binäre Suche selbst als Geflecht von Verweisen ab. Oben steht ein Schlüssel, alles Kleinere hängt links darunter, alles Größere rechts, und darunter geht es nach derselben Regel weiter. Wer sucht, vergleicht und geht nach links oder rechts. Wer einfügt, geht denselben Weg und hängt den neuen Schlüssel dort an, wo der Weg endet.

Vermute zuerst

Du fügst die Schlüssel 1,2,3,4,5,6,71, 2, 3, 4, 5, 6, 7 in dieser Reihenfolge nach der Regel „kleiner nach links, größer nach rechts“ ein. Danach suchst du die 77. Wie viele Schlüssel musst du dabei ansehen?

Definition

Baum, Binärbaum

Ein (gewurzelter) Baum besteht aus Knoten und Kanten. Ein Knoten ist die Wurzel. Jeder andere Knoten hat genau einen Elternknoten, mit dem ihn eine Kante verbindet, und folgt man immer dem Elternknoten, kommt man nach endlich vielen Schritten zur Wurzel. Die Knoten, deren Elternknoten vv ist, heißen Kinder von vv. Ein Knoten ohne Kinder ist ein Blatt, einer mit Kindern ein innerer Knoten. Ein Knoten vv mit allem, was unter ihm hängt, ist der Teilbaum von vv.

  • Die Tiefe eines Knotens ist die Zahl der Kanten auf dem Weg von der Wurzel zu ihm. Die Wurzel hat Tiefe 00.
  • Die Höhe eines Knotens ist die Zahl der Kanten auf dem längsten Weg von ihm hinab zu einem Blatt. Ein Blatt hat Höhe 00.
  • Die Höhe des Baums hh ist die Höhe der Wurzel, also die größte Tiefe, die vorkommt. Für den leeren Baum setzt man h=−1h = -1.

Ein Binärbaum ist entweder leer, oder er besteht aus einer Wurzel, einem linken und einem rechten Teilbaum, die selbst Binärbäume sind. Jeder Knoten hat also höchstens zwei Kinder, und es ist festgelegt, welches links und welches rechts steht. Im Speicher ist ein Knoten ein Objekt mit einem Schlüssel und zwei Verweisen wie bei einer verketteten Liste; ein fehlendes Kind ist der leere Verweis NIL\texttt{NIL}.

Beispiel

Ein Binärbaum als Tabelle

Jede Zeile nennt einen Knoten und seine Kinder; ein Strich heißt: Kind fehlt.

Knotenlinkes Kindrechtes KindTiefeHöhe
831003
31612
1––20
64721
4––30
7––30
10–1412
1413–21
13––30

Kürzer ist die Klammerschreibweise: k(L,R)k(L, R) heißt Knoten kk mit linkem Teilbaum LL und rechtem Teilbaum RR. Der Baum oben ist 8(3(1, 6(4, 7)), 10(–, 14(13, –))).

Die Wurzel ist 88, die Blätter sind 1,4,7,131, 4, 7, 13. Die Höhe des Baums ist 33, denn 44, 77 und 1313 haben Tiefe 33. Die Höhe von 1010 ist 22 (Weg 10,14,1310, 14, 13), obwohl 1010 nur ein Kind hat.

Gegenbeispiel: Hätte 44 zusätzlich eine Kante zu 1010, so hätte 44 zwei Elternknoten, 66 und 1010. Das ist kein Baum: Der Weg nach oben ist nicht eindeutig.

Definition

Binärer Suchbaum

Jeder Knoten trägt einen Schlüssel aus einer total geordneten Menge (zum Beispiel ganze Zahlen); alle Schlüssel sind verschieden. Ein Binärbaum ist ein binärer Suchbaum, wenn für jeden Knoten vv mit Schlüssel kk die Suchbaumeigenschaft gilt:

  • Jeder Schlüssel im linken Teilbaum von vv ist kleiner als kk.
  • Jeder Schlüssel im rechten Teilbaum von vv ist größer als kk.

Der Baum im Beispiel oben ist einer: Links von 88 stehen 1,3,4,6,71, 3, 4, 6, 7, rechts 10,13,1410, 13, 14, und an den anderen Knoten ebenso.

Beispiel

Gegenbeispiel: nur die Kinder geprüft

Der Baum 8(3(–, 9), 10) erfüllt an jedem Knoten die schwächere Bedingung „linkes Kind kleiner, rechtes Kind größer“: 3<8<103 < 8 < 10 und 9>39 > 3. Trotzdem ist er kein binärer Suchbaum. Die 99 liegt im linken Teilbaum der Wurzel 88, ist aber größer als 88.

Wer die 99 sucht, geht an der 88 nach rechts zur 1010, dann links ins Leere und meldet „nicht vorhanden“. Die Bedingung betrifft deshalb ganze Teilbäume, nicht nur Kinder.

Kurz geprüft

Im Beispielbaum 8(3(1, 6(4, 7)), 10(–, 14(13, –))) soll ein neuer Knoten rechtes Kind der 77 werden. Welcher Schlüssel erhält die Suchbaumeigenschaft?

Beispiel

Suchen

Die Suche vergleicht den gesuchten Schlüssel xx mit dem aktuellen Knoten. Ist xx kleiner, kann er wegen der Suchbaumeigenschaft nur links liegen, ist er größer, nur rechts.

ZeileEinrückungAnweisung
10suche(v, x):\texttt{suche(v, x):}
21while v != NIL:\texttt{while v != NIL:}
32if x == v.schluessel: return v\texttt{if x == v.schluessel: return v}
42if x < v.schluessel:\texttt{if x < v.schluessel:}
53v = v.links\texttt{v = v.links}
62else:\texttt{else:}
73v = v.rechts\texttt{v = v.rechts}
81return NIL\texttt{return NIL}

Aufgerufen wird suche(wurzel, x)\texttt{suche(wurzel, x)}. Zwei Suchen im Beispielbaum:

gesuchtbesuchte KnotenErgebnis
78, 3, 6, 7gefunden in Tiefe 3
58, 3, 6, 4nach der 4 geht es rechts ins Leere: nicht vorhanden

Jeder Schleifendurchlauf geht eine Ebene tiefer. Die Suche besucht also höchstens h+1h + 1 Knoten, egal wie groß der Baum ist.

Beispiel

Einfügen

Einfügen heißt: suchen, bis man ins Leere läuft, und dort den neuen Knoten anhängen. Die rekursive Funktion gibt die (eventuell neue) Wurzel des Teilbaums zurück:

ZeileEinrückungAnweisung
10einfuegen(v, x):\texttt{einfuegen(v, x):}
21if v == NIL: return neuerKnoten(x)\texttt{if v == NIL: return neuerKnoten(x)}
31if x < v.schluessel:\texttt{if x < v.schluessel:}
42v.links = einfuegen(v.links, x)\texttt{v.links = einfuegen(v.links, x)}
51else if x > v.schluessel:\texttt{else if x > v.schluessel:}
62v.rechts = einfuegen(v.rechts, x)\texttt{v.rechts = einfuegen(v.rechts, x)}
71return v\texttt{return v}

Ist xx schon vorhanden, ändert sich nichts. Der Beispielbaum entsteht aus der Folge 8,3,10,1,6,14,4,7,138, 3, 10, 1, 6, 14, 4, 7, 13:

eingefügtbesuchte KnotenwirdTiefe
8keineWurzel0
38linkes Kind von 81
108rechtes Kind von 81
18, 3linkes Kind von 32
68, 3rechtes Kind von 32
148, 10rechtes Kind von 102
48, 3, 6linkes Kind von 63
78, 3, 6rechtes Kind von 63
138, 10, 14linkes Kind von 143

Ein neuer Knoten wird immer als Blatt angehängt; die übrigen bleiben, wo sie sind. Die Suchbaumeigenschaft bleibt erhalten, weil der neue Schlüssel bei jedem Vorfahren auf der Seite landet, die der Vergleich verlangt.

Kurz geprüft

Du fügst in den Beispielbaum den Schlüssel 55 ein. Wo landet er?

Satz

Inorder-Durchlauf liefert die sortierte Folge

Der Inorder-Durchlauf besucht erst den linken Teilbaum, dann den Knoten selbst, dann den rechten Teilbaum:

ZeileEinrückungAnweisung
10inorder(v):\texttt{inorder(v):}
21if v == NIL: return\texttt{if v == NIL: return}
31inorder(v.links)\texttt{inorder(v.links)}
41ausgeben(v.schluessel)\texttt{ausgeben(v.schluessel)}
51inorder(v.rechts)\texttt{inorder(v.rechts)}

Satz. Für jeden binären Suchbaum gibt inorder(wurzel)\texttt{inorder(wurzel)} jeden Schlüssel genau einmal aus, und zwar in aufsteigender Reihenfolge. Die Laufzeit ist O(n)O(n) bei nn Knoten.

Im Beispielbaum entsteht 1,3,4,6,7,8,10,13,141, 3, 4, 6, 7, 8, 10, 13, 14.

Kurz geprüft

Welcher Schlüssel folgt in der Inorder-Folge des Beispielbaums direkt auf die 88?

Definition

Nachfolger

Der Nachfolger eines Schlüssels kk ist der kleinste Schlüssel im Baum, der größer als kk ist, also der nächste in der Inorder-Folge. Hat der Knoten von kk einen rechten Teilbaum, so ist der Nachfolger dessen Minimum: Man geht einmal nach rechts und dann so lange nach links, bis es nicht weitergeht.

ZeileEinrückungAnweisung
10minimum(v):\texttt{minimum(v):}
21while v.links != NIL:\texttt{while v.links != NIL:}
32v = v.links\texttt{v = v.links}
41return v\texttt{return v}

Der so gefundene Knoten hat kein linkes Kind, sonst wäre minimum\texttt{minimum} weitergelaufen.

Beispiel

Löschen in drei Fällen

Beim Löschen eines Knotens vv muss der Rest wieder ein binärer Suchbaum sein. Es gibt drei Fälle:

  • Fall 1, vv ist ein Blatt: Man entfernt vv, der Verweis im Elternknoten wird NIL\texttt{NIL}.
  • Fall 2, vv hat genau ein Kind: Das Kind rückt mit seinem ganzen Teilbaum an die Stelle von vv.
  • Fall 3, vv hat zwei Kinder: Man sucht den Nachfolger mm im rechten Teilbaum, schreibt dessen Schlüssel in vv und löscht mm aus dem rechten Teilbaum. Weil mm kein linkes Kind hat, ist das Fall 1 oder Fall 2.
ZeileEinrückungAnweisung
10loesche(v, x):\texttt{loesche(v, x):}
21if v == NIL: return NIL\texttt{if v == NIL: return NIL}
31if x < v.schluessel: v.links = loesche(v.links, x)\texttt{if x < v.schluessel: v.links = loesche(v.links, x)}
41else if x > v.schluessel: v.rechts = loesche(v.rechts, x)\texttt{else if x > v.schluessel: v.rechts = loesche(v.rechts, x)}
51else:\texttt{else:}
62if v.links == NIL: return v.rechts\texttt{if v.links == NIL: return v.rechts}
72if v.rechts == NIL: return v.links\texttt{if v.rechts == NIL: return v.links}
82m = minimum(v.rechts)\texttt{m = minimum(v.rechts)}
92v.schluessel = m.schluessel\texttt{v.schluessel = m.schluessel}
102v.rechts = loesche(v.rechts, m.schluessel)\texttt{v.rechts = loesche(v.rechts, m.schluessel)}
111return v\texttt{return v}

Zeile 6 erledigt Fall 1 und Fall 2 mit rechtem Kind, Zeile 7 Fall 2 mit linkem Kind, Zeilen 8 bis 10 Fall 3. Drei Löschungen nacheinander:

gelöschtFallwas passiertBaum danach
13114 verliert ihr linkes Kind8(3(1, 6(4, 7)), 10(–, 14))
10214 rückt an die Stelle von 108(3(1, 6(4, 7)), 14)
33Nachfolger ist 4; die 4 wird in den Knoten geschrieben, das Blatt 4 gelöscht8(4(1, 6(–, 7)), 14)

Im Fall 3 passt mm an die Stelle von vv: Er ist größer als alles im linken Teilbaum und kleiner als alles, was im rechten bleibt (Übung bst-6). Inorder lautet danach 1,4,6,7,8,141, 4, 6, 7, 8, 14.

Häufige Fehler

Das rechte Kind als Ersatz nehmen

Beim Löschen der 33 aus dem Beispielbaum wird oft der Schlüssel des rechten Kindes als Ersatz genommen: „Die 66 ist größer als die 33 und steht direkt darunter.“ Schreibt man 66 in den Knoten der 33, liegt die 44 aber weiterhin in dessen rechtem Teilbaum, obwohl 4<64 < 6 ist. Die Suchbaumeigenschaft ist verletzt, und eine Suche nach 44 biegt an der neuen 66 nach links ab und findet sie nicht mehr.

Richtig ist

Der Ersatz muss der nächstgrößere Schlüssel sein, also das Minimum des rechten Teilbaums, hier die 44, nicht die 66. Nur dieser Schlüssel passt genau zwischen den linken Teilbaum und den Rest des rechten Teilbaums. Gleichwertig ist der Vorgänger, das Maximum des linken Teilbaums.

Satz

Laufzeit O(h)O(h) und Grenzen für die Höhe

Suchen, Einfügen, Löschen, Minimum und Nachfolger kosten in einem binären Suchbaum der Höhe hh jeweils O(h+1)O(h + 1) Schritte, kurz O(h)O(h). Für die Höhe eines Binärbaums mit n≥1n \ge 1 Knoten gilt

⌈log⁡2(n+1)⌉−1  ≤  h  ≤  n−1\lceil \log_2(n+1) \rceil - 1 \;\le\; h \;\le\; n - 1
Beispiel

Der entartete Baum

Fügst du 1,2,…,n1, 2, \dots, n aufsteigend ein, ist jeder neue Schlüssel größer als alle bisherigen und wird rechtes Kind des zuletzt eingefügten. Der Baum ist eine Kette 1(–, 2(–, 3(–, …))) mit Höhe n−1n - 1, die obere Schranke ist erreicht.

Der kk-te Schlüssel besucht beim Einfügen die k−1k - 1 schon vorhandenen Knoten. Insgesamt sind das

0+1+2+⋯+(n−1)=n(n−1)2∈Θ(n2)0 + 1 + 2 + \dots + (n-1) = \frac{n(n-1)}{2} \in \Theta(n^2)

Für n=7n = 7 sind es 2121 besuchte Knoten, und jede spätere Suche nach 77 besucht 77 statt 33 Knoten. Absteigende Folgen ergeben eine Kette nach links. Fast sortierte Daten, etwa fortlaufende Bestellnummern, sind in der Praxis häufig.

Die beste Höhe für n=7n = 7 ist ⌈log⁡28⌉−1=2\lceil \log_2 8 \rceil - 1 = 2, erreicht von 4(2(1, 3), 6(5, 7)).

Zusammenfassung

  • Tiefe zählt Kanten von der Wurzel, Höhe Kanten bis zum tiefsten Blatt darunter.

  • Suchbaumeigenschaft: Für jeden Knoten ist der ganze linke Teilbaum kleiner, der ganze rechte größer, nicht nur das Kind.

  • Suchen und Einfügen laufen einen Weg nach unten; eingefügt wird als Blatt.

  • Löschen: Blatt entfernen, einziges Kind hochziehen, bei zwei Kindern den Nachfolger einsetzen und dort löschen.

  • Inorder gibt die Schlüssel aufsteigend aus (Induktion über die Knotenzahl).

  • Alle Operationen kosten O(h)O(h), und ⌈log⁡2(n+1)⌉−1≤h≤n−1\lceil \log_2(n+1) \rceil - 1 \le h \le n - 1.

  • Sortierte Einfügefolgen erzeugen eine Kette mit h=n−1h = n - 1 und Gesamtkosten Θ(n2)\Theta(n^2).

Übungen

Aufgabe 1Numerisch

Füge 50,30,70,20,40,60,80,35,45,6550, 30, 70, 20, 40, 60, 80, 35, 45, 65 in dieser Reihenfolge in einen leeren binären Suchbaum ein. Welche Höhe hat der Baum danach?

Aufgabe 2Numerisch

Im Baum aus der vorigen Aufgabe suchst du den Schlüssel 3636. Wie viele Knoten besucht die Suche, bevor sie „nicht vorhanden“ meldet?

Aufgabe 3Multiple Choice

Aus demselben Baum wird die Wurzel 5050 mit der Nachfolger-Regel gelöscht. Welcher Schlüssel steht danach in der Wurzel?

Aufgabe 4Numerisch

Welche Höhe hat ein binärer Suchbaum mit 100100 Schlüsseln mindestens?

Aufgabe 5Numerisch

Die Schlüssel 1,2,31, 2, 3 können in 66 verschiedenen Reihenfolgen eingefügt werden. Bei wie vielen dieser Reihenfolgen hat der entstehende binäre Suchbaum die Höhe 22?

Aufgabe 6Freitext

Beweise, dass Fall 3 des Löschens die Suchbaumeigenschaft erhält: Der Knoten vv mit Schlüssel kk hat zwei Kinder, mm ist das Minimum seines rechten Teilbaums RR, und nach dem Löschen steht der Schlüssel mm in vv, während der Knoten mm aus RR entfernt wurde.

Aufgabe 7Freitext

Man kann nn verschiedene Zahlen sortieren, indem man sie in einen leeren binären Suchbaum einfügt und dann den Inorder-Durchlauf ausgibt. Gib eine Eingabe an, bei der dieses Verfahren Θ(n2)\Theta(n^2) Schritte braucht, und begründe, warum es nie mehr als O(n2)O(n^2) braucht.