Nun folgt die Ausprägung der wichtigsten Methoden und ein Beispielprogramm mit den o.a. Integer-Werten: |
Nun folgt die Ausprägung der wichtigsten Methoden und ein Beispielprogramm mit den o. a. Integer-Werten: |
Im worst-case ist der Baum nämlich gerade eine Liste, insbesondere bei dem o.a. Beispiel, wenn man die Menge sortiert eingibt, und damit ist die Komplexität gerade die der sequentiellen Suche, also O(n). |
Im worst-case ist der Baum nämlich gerade eine Liste, insbesondere bei dem o. a. Beispiel, wenn man die Menge sortiert eingibt, und damit ist die Komplexität gerade die der sequentiellen Suche, also O(n). |
Stellen wir uns einfach mal eine Menge von Integer-Werten vor: 1,7,-3,10,0,-4. Um in dieser (zugegebenermaßen sehr kleinen) Menge von Werten binär suchen zu können, muß mit diesen Werten ein Baum aufgebaut werden. Eine Baumstruktur, bei der im linken Teilbaum alle kleineren und im rechten Teilbaum alle größeren Elemente stehen, sähe dann wie folgt aus:
1 / \ -3 7 / \ \ -4 0 10
Baum-Vokabular |
Man nennt das oberste Element eines Baums, also hier 1, die Wurzel des Baums. Da das Konstrukt
-3 / \ -4 0
auch wieder einen Baum darstellt, spricht man von linken Teilbaum.
Im Zusammenhang mit Stammbäumen ergibt sich die Bezeichnung Vater-Sohn-Beziehung, also ist -3 Vater und hat zwei Söhne, nämlich -4 und 0.
Die letzten Söhne, die eben keine Väter mehr sind, nennt man auch Blätter. Hier sind -4, 0 und 10 Blätter.
Die Höhe eines Baums ist die größte Entfernung, die eines der Blätter zur Wurzel hat. Dies ist hier 2.
Es gibt nun wie bei fast allen Strukturen eine statische und eine dynamische Variante der Implementierung.
Dynamischer Baum |
Ein dynamischer Baum, der also noch wachsen kann :), wird beispielsweise in C mit folgender (rekursiver) Struktur erstellt:
|
Nun folgt die Ausprägung der wichtigsten Methoden und ein Beispielprogramm mit den o. a. Integer-Werten:
|
Mit diesem kleinen Programm kann man dynamisch einen Baum erstellen und nach Schlüsselwerten suchen. Was ist nun aber der Vorteil dieser Suche?
Ganz einfach. Gehen wir mal davon aus der Baum sei ausgeglichen, d.h. links und rechts stehen jeweils in etwa gleich viel Elemente. Dann halbieren wir die Suchmenge mit jedem Suchschritt. Ist das Wurzelelement größer, so untersuchen wir nur noch den linken Teilbaum. Ist das Wurzelelement kleiner, so untersuchen wir nur noch den rechten Teilbaum.
So ergibt sich die durchschnittliche Anzahl der Suchschritte bei einem ausgeglichenen Baum durch die Höhe des Baums. Man kann nun mathematisch zeigen, daß die Höhe eines ausgeglichenen Baums mit n-Elementen eben gerade log(n) ist, d.h. unser Algorithmus zum Suchen hat die Komplexität O(log(n)) (Landau-Symbol).
Leider ist es nicht gerade besonders einfach ausgeglichene Bäume zu erstellen. Man nennt diese Bäume auch AVL-Bäume, nach den Entdeckern Adelson-Velskij und Landis.
Im worst-case ist der Baum nämlich gerade eine Liste, insbesondere bei dem o. a. Beispiel, wenn man die Menge sortiert eingibt, und damit ist die Komplexität gerade die der sequentiellen Suche, also O(n).
Statischer Baum |
Man kann ein Array auch mit einer Baumstruktur versehen, indem man festlegt, daß das Element mit Index i seinen Vater bei Index i/2 (Integer-Division!) hat.