Suchbaume Flashcards
Lineare Suche
in O(n) Zeit
Binäre Suche
in O(log n) Zeit.
Einfugen in ein sortiertes Array
in O(n) Zeit
Entfernen aus einem sortierten
in O(n) Zeit
Höhe eines (Teil-)baumes:
Die Höhe h(Tr) eines (Teil-)Baumes Tr mit dem
Wurzelknoten r ist die Länge eines längsten Pfades in dem Teilbaum von r zu einem beliebigen Knoten v in Tr.
Inorder-Durchmusterung:
Behandle rekursiv zunächst den linken
Unterbaum, dann die Wurzel, dann den rechten Unterbaum.
Die Laufzeit liegt fur ¨ n ≥ 1 Knoten in Θ(n), da fur jeden
Knoten genau ein rekursiver Aufruf erfolgt, maximal 2n zusätzliche Aufrufe fur leere Unterbäume hinzukommen, und jeder Aufruf ohne
Folgeaufrufe eine Laufzeit von Θ(1) hat.
Preorder-Durchmusterung:
Behandle rekursiv zunächst die Wurzel,
dann den linken Unterbaum, danach den rechten Unterbaum.
Postorder-Durchmusterung:
Behandle rekursiv zunächst den linken
Unterbaum, dann den rechten Unterbaum, danach die Wurzel.
Successor
Ruckgabewert: Nächster Knoten entsprechend der
Inorder-Durchmusterungsreihenfolge oder null.
Predecessor
Rückgabewert: Vorhergehender Knoten entsprechend der
Inorder-Durchmusterungsreihenfolge oder null.
Entfernen eines Knotens z aus dem Wurzelbaum:
Fall 1: z hat keine Kinder (z.B. Knoten 13). In diesem Fall kann z
einfach entfernt werden.
Fall 2: z hat ein Kind (z.B. Knoten 16). Dieser Fall entspricht dem
Entfernen aus einer verketteten linearen Liste.
Fall 3: z hat zwei Kinder (z.B. Knoten 5). Wir bringen an die Stelle des zu löschenden Knotens einen Ersatzknoten und löschen den
Ersatzknoten an seiner ursprünglichen Position.
Geeigneter Ersatzknoten fur z:
* Der Knoten mit dem größten Schlussel des linken
Unterbaumes (Predecessor) oder
* der Knoten mit dem kleinsten Schlussel des rechten
Unterbaumes (Successor)
Hinweis: Der Ersatzknoten hat in seiner ursprünglichen Position immer maximal einen Nachfolger und wird schließlich gemäß Fall 1
oder 2 entfernt.
Laufzeiten binär Wurzelbaum
Vollständig balancierter Baum:
*Alle inneren Knoten bis auf jene in der vorletzten Ebene
haben 2 Nachfolger.
*Hat die Höhe h(T) = log2n und daher benötigen alle
Operationen bis auf das Durchmustern O(log n) Zeit.
Zu einer Liste entarteter Baum:
Ist der Baum jedoch entartet und hat eine Höhe
h(T) = O(n), dann benötigen alle Operationen O(n) Zeit!
AVL-Baum Laufzeit
Die Laufzeit der Operationen Einfugen und Entfernen ¨
liegt daher immer in O(log n).
Definition: B-Baum der Ordnung m
- Alle Blätter haben gleiche Tiefe und sind leere Knoten.
- Jeder Knoten hat bis zu m Kinder.
- Jeder innere Knoten außer der Wurzel hat mindestens [m/2] Kinder. Die Wurzel hat mindestens 2 Kinder
- Jeder Knoten mit l Schlüssel hat l + 1 Kinder.
B-Bäumen laufzeit
die Operationen Suchen,
Einfugen und Entfernen auch wieder effizient in Θ(logN) Zeit durchfuhrbar.
