Zur Themenübersicht     

Wir greifen zurück auf die Definitionen der Graphentheorie, die hier als bekannt vorausgesetzt werden. 

Zur Erinnerung hier ein Graph:

Ein Graph besteht aus Knoten : und Kanten: , welche die Konten verbinden. Werden Graphen zur Verwaltung von Daten verwendet, dann sind die Informationsinghalte in den Knoten und die logischen Verbindungen zwischen den Informationsinhalten in den Kanten zu finden.

 Einige Definitionen zu Graphen:

• Die Anzahl der Kanten, die zu einem Knoten hinführen heißt Indegree des Knotens.

• Die Anzahl der Kanten, die von einem Knoten wegführen heißt Outdegree des Knotens.

 

Mögliche Deklaration eines Knotens in Delphi

Wie immer werden nur Verweise zu den Informationsinhalten gespeichert. TNodeList ist irgendeine Liste von Verweisen auf andere Knoten.

TNode = class(TObject) private ValueP{ointer}:TObject; In Pointer : TNodeList; OutPointer : TNodeList

Nun auf in den Wald! zu einem B A UM :

Definition: Ein Baum ist ein zusammenhängender gerichteter Graph ohne alternative Pfade.

 Einige wichtige Aussagen und Definitionen zu Bäumen:

• Jeder Baum besitzt einen Knoten, von dem aus alle anderen Knoten zu erreichen sind. Dieser Anfangsknoten heißt Wurzel.

• Die Wurzel ist der einzige Knoten, der keinen Vorgänger hat.

• Knoten, von denen keine Kanten mehr ausgehen heißen Blätter.

• Die maximale Anzahl der Knoten längs eines Pfades heißt Tiefe (oder Höhe) des Baumes.

Und nun gleich zu den Binärbäumen:

 

Definition:   Ein binärer Baum ist ein Baum, bei dem jeder Knoten höchstens den Outdegree 2 besitzt.

Im Unterricht haben wir noch eine weitere rekursive (!) Definition erarbeitet:

 

rekursive Definition:   Ein binärer Baum ist entweder leer oder besteht aus einem Knoten, der über zwei Kanten mit zwei weiteren Binärbäumen verkettet ist.

Wer genau hinsieht, bemerkt, dass das untere Bild sich etwas vom oberen unterscheidet: Von den Blättern des Baumes müssen laut Definition ja noch zwei Kanten abgehen, die auf leere Teilbäume zeigen.  !!!

 Auch hier zwei Definitionen zu binären Bäumen:

• Ein Binärbaum heißt vollständig, wenn jeder Pfad (Folge von Kanten) zu einem beliebigen Blatt die gleiche Länge hat. (Dann gibt es keine Leerstellen im Baum)

• ein binärer Baum heißt vollständig ausgeglichen, wenn für jeden Knoten die Anzahl der Knoten in seinem rechten und linken Teilbaum sich um höchstens 1 unterscheidet.

• ein binärer Baum heißt ausgeglichen (oder AVL-ausgeglichen),  wenn die Tiefe seiner beiden Teilbäume sich um höchstens 1 unterscheidet und beide Teilbäume ausgeglichen sind.

Zur Themenübersicht
Zum Seitenanfang
Zur vorigen Seite	Zur nächsten Seite