Bäume

Bäume sind eine der wichtigsten Datenstrukturen der Informatik. Sie finden Anwendung in unterschiedlichen Bereichen:

• als Suchbäume zum Finden von Elementen in geordneten Mengen
• als Entscheidungsbäume zur Organisation sukzessiver Entscheidungen
• als Strukturbäume zur Repräsentation der syntaktischen Struktur von Programmen
• als Datenstruktur zur Organisation eines Sortierprozesses

Grundbegriffe

Baum

Eine Datenstruktur heißt dann ein Baum (tree) B, wenn sie folgende Eigenschaften besitzt:

• Es gibt genau einen Knoten, der keinen Vorgänger besitzt. Dieser wird als Wurzel (root) bezeichnet.
• Alle Knoten von B, außer Root besitzen genau einen Vorgängerknoten.
• Ein Baum ist eine rekursive Datenstruktur, d.h. er lässt sich durch eine Reihe von Teilbäumen darstellen.

Blätter und innere Knoten

Als Blatt (leaf) bezeichnet man denjenigen Knoten, der keine Nachfolger besitzt.
Alle anderen Knoten heißen innere Knoten vom Baum B.

Vorgänger und Nachfolger

Ein Knoten y, der direkt unter einem Knoten x liegt, heißt (direkter) Nachfolger (descendant) von x.
Umgekehrt heißt der Knoten x direkter Vorgänger (ancestor) von y.

Stufen und Höhe

Ist ein Knoten x auf der Stufe i, so ordnet man seinem Nachfolger y die Stufe i+1 zu.
Die Wurzel eines Baumes liegt auf Stufe 0.
Die größte Stufe eines Baumes nennt man seine Höhe.

Grad und Kanten

Die Zahl der direkten Nachfolger eines inneren Knotens ist sein (Verzweigungs-)Grad.
Der höchste Grad unter allen Knoten ist der Grad des Baumes.
Bäume vom Grad 2 heißen binär.
Als Kanten bezeichnet man die Äste des Baumes.

Weglänge

Die Zahl der Kanten von der Wurzel bis zu einem Knoten x nennt man Weglänge von x.
Der Knoten auf der Stufe i hat die Weglänge i.
Die Weglänge eines Baumes ist die Summe der Weglängen aller seiner Knoten. Sie heißt innere Weglänge.

Schlüssel oder Marke oder Informationsfeld eines Knotens

Der Wert (Text, Zahl, etc.) der einem Knoten zugeordnet wird, nennt man Schlüssel, Marke oder Informationsfeld.

Darstellung von Baumstrukturen

Es gibt verschiedene Möglichkeiten eine Baumstruktur darzustellen:

als geschachtelte Mengen

als geschachtelte Klammern

(Z(A(B,C),D(E,F(G),H,I(K,L)))

als Einrückungen

                  Z
                        A
                              B
                              C
                        D
                              E
                              F
                                    G
                              H
                              I
                                    K
                                    L

oder als Graphen

Bäume als Datenstrukturen

Bäume können wie Listen rekursiv definiert werden.

Wurzel (root) eines Teilbaumes T = w.
Kind/Sohn sind die direkten Nachfolger von w.
Der Vater ist der direkte Vorgänger vom Knoten w.

Operationen auf Bäume

Die wichtigsten Operationen auf Bäume sind

• das Suchen eine Knotens
• das Einfügen eines neuen Knotens
• das Entfernen eines Knotens.
  

» drucken: pdf | html