IN BEARBEITUNG
Um dieses Kapitel zu verstehen, sollten Listen beherrscht werden.
Listen sind beliebig große Elementsammlungen, die in einer geordneten Reihenfolge vorliegen können. Allerdings haben Listen den Nachteil, dass man sie vollständig durchlaufen muss, um ein Element zu finden. Im Falle einer sortierten Liste, findet man im Idealfall das Element ganz vorne, im schlechtesten Fall findet man das gesuchte Element ganz hinten. Im Schnitt findet man das gesuchte Element Mittig der Liste. Bei einer Liste mit 100 Elementen sind also im Durchschnitt 50 Tests nötig, bevor man das gesuchte Element gefunden hat.
In einem sortierten Array wäre die Suche mit Hilfe der binären Suche deutlich schneller. Was tun, wenn man die Vorteile einer Liste benötigt, aber auch eine hohe Geschwindigkeit, um Datensätze wiederzufinden? Hier kommt der Baum ins Spiel: Grundsätzlich kann man einen Baum wie eine Liste verstehen, allerdings unterteilt die einfachste Form des Baumeselement die Liste in zwei neue Listen, die entsprechend kürzer sind. Während ein Element in der Liste erlaubt zum nächsten Element und bei entsprechender Implementierung auch zum vorherigen Element zu gehen, so erlaubt ein Baumelement mindestens zwei Nachfolger. Bäume mit zwei Nachfolgern heißen binäre Bäume.
Der Listenkopf bei Bäumen heißt Wurzel (englisch 'root'). Die Verzweigungen des Baumes, also ein Element wird als Knoten bezeichnet. Zeichnet man die Verzweigungen (Linien zwischen den Knoten), so werden diese als Kanten bezeichnet. Knoten, die keine Nachfolger besitzen, werden Blatt genannt.
Wird ein Baum gezeichnet, so zeichnet man üblicherweise die Wurzel oben und verzweigt nach unten über die Knoten zu den Blättern. Die einzelnen Elemente (Wurzel, Knoten und Blätter) werden durch Linien verbunden (die Kanten).
Im Vergleich zu einer Liste, ist ein Baum-Element ähnlich aufgebaut, lediglich besitzt es zwei Nachfolger, die im binären Baum häufig mit 'Links' und 'Rechts' bezeichnet werden.
Wie bei Listen gibt es unterschiedliche Implementierungen, entsprechend gibt es optionale Felder, die bei Problemstellungen praktisch sein können, jedoch nicht notwendig sind, um einen Baum aufzubauen.
Superior
entspricht dem Vorgängerelement bei der Liste.
struct AddressTreeElement { struct AddressTreeElement * Superior; // übergeordnetes Element (optional) struct AddressTreeElement * Left, * Right; // Nachfolgende Elemente struct Address Data; }
Nehmen wir an, dass wir hier nun ein Adressbuch aufbauen und möglichst schnell durch die Datensätze suchen wollen. Auch hier benötigen wir einen Kopf, der mindestens den Zeiger auf das Wurzelelement enthält, aber auch beliebige andere Daten enthalten kann. AddressTreeRoot entspricht somit dem Kopf einer Liste:
struct AddressTreeRoot { struct AddressTreeElement * Root; int Elements; };