Was ist ein binärer Suchbaum?
Ein binärer Suchbaum ist eine Sammlung von Knoten, bei der jeder Knoten höchstens zwei Kinder hat und die Werte nach einer festen Regel liegen. Damit finden Sie einen Wert, indem Sie bei jedem Schritt die Hälfte der Möglichkeiten ausschließen.
Eine Hochschule führt Tausende Matrikelnummern. Eine Liste müsste alle durchgehen. Ein Suchbaum springt von der Wurzel in zwanzig Schritten zum Ziel.
Am Ende dieser Lektion
Notiz
Ich kann einen binären Suchbaum aufbauen und in ihm suchen.
Schlüsselwörter
| Begriff | Was er bedeutet |
|---|---|
| Wurzel | der oberste Knoten des Baums |
| Kind | ein Knoten direkt unter einem anderen Knoten |
| Blatt | ein Knoten ohne Kinder |
| Suchbaumregel | links stehen kleinere Werte, rechts größere |
| Rekursion | eine Funktion ruft sich für einen kleineren Teil selbst auf |
| In-order-Wanderung | erst links, dann der Knoten, dann rechts |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Links ist kleiner, rechts ist größer
Jeder Knoten hat einen Wert und höchstens zwei Kinder, links und rechts. Alles im linken Teilbaum ist kleiner als der Knoten. Alles im rechten ist größer. Beim Suchen vergleichen Sie mit der Wurzel und gehen nach links oder rechts. So scheiden Sie bei jedem Schritt einen ganzen Ast aus.
Beispiel: die 60 im Baum suchen
| Schritt | Knoten | Vergleich | Weiter |
|---|---|---|---|
| 1 | 50 | 60 ist größer | Nach rechts |
| 2 | 70 | 60 ist kleiner | Nach links |
| 3 | 60 | 60 ist gleich | Gefunden |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Warum der Baum so schnell ist
Bei jedem Schritt entfällt etwa die Hälfte der Werte. Der erste Befehl gibt die Zahlen in der Reihenfolge der Wanderung aus, nämlich sortiert. Der zweite schreibt eine Million in Binärschreibweise und zählt die Stellen. Das sind zwanzig, so oft lässt sich eine Million halbieren.
Zahlen aufsteigend sortiert ausgeben
printf '50\n30\n70\n20\n60\n80\n40\n' | sort -nHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Wie oft lässt sich eine Million halbieren?
python3 -c "print(len(bin(1000000)) - 2)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Einfügen sucht die freie Stelle
Ein neuer Wert geht wie beim Suchen nach links oder rechts, bis dort kein Knoten mehr ist. Dort hängen Sie den neuen Knoten an. Ein Wert, der schon im Baum steht, wird nicht noch einmal eingetragen. Die Funktion ruft sich dabei für den linken oder rechten Teilbaum selbst auf. Das heißt Rekursion. Sie endet, wenn der Teilbaum leer ist.
Beispiel: 50, 30, 70, 20, 60 einfügen
| Wert | Weg im Baum | Neue Stelle |
|---|---|---|
| 50 | Kein Knoten da | Wurzel |
| 30 | 50: nach links | Links von 50 |
| 70 | 50: nach rechts | Rechts von 50 |
| 20 | 50: links, 30: links | Links von 30 |
| 60 | 50: rechts, 70: links | Links von 70 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Einen Suchbaum aufbauen
# Einen Suchbaum aus Zahlen aufbauen. Die Funktion ruft sich selbst auf.
def einfuegen(knoten, wert):
if knoten is None:
return {"wert": wert, "links": None, "rechts": None}
if wert < knoten["wert"]:
knoten["links"] = einfuegen(knoten["links"], wert)
elif wert > knoten["wert"]:
knoten["rechts"] = einfuegen(knoten["rechts"], wert)
return knoten
wurzel = None
for zahl in [50, 30, 70, 20, 60]:
wurzel = einfuegen(wurzel, zahl)
print(wurzel["rechts"]["links"]["wert"])
# Fuegen Sie noch die 80 ein und lesen Sie wurzel["rechts"]["rechts"] aus.
Die In-order-Wanderung liest alles sortiert
Bei der In-order-Wanderung besuchen Sie zuerst den linken Teilbaum, dann den Knoten, dann den rechten. Das ergibt alle Werte in aufsteigender Reihenfolge. Auch diese Wanderung ruft sich für beide Teilbäume selbst auf. Ein leerer Teilbaum ergibt eine leere Liste.
Beispiel: die Wanderung durch den Baum
| Besuch | Knoten | Ausgabe bisher |
|---|---|---|
| 1 | 20 (ganz links) | 20 |
| 2 | 30 | 20, 30 |
| 3 | 50 | 20, 30, 50 |
| 4 | 60 | 20, 30, 50, 60 |
| 5 | 70 | 20, 30, 50, 60, 70 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Die Wanderung in Python
# Die In-order-Wanderung: links, Knoten, rechts.
def einfuegen(knoten, wert):
if knoten is None:
return {"wert": wert, "links": None, "rechts": None}
if wert < knoten["wert"]:
knoten["links"] = einfuegen(knoten["links"], wert)
elif wert > knoten["wert"]:
knoten["rechts"] = einfuegen(knoten["rechts"], wert)
return knoten
def in_reihenfolge(knoten):
if knoten is None:
return []
return in_reihenfolge(knoten["links"]) + [knoten["wert"]] + in_reihenfolge(knoten["rechts"])
wurzel = None
for zahl in [50, 30, 70, 20, 60]:
wurzel = einfuegen(wurzel, zahl)
print(in_reihenfolge(wurzel))
Ein häufiger Fehler
Warnung
Viele denken, ein Suchbaum sei immer schnell. Fügen Sie aber 1, 2, 3, 4 in dieser Reihenfolge ein, entsteht eine Kette nach rechts. Dann prüfen Sie jeden Knoten einzeln wie bei einer Liste. Erst ein ausgeglichener Baum halbiert bei jedem Schritt.