Binäre Suchbäume

Binäre Suchbäume

• Binärbaum

• Jeder Knoten enthält ein Feld key für den Schlüssel und die Felder left, right und p für den linken und rechten Unterbaum und den Elternknoten

Die Binärer-Suchbaum-Eigenschaft: Sei x ein Knoten in einem binären Suchbaum. Wenn y ein Knoten im linken Unterbaum ist, dann ist key[y]≤key[x]. Wenn y ein Knoten im rechten Unterbaum ist, dann ist key[x]≤key[y].

Inorder-Tree-Walk

gibt alle Elemente des Suchbaumes in sortierter Reihenfolge aus.

Tree-Search

Tree-Search benötigt O(h) Zeit bei einem Baum der Höhe h

Minimum und Maximum

Tree-Minimum und Tree Maximum benötigen O(h) Zeit

Nachfolger

Laufzeit: O(h)

Einfügen

Laufzeit: O(h)

Löschen

Löschen

Suche den zu löschenden KnotenSetze x auf ein Kind

von y

Lösche Knoten y

Verschiebe y nach z

Laufzeit: O(h)