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

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.

Ein dynamischer Baum, der also noch wachsen kann :), wird beispielsweise in C mit folgender (rekursiver) Struktur erstellt:

struct Tree { int data; // bzw. key struct Tree * left; struct Tree * right; };

Nun folgt die Ausprägung der wichtigsten Methoden und ein Beispielprogramm mit den o. a. Integer-Werten:

#include <stdio.h> #include <stdlib.h> struct Tree* createNewTree(int firstElement) { struct Tree * newTree = (struct Tree *) malloc(sizeof(struct Tree)); newTree->data = firstElement; newTree->left = NULL; newTree->right = NULL; return newTree; } void insert(struct Tree *tree, int newData) { // kleinere Elemente werden in den // linken Teilbaum eingefuegt if (tree->data > newData) { // Ist der Tree an dieser Stelle leer, // so wird ein neues Element eingefuegt. if (!tree->left) { struct Tree * newElement = (struct Tree *) malloc(sizeof(struct Tree)); newElement->data = newData; newElement->left = NULL; newElement->right = NULL; tree->left = newElement; return; } else { insert(tree->left,newData); } } // groessere Elemente werden in den // rechten Teilbaum eingefuegt if (tree->data < newData) { // Ist der Tree an dieser Stelle leer, // so wird ein neues Element eingefuegt. if (!tree->right) { struct Tree * newElement = (struct Tree *) malloc(sizeof(struct Tree)); newElement->data = newData; newElement->left = NULL; newElement->right = NULL; tree->right = newElement; return; } else { insert(tree->right,newData); } } // Dieser Zweig sollte nie erreicht werden, da // die Elemente unterscheidbar sein sollten if (tree->data == newData) { printf("Elemente ist bereits vorhanden. Fehler im key!\n"); return; } } void deleteTree(struct Tree *tree) { if (tree->left) deleteTree(tree->left); if (tree->right) deleteTree(tree->right); free(tree); tree = NULL; } int findKey(struct Tree *tree, int key) { if (tree->data == key) return key; // Hier koennten auch komplexere // Strukturen zurueckgeliefert werden, // je nachdem was im Baum verwaltet wurde. if (tree->data > key) { if (!tree->left) // Element ist nicht vorhanden return key-1; else return findKey(tree->left,key); } if (tree->data < key) { if (!tree->right) // Element ist nicht vorhanden return key-1; else return findKey(tree->right,key); } } int main() { // Baum wird mit dem ersten einzufuegenden Element erstellt. struct Tree *myTree = createNewTree(1); // Weitere Elemente werden eingefuegt. insert(myTree,7); insert(myTree,-3); insert(myTree,10); insert(myTree,0); insert(myTree,-4); // Wurde ein Element gefunden, so stimmt die Rückgabe mit dem Schluessel ueberein; // sonst nicht. printf("Ergebnis der Suche nach %d: %d\n",-3,findKey(myTree,-3)==-3); printf("Ergebnis der Suche nach %d: %d\n", 3,findKey(myTree, 3)== 3); // Aufraeumarbeiten deleteTree(myTree); }

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).

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.