Bäume

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.

Vokabeln

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).
Baum als Datenstruktur

Binäre Bäume

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;  
};

weiterführende Themen

weitere Bäume

Heaps