Binäre Suchbäume
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 kosten und warum bis zu 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 da? Welche Nummern liegen zwischen und ? Welches ist die nächstgrößere Nummer?
Ein sortiertes Array sucht mit binärer Suche in , verschiebt beim Einfügen aber bis zu Einträge. Eine verkettete Liste fügt an bekannter Stelle in ein, findet die Stelle aber erst nach Schritten. Eine Hashtabelle sucht im Mittel in , 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.
Du fügst die Schlüssel in dieser Reihenfolge nach der Regel „kleiner nach links, größer nach rechts“ ein. Danach suchst du die . Wie viele Schlüssel musst du dabei ansehen?
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 ist, heißen Kinder von . Ein Knoten ohne Kinder ist ein Blatt, einer mit Kindern ein innerer Knoten. Ein Knoten mit allem, was unter ihm hängt, ist der Teilbaum von .
- Die Tiefe eines Knotens ist die Zahl der Kanten auf dem Weg von der Wurzel zu ihm. Die Wurzel hat Tiefe .
- 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 .
- Die Höhe des Baums ist die Höhe der Wurzel, also die größte Tiefe, die vorkommt. Für den leeren Baum setzt man .
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 .
Ein Binärbaum als Tabelle
Ein Binärbaum als Tabelle
Jede Zeile nennt einen Knoten und seine Kinder; ein Strich heißt: Kind fehlt.
| Knoten | linkes Kind | rechtes Kind | Tiefe | Höhe |
|---|---|---|---|---|
| 8 | 3 | 10 | 0 | 3 |
| 3 | 1 | 6 | 1 | 2 |
| 1 | – | – | 2 | 0 |
| 6 | 4 | 7 | 2 | 1 |
| 4 | – | – | 3 | 0 |
| 7 | – | – | 3 | 0 |
| 10 | – | 14 | 1 | 2 |
| 14 | 13 | – | 2 | 1 |
| 13 | – | – | 3 | 0 |
Kürzer ist die Klammerschreibweise: heißt Knoten mit linkem Teilbaum und rechtem Teilbaum . Der Baum oben ist 8(3(1, 6(4, 7)), 10(–, 14(13, –))).
Die Wurzel ist , die Blätter sind . Die Höhe des Baums ist , denn , und haben Tiefe . Die Höhe von ist (Weg ), obwohl nur ein Kind hat.
Gegenbeispiel: Hätte zusätzlich eine Kante zu , so hätte zwei Elternknoten, und . Das ist kein Baum: Der Weg nach oben ist nicht eindeutig.
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 mit Schlüssel die Suchbaumeigenschaft gilt:
- Jeder Schlüssel im linken Teilbaum von ist kleiner als .
- Jeder Schlüssel im rechten Teilbaum von ist größer als .
Der Baum im Beispiel oben ist einer: Links von stehen , rechts , und an den anderen Knoten ebenso.
Gegenbeispiel: nur die Kinder geprüft
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“: und . Trotzdem ist er kein binärer Suchbaum. Die liegt im linken Teilbaum der Wurzel , ist aber größer als .
Wer die sucht, geht an der nach rechts zur , dann links ins Leere und meldet „nicht vorhanden“. Die Bedingung betrifft deshalb ganze Teilbäume, nicht nur Kinder.
Im Beispielbaum 8(3(1, 6(4, 7)), 10(–, 14(13, –))) soll ein neuer Knoten rechtes Kind der werden. Welcher Schlüssel erhält die Suchbaumeigenschaft?
Suchen
Suchen
Die Suche vergleicht den gesuchten Schlüssel mit dem aktuellen Knoten. Ist kleiner, kann er wegen der Suchbaumeigenschaft nur links liegen, ist er größer, nur rechts.
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 2 | |
| 4 | 2 | |
| 5 | 3 | |
| 6 | 2 | |
| 7 | 3 | |
| 8 | 1 |
Aufgerufen wird . Zwei Suchen im Beispielbaum:
| gesucht | besuchte Knoten | Ergebnis |
|---|---|---|
| 7 | 8, 3, 6, 7 | gefunden in Tiefe 3 |
| 5 | 8, 3, 6, 4 | nach der 4 geht es rechts ins Leere: nicht vorhanden |
Jeder Schleifendurchlauf geht eine Ebene tiefer. Die Suche besucht also höchstens Knoten, egal wie groß der Baum ist.
Einfügen
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:
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 1 | |
| 4 | 2 | |
| 5 | 1 | |
| 6 | 2 | |
| 7 | 1 |
Ist schon vorhanden, ändert sich nichts. Der Beispielbaum entsteht aus der Folge :
| eingefügt | besuchte Knoten | wird | Tiefe |
|---|---|---|---|
| 8 | keine | Wurzel | 0 |
| 3 | 8 | linkes Kind von 8 | 1 |
| 10 | 8 | rechtes Kind von 8 | 1 |
| 1 | 8, 3 | linkes Kind von 3 | 2 |
| 6 | 8, 3 | rechtes Kind von 3 | 2 |
| 14 | 8, 10 | rechtes Kind von 10 | 2 |
| 4 | 8, 3, 6 | linkes Kind von 6 | 3 |
| 7 | 8, 3, 6 | rechtes Kind von 6 | 3 |
| 13 | 8, 10, 14 | linkes Kind von 14 | 3 |
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.
Du fügst in den Beispielbaum den Schlüssel ein. Wo landet er?
Inorder-Durchlauf liefert die sortierte Folge
Der Inorder-Durchlauf besucht erst den linken Teilbaum, dann den Knoten selbst, dann den rechten Teilbaum:
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 1 | |
| 4 | 1 | |
| 5 | 1 |
Satz. Für jeden binären Suchbaum gibt jeden Schlüssel genau einmal aus, und zwar in aufsteigender Reihenfolge. Die Laufzeit ist bei Knoten.
Im Beispielbaum entsteht .
Beweisidee: Die Wurzel trennt die kleineren von den größeren Schlüsseln, und für die beiden Teilbäume gilt die Aussage nach Induktionsannahme.
Wir zeigen die Aussage durch starke Induktion über die Zahl der Knoten.
Anfang : Der leere Baum gibt nichts aus. Die leere Folge ist aufsteigend, und es fehlt kein Schlüssel.
Schritt: Sei und die Aussage für alle binären Suchbäume mit weniger als Knoten bewiesen. Die Wurzel habe den Schlüssel , den linken Teilbaum und den rechten Teilbaum . Beide sind selbst binäre Suchbäume (die Bedingung gilt für jeden ihrer Knoten schon im ganzen Baum) mit höchstens Knoten.
Nach Induktionsannahme gibt auf alle Schlüssel von aufsteigend aus. Dann kommt , dann nach Induktionsannahme alle Schlüssel von aufsteigend. Nach der Suchbaumeigenschaft an der Wurzel ist jeder Schlüssel aus kleiner als und jeder aus größer. Die drei Stücke ergeben also zusammen eine aufsteigende Folge. Jeder Schlüssel liegt in genau einem Stück und wird genau einmal ausgegeben.
Laufzeit: Es gibt einen Aufruf je Knoten und einen je leerem Verweis. Von den Verweisen zeigen auf Knoten (alle außer der Wurzel), also sind leer. Das sind Aufrufe mit konstantem Aufwand, also .
Welcher Schlüssel folgt in der Inorder-Folge des Beispielbaums direkt auf die ?
Nachfolger
Der Nachfolger eines Schlüssels ist der kleinste Schlüssel im Baum, der größer als ist, also der nächste in der Inorder-Folge. Hat der Knoten von einen rechten Teilbaum, so ist der Nachfolger dessen Minimum: Man geht einmal nach rechts und dann so lange nach links, bis es nicht weitergeht.
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 2 | |
| 4 | 1 |
Der so gefundene Knoten hat kein linkes Kind, sonst wäre weitergelaufen.
Löschen in drei Fällen
Löschen in drei Fällen
Beim Löschen eines Knotens muss der Rest wieder ein binärer Suchbaum sein. Es gibt drei Fälle:
- Fall 1, ist ein Blatt: Man entfernt , der Verweis im Elternknoten wird .
- Fall 2, hat genau ein Kind: Das Kind rückt mit seinem ganzen Teilbaum an die Stelle von .
- Fall 3, hat zwei Kinder: Man sucht den Nachfolger im rechten Teilbaum, schreibt dessen Schlüssel in und löscht aus dem rechten Teilbaum. Weil kein linkes Kind hat, ist das Fall 1 oder Fall 2.
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 1 | |
| 4 | 1 | |
| 5 | 1 | |
| 6 | 2 | |
| 7 | 2 | |
| 8 | 2 | |
| 9 | 2 | |
| 10 | 2 | |
| 11 | 1 |
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öscht | Fall | was passiert | Baum danach |
|---|---|---|---|
| 13 | 1 | 14 verliert ihr linkes Kind | 8(3(1, 6(4, 7)), 10(–, 14)) |
| 10 | 2 | 14 rückt an die Stelle von 10 | 8(3(1, 6(4, 7)), 14) |
| 3 | 3 | Nachfolger ist 4; die 4 wird in den Knoten geschrieben, das Blatt 4 gelöscht | 8(4(1, 6(–, 7)), 14) |
Im Fall 3 passt an die Stelle von : Er ist größer als alles im linken Teilbaum und kleiner als alles, was im rechten bleibt (Übung bst-6). Inorder lautet danach .
Das rechte Kind als Ersatz nehmen
Das rechte Kind als Ersatz nehmen
Beim Löschen der aus dem Beispielbaum wird oft der Schlüssel des rechten Kindes als Ersatz genommen: „Die ist größer als die und steht direkt darunter.“ Schreibt man in den Knoten der , liegt die aber weiterhin in dessen rechtem Teilbaum, obwohl ist. Die Suchbaumeigenschaft ist verletzt, und eine Suche nach biegt an der neuen nach links ab und findet sie nicht mehr.
Der Ersatz muss der nächstgrößere Schlüssel sein, also das Minimum des rechten Teilbaums, hier die , nicht die . 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.
Laufzeit und Grenzen für die Höhe
Suchen, Einfügen, Löschen, Minimum und Nachfolger kosten in einem binären Suchbaum der Höhe jeweils Schritte, kurz . Für die Höhe eines Binärbaums mit Knoten gilt
Laufzeit: Jede Operation läuft von der Wurzel aus einen Weg nach unten und tut an jedem Knoten nur konstant viel (ein Vergleich, ein Verweis). Ein solcher Weg enthält höchstens Knoten. Beim Löschen im Fall 3 kommen der Weg zu und der zweite Aufruf von im rechten Teilbaum dazu; beide laufen wieder nur abwärts, zusammen also höchstens Knoten. Das ist .
Obere Schranke: Ein Weg von der Wurzel zu einem Knoten der Tiefe besteht aus verschiedenen Knoten, also .
Untere Schranke: In Tiefe liegen höchstens Knoten, denn jeder Knoten hat höchstens zwei Kinder (Induktion über ). Ein Baum der Höhe hat also höchstens Knoten. Aus folgt , und weil ganz ist, auch .
Der entartete Baum
Der entartete Baum
Fügst du 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 , die obere Schranke ist erreicht.
Der -te Schlüssel besucht beim Einfügen die schon vorhandenen Knoten. Insgesamt sind das
Für sind es besuchte Knoten, und jede spätere Suche nach besucht statt 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 ist , 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 , und .
Sortierte Einfügefolgen erzeugen eine Kette mit und Gesamtkosten .
Übungen
Füge in dieser Reihenfolge in einen leeren binären Suchbaum ein. Welche Höhe hat der Baum danach?
Im Baum aus der vorigen Aufgabe suchst du den Schlüssel . Wie viele Knoten besucht die Suche, bevor sie „nicht vorhanden“ meldet?
Aus demselben Baum wird die Wurzel mit der Nachfolger-Regel gelöscht. Welcher Schlüssel steht danach in der Wurzel?
Welche Höhe hat ein binärer Suchbaum mit Schlüsseln mindestens?
Die Schlüssel können in verschiedenen Reihenfolgen eingefügt werden. Bei wie vielen dieser Reihenfolgen hat der entstehende binäre Suchbaum die Höhe ?
Beweise, dass Fall 3 des Löschens die Suchbaumeigenschaft erhält: Der Knoten mit Schlüssel hat zwei Kinder, ist das Minimum seines rechten Teilbaums , und nach dem Löschen steht der Schlüssel in , während der Knoten aus entfernt wurde.
Man kann 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 Schritte braucht, und begründe, warum es nie mehr als braucht.