Binärer Suchbaum

Die Suchbäume sind die am meisten verwendete Art von Bäumen, sie sind sind geordnete binäre Schlüsselbäume. In Schlüsselbäumen besitzt jeder Knoten einen Schlüssel. Ein Schlüssel ist ein Element aus einer geordneten Menge. Wir gehen hier davon aus, dass jeder Schlüssel nur einmal vorkommt. Es gilt: Alle Schlüssel im linken Teilbaum sind kleiner, alle im rechten Teilbaum sind größer oder gleich dem Schlüssel in diesem Knoten.

Operationen auf binären Suchbäumen:
 - Suchen
- Einfügen
- Löschen
- Sortiert ausgeben

Verwendung
- Verwaltung von geordneten Mengen,
  vor allem, wenn die Größe und Zusammensetzung der Menge sich häufig ändern

Aufgabe a) Zeichnen Sie für die Schlüsselmenge {2,5,6,11,17,18,22} binäre Suchbäume mit den Höhen 2,3,4,5,6!

Elemente in einen Suchbaum einfügen

Aufgabe b) Erstellen Sie Suchbäume mit Hilfe dieses Applets:

Aufgabe c) Fügen Sie folgende Elemente in einen Suchbaum für Integer:

{6, 12, 4, 13, 9, 7, 8, 5, 3, 1, 20}

Traversierung - Möglichkeiten, um Knoten von Binärbäumen zu durchlaufen

Das Verständnis über nachfolgend aufgeführte Möglichkeiten erlangt man zum Beispiel sehr gut über das Applet in Aufgabe d).

Gegeben ist nebenstehender Baum:

PREORDER (= Hauptreihenfolge) (W–BL–BR)

Man betrachtet zuerst die Wurzel (W) und durchläuft anschließend zuerst BL, dann BR.
Beispiel: *+3y/+5x-7a

INORDER (= symmetrische Reihenfolge (BL–W–BR)
Beispiel: 3+y*5+x/7-a

Zuerst durchläuft man BL, betrachtet dann die Wurzel (W) und durchläuft anschließend BR
Alle Schlüssel werden in sortierter Reihenfolge ausgegeben.

POSTORDER (= Nebenreihenfolge) (BL–BR–W)
Beispiel: 3y+5x+7a-/*
Diese Notation wird auch als Postfix-Notation bezeichnet, sie bgegenet uns bei der Stapelverarbeitung.

Zuerst durchläuft man BL, dann BR und anschließend betrachtet man die Wurzel (W).

Beispiel: Gegeben ist der arithmetische Ausdruck (2+y)*(5 + x)/(7-a)

Aufgabe d) Erstellen Sie in diesem Applet Suchbäume.
Beispiel: 3,1,7,2,12,6,4,10,8,5,11,9 Lösung:
Prägen Sie sich die Traversierung bei Inorder und bei Preorder ein. (Vorschlag: Baum erstellen, abzeichnen, Traversierung durchführen und noteiren, welche Knoten der Reihe nach aufgesucht werden.)

Aufgabe e) Wiederholung: Anhand dieses Applets können Sie sich zum Beipiel informieren über:
- Arten von Bäumen
- Tiefe, Knotenanzahl eines Baumes
Beachten Sie insbesondere die Unterschiede bei der Traversierung zwischen Preorder und Inorder (und wer möchte, auch Postorder.)

Aufgabe f) Zeichnen Sie einen Binärbaum mit den folgenden Eigenschaften:
- Jeder Knoten speichert einen Buchstaben
- PREORDER: R O T W E I N
- INORDER:   W T E O I R N

Aufgabe g)
Wie lautet PREORDER zu nebenstehendem Baum?

AVL-Baum

(Ein AVL-Baum (die Erfinder Adelson-Velsky und Landis) ist ein ausbalancierter Baum.)

Aufgabe h) Rufen Sie die Seite auf und stellen Sie sicher, dass AVL nicht aktiviert ist. Fügen Sie nun die einzelnen Knoten ein: {7, 12, 0, 5, 9, 3, 10, 15, 1} .

Termbaum

Applet

Rot-Schwarz-Baum

Applet