Hierarchische Strukturen
Die bisher betrachteten Datenstrukturen waren im Wesentlichen eindimensional oder linear : sie weisen mit der Vorgänger-Nachfolger-Relation nur eine Form von Beziehungen zwischen den einzelnen Elementen auf. In diesem Kapitel wollen wir mit den Bäumen eine Klasse von Datenstrukturen kennen lernen, die eine zweite Dimension einbeziehen und dadurch auch die Darstellung von hierarchischen Strukturen ermöglichen.
Baumstrukturen sind nicht nur in der Informatik von fundamentaler Bedeutung, etwa zur Organisation von Daten, sondern sind auch im Alltag in vielfältiger Form wiederzufinden. Ausgehend von solchen Beispielen wird im Folgenden zunächst die Terminologie eingeführt. Im Anschluss daran stellen wir einen Datentyp für Bäume vor und lernen die Basisalgorithmen für das Durchwandern von Bäumen kennen. Eine der wohl wichtigsten Anwendungen von Bäumen in der Informatik ist das Suchen. Auf die hierfür benötigten Strukturen und Algorithmen sowie spezielle Formen von Bäumen werden wir daher im Detail eingehen.
Bäume als hierarchisches Strukturierungshilfsmittel oder Organisationsprinzip sind sicher jedem aus dem täglichen Umfeld vertraut. Ein typisches Beispiel ist etwa der Stammbaum einer Familie, der die Vererbungsbeziehungen darstellt, oder die Systematik in der Biologie (Abbildung 14–1).
Baum
Wurzel
Kind
Blatt
Allgemein können wir unter einem Baum eine Menge von Knoten und Kanten verstehen, die besondere Eigenschaften aufweisen. So besitzt jeder Baum genau einen ausgezeichneten Knoten, der als Wurzel bezeichnet wird. Weiterhin ist jeder Knoten außer der Wurzel durch genau eine Kante mit seinem Vaterknoten (manchmal auch Elternknoten oder Vorgänger) verbunden. Er wird dann auch Kind (Sohn, Nachfolger) dieses Knotens genannt. Ein Knoten ohne Kinder heißt Blatt, alle anderen Knoten bezeichnet man als innere Knoten (Abbildung 14–2).
Abb. 14–1 Beispiele für Baumstrukturen
Abb. 14–2 Begriffe in einem Baum
Pfad
Ein Pfad in einem Baum ist eine Folge von unterschiedlichen Knoten, in der die aufeinander folgenden Knoten durch Kanten miteinander verbunden sind. Mithilfe des Pfades lässt sich auch die grundlegende Eigenschaft eines Baumes definieren: Zwischen jedem Knoten und der Wurzel gibt es genau einen Pfad. Dies bedeutet, dass:
Niveau Höhe
Weitere wichtige Begriffe im Zusammenhang mit Bäumen sind Niveau und Höhe. Unter dem Niveau eines Knotens versteht man die Länge des Pfades von der Wurzel zu diesem Knoten. Die Höhe eines Baumes entspricht dem größtem Niveau eines Blattes plus 1 (Abbildung 14–3).
N-ärer Baum
Binärer Baum
Einzelne Arten von Bäumen können dadurch unterschieden werden, ob jeder Knoten eine bestimmte Anzahl von direkten Kindern haben muss und wie die Kinder angeordnet sind. Ist die Anzahl von Kindern vorgegeben, so spricht man von einem n-ären Baum. Sind die Kinder jedes Knotens in einer bestimmten Reihenfolge geordnet, wird ein solcher Baum als geordneter Baum bezeichnet. Dies führt uns zu einer sehr wichtigen Form von Bäumen: dem binären Baum. Hierbei handelt es sich um einen geordneten Baum, bei dem jeder Knoten maximal zwei Kinder hat. Da binäre Bäume insbesondere für Suchanwendungen von großer Bedeutung sind, werden wir in den folgenden Abschnitten noch genauer auf diese Form eingehen.
Abb. 14–3 Baum mit Niveau der Höhe 4
Abschließend wollen wir noch zwei weitere Beispiele für die Anwendung von Bäumen betrachten. So lassen sich arithmetische Ausdrücke wie
(3 + 4) * 5 + 2 * 3
als Baum repräsentieren (Abbildung 14–4). Der Ausdruck kann nun ausgewertet werden, indem die Operation eines Knotens auf die Werte der beiden linken und rechten Teilbäume angewendet wird. Für die Wurzel liefert dies somit den Gesamtwert des Ausdrucks.
Abb. 14–4 Arithmetischer Ausdruck als Baum
Ein zweites Beispiel ist die Anordnung von Dateien im Dateisystem eines Computers. Wohl jedes moderne Betriebssystem unterstützt ein hierarchisches Dateisystem, das Dateien in Verzeichnissen oder Ordnern organisiert. Da jedes Verzeichnis wiederum selbst Verzeichnisse enthalten kann und ein Wurzelverzeichnis existiert (unter UNIX mit »/« und unter Windows mit »\« bezeichnet), ergibt sich daraus eine Baumstruktur (Abbildung 14–5).
Abb. 14–5 Baumstruktur in einem Dateisystem
Es lassen sich sicher noch eine Vielzahl von Beispielen für Bäume in der Informatik finden. Im Weiteren wollen wir uns aber – nach einem kurzen Exkurs zur Auswertung von arithmetischen Ausdrücken – im Wesentlichen auf die Anwendung als Suchbäume konzentrieren.
Nach der informalen Einführung von Bäumen wollen wir in diesem Abschnitt speziell die Eigenschaften von binären Bäumen mittels eines abstrakten Datentyps unter Verwendung der in Kapitel 11 eingeführten Notation spezifizieren und die Implementierung eines konkreten Datentyps in Java skizzieren.
Parametrisierbarer Datentyp Konstruktion eines binären Baumes
Da der ADT Tree parametrisierbar bezüglich des Typs der Elemente sein soll, wird in der folgenden Spezifikation wieder ein Sortenparameter T verwendet. Die entscheidende Funktion ist bin, die einen binären Baum aus einem linken und einem rechten Teilbaum sowie einem Element des Datentyps T konstruiert. Für einen gegebenen Baum liefern daher left und right den linken bzw. rechten Teilbaum, während value das Wurzelelement dieses Baumes ermittelt. Dies kann unter Verwendung der Funktion bin in Form von Axiomen ausgedrückt werden:
type Tree(T)
import Bool
empty : → Tree
bin : Tree × T × Tree → Tree
left : Tree → Tree
right : Tree → Tree
value : Tree → T
is_empty : Tree → Bool
axioms ∀x,y: Tree, ∀b: T
left (bin (x, b, y)) = x
right (bin (x, b, y)) = y
value (bin (x, b, y)) = b
is_empty (empty) = true
is_empty (bin (x, b, y)) = false
Für einen aus den Teilbäumen x und y sowie dem Element b konstruierten Baum bin(x,b,y) liefert left demnach den Teilbaum x, right den Teilbaum y und value das Element b. Die beiden weiteren Funktionen empty und is_empty werden zur Konstruktion eines leeren Baumes bzw. zum Test auf einen leeren Baum benötigt.
Rekursive Struktur
Spätestens bei der Spezifikation des ADT sollte die rekursive Struktur eines Baumes deutlich werden: Jeder Knoten ist wiederum Wurzel eines Teilbaumes, der aus dem Knoten selbst und den direkten und indirekten Nachfolgern besteht. Bei der Umsetzung in einen konkreten Datentyp muss diese Rekursivität nun dadurch berücksichtigt werden, dass jeder Knoten Verweise auf seine Kinder besitzt. Für den Baum selbst muss dadurch nur noch der Wurzelknoten verwaltet werden, alle anderen Knoten sind durch das Verfolgen der Referenzen (d.h. der Kanten) erreichbar. Sowohl die Knoten als auch der Baum werden in Java als Klassen implementiert. Für einen binären Baum ist dies in Programm 14.1 dargestellt.
public class BinaryTree {
static class TreeNode {
TreeNode left = null, right = null;
Object key;
public TreeNode(Object o) { key = o; }
public Object getKey() { return key; }
public TreeNode getLeft() { return left; }
public TreeNode getRight() { return right; }
public void setLeft(TreeNode n) { left = n; }
public void setRight(TreeNode n) { right = n; }
public String toString() { return key.toString (); }
}
private TreeNode head, nullNode;
public BinaryTree() {
head = new TreeNode(null);
nullNode = new TreeNode(null);
head.setRight(nullNode);
nullNode.setLeft(nullNode);
nullNode.setRight(nullNode);
}
...
}
Referenzen auf die Kinder
Die Klasse TreeNode umfasst neben den Attributen left und right mit den Referenzen auf die beiden Kinder noch ein Attribut key, welches das eigentliche Datenelement aufnimmt – in der Spezifikation des ADT ist dies ein Element des nicht näher spezifizierten Typs T. Die einzelnen Methoden der Klasse TreeNode dienen im Wesentlichen dem Zugriff auf diese Attribute. Soll anstelle eines binären Baumes ein n-ärer Baum mit n > 2 Kindern pro Knoten implementiert werden, so kann auch ein Feld oder eine Liste von Referenzen für die Kindknoten verwaltet werden.
Pseudoknoten
In der Klasse BinaryTree wird die TreeNode-Klasse zur Repräsentation der Knoten verwendet, wobei ähnlich wie bei der Implementierung der Liste aus Abschnitt 13.2 Pseudoknoten eingeführt werden, die die (»leeren«) Verweise der Wurzel (head) und der Blätter des Baumes (nullNode) kennzeichnen (Abbildung 14–6). Diese Pseudoknoten vereinfachen die Implementierung deutlich, da einige Sonderfälle wie der Test auf einen leeren Baum oder auf null-Verweise entfallen können. Der Default-Konstruktor der Klasse BinaryTree führt dabei die notwendigen Initialisierungen durch, d.h., der rechte Nachfolger des head-Knotens verweist auf den eigentlichen Baum – im Fall des leeren Baumes auf den nullNode-Knoten. »Echte« Knoten (in der Abbildung als weiße Knoten dargestellt) werden somit immer als innere Knoten in den rechten Teilbaum von head eingefügt. Die eigentliche Wurzel des Baumes ist demzufolge über head.getRight() erreichbar.
Verarbeitung von arithmetischen Ausdrücken
Als eine Anwendung eines Binärbaumes wollen wir auf das Beispiel des Terminterpreters aus Abschnitt 11.3.2 zur Verwendung eines Kellerspeichers für die Verarbeitung von arithmetischen Ausdrückenzurückgreifen. Wir modifizieren dabei das dort eingeführte Prinzip in der Weise, dass der zweite Stack keine Operanden, sondern Bäume enthält.
Abb. 14–6 Pseudoknoten für die Realisierung eines Binärbaumes
Betrachten wir zunächst das Einlesen eines Terms und die darauf basierende Konstruktion eines Binärbaumes. Anstelle der eigentlichen Termauswertung benötigen wir also Regeln zum Aufbau eines Baumes, wobei die Baumkonstruktion bin jetzt die Termauswertung [[…]] ersetzt, d.h., 
x
wird ersetzt durch bin (empty, x, empty), x * y durch bin (x, *, y) und x + y durch bin (x, +, y). Hierbei ist bin der Operator aus dem ADT Tree. Die eigentlichen Regeln lassen sich nun unter Verwendung der Funktion eval mit zwei Stacks als Parameter wie folgt angeben:
value(t) |
= |
eval |
eval |
= |
eval |
eval |
= |
eval |
eval |
= |
eval |
eval |
= |
eval |
eval |
= |
eval |
eval |
= |
eval |
eval |
= |
eval |
eval |
= |
eval |
eval |
= |
eval |
eval |
= |
x |
eval |
= |
eval |
Die Anwendung dieser Regeln liefert beispielsweise für den Term
(3 + 4) * 5 + 2 * 3
einen Baum, wie er in Abbildung 14–4 auf Seite 371 dargestellt ist. Hierbei werden rekursiv der Reihe nach die Teilbäume für »3«, »4«, »3 + 4« usw. berechnet und auf dem Stack abgelegt.
TextuelleRepräsentation eines Ausdrucks
Infixnotation
Durch Auslesen eines solchen Baumes kann nicht nur der Wert des repräsentierten Ausdrucks bestimmt werden, sondern es lassen sich auch textuelle Repräsentationen des Ausdrucks in unterschiedlichen Notationen ableiten. Nehmen wir eine Funktion term an, die zu einem Knoten im Baum die Textrepräsentation liefert, und einen Operator »+« zur Konkatenation von Zeichenketten, so kann das Auslesen zur Erzeugung der bekannten Infixnotation durch folgende Regeln der rekursiven Anwendung von term erfolgen:
term(empty) = ’*’
term(bin(x, *, y)) = ’(’ + term(x) + ’*’ +
term(y) + ’)’
term(bin(x, +, y)) = ’(’ + term(x) + ’+’ +
term(y) + ’)’
term(bin(empty, x, empty)) = x
Das Prinzip des Auslesens besteht dabei darin, rekursiv von der Wurzel zunächst den linken Teilbaum auszulesen (d.h., den dort repräsentierten Ausdruck auszugeben), anschließend den Operanden bzw. Operator des aktuellen Knotens auszugeben (»*« bzw. »+« in der zweiten und dritten Regel) und schließlich noch den Ausdruck für den rechten Teilbaum zu konstruieren. Dieses Verfahren terminiert für einen leeren Baum sowie einen Knoten mit einem Terminalsymbol. Für den Baum aus Abbildung 14–4 ist die Ausgabe folgende Textrepräsentation:
(((3 + 4) * 5) + (2 * 3))
Präfixschreibweise
Diese Ausleseregeln lassen sich nun leicht modifizieren, um eine andere Notation zu erzeugen. In der Präfixschreibweise steht beispielsweise der Operator vor den beiden Operanden. Dies wird erreicht, indem in der zweiten und dritten Regel zuerst der Operator ausgegeben wird und anschließend erst die Ausdrücke des linken und rechten Teilbaumes:
term(empty) = ’ ’
term(bin(x, *, y)) = ’ ’ + term(x) + term(y)
term(bin(x, +, y)) = ’+’ + term(x) + term(y)
term(bin(empty, x, empty)) = x
Das Ergebnis dieser Variante des Auslesens ist folgender Ausdruck:
+ * + 3 4 5 * 2 3
Postfixnotation
Auf vergleichbare Weise wird der Ausdruck in Postfixnotation (beide Operanden vor dem Operator) konstruiert, indem erst die beiden Teilausdrücke und danach das Operator-Zeichen ausgegeben werden:
term(empty) = ’ ’
term(bin(x, *, y)) = term(x) + term(y) + ’*’
term(bin(x, +, y)) = term(x) + term(y) + ’+’
term(bin(empty, x, empty)) = x
Dies ergibt die folgende Notation:
3 4 + 5 * 2 3 * +
Traversierung
Verallgemeinert man die verschiedenen Varianten des Auslesens eines Baumes aus Abschnitt 14.2.1, so gelangt man zum systematischen Abarbeiten aller Knoten. Dieses »Durchlaufen« des Baumes wird auch als Traversierung (engl. traversal) bezeichnet. Hierfür lassen sich mehrere Strategien finden, die wichtigsten davon wollen wir im Folgenden vorstellen.
Abb. 14–7 Beispiel eines binären Baumes
Hier wird zuerst rekursiv der linke Teilbaum besucht, dann der Knoten selbst und anschließend der rechte Teilbaum. Für den binären Baum aus Abbildung 14–7 entspricht das der Reihenfolge:
D → B → E → A → F → C → G
Ein Beispiel für die Anwendung dieser Strategie ist das Auslesen eines Baumes für einen arithmetischen Ausdruck in Infixschreibweise.
Der Algorithmus für einen Inorder-Durchlauf lässt sich am einfachsten rekursiv formulieren (Algorithmus 14.1). Der gesamte Baum wird nach der Inorder-Strategie durchlaufen, wenn der Algorithmus mit der Wurzel des Baumes als Parameter aufgerufen wird.
algorithm Inorder (k)
Eingabe: Knoten k eines binären Baumes mit Verweis auf
linken (k.left) und rechten (k.right) Teilbaum sowie
dem Element k.elem
Inorder (k.left); /* besuche linken Teilbaum */
Verarbeite k.elem;
Inorder (k.right)/* besuche rechten Teilbaum */
Bei dieser Strategie wird zuerst der Knoten selbst besucht und erst danach erfolgt das Traversieren des linken bzw. rechten Teilbaumes. Für den Beispielbaum liefert das die Reihenfolge:
A → B → D → E → C → F → G
Neben der Ausgabe eines arithmetischen Ausdrucks in Präfixschreibweise ist die Erzeugung einer eingerückten Baumdarstellung für ein Dateisystem wie etwa in Abbildung 14–5 ein typisches Anwendungsbeispiel. Hier wird zuerst der Name des Verzeichnisses ausgegeben und darunter eingerückt eine Liste der darin enthaltenen Dateien und Verzeichnisse.
Der Algorithmus für den Preorder-Durchlauf kann wiederum rekursiv formuliert werden (Algorithmus 14.2).
algorithm Preorder (k)
Eingabe: Knoten k eines binären Baumes
Verarbeite k.elem;
Preorder (k.left); /* besuche linken Teilbaum */
Preorder (k.right) /* besuche rechten Teilbaum */
Beim Postorder-Durchlauf werden erst beide Teilbäume durchlaufen, bevor der Knoten selbst besucht wird. Dies führt in unserem Beispiel zur Reihenfolge
D → E → B → F → G → C → A
Ein Beispiel für die Anwendung dieser Strategie ist die Erstellung einer Stückliste mit Aufsummierung, etwa beim UNIX-Kommando du (disk usage), das den Platzbedarf eines Verzeichnisses und aller Unterverzeichnisse im Dateisystem ermittelt. Hierbei werden zuerst die Größen der Einträge in den Blättern (d.h. der Dateien) bestimmt und für den direkten Vaterknoten (d.h. das enthaltende Verzeichnis) addiert. Der Platzbedarf dieser Verzeichnisse wird wiederum zum Platzbedarf des übergeordneten Verzeichnisses zusammengefasst usw., bis die Gesamtgröße der Wurzel bestimmt werden kann.
Wie bereits bei den anderen beiden Strategien wird der Algorithmus zum Postorder-Durchlauf am einfachsten rekursiv formuliert (Algorithmus 14.3).
algorithm Postorder (k)
Eingabe: Knoten k eines binären Baumes
Postorder (k.left); /* besuche linken Teilbaum */
Postorder (k.right); /* besuche rechten Teilbaum */
Verarbeite k.elem
Während bei den ersten drei Strategien der Baum zuerst in der Tiefe durchwandert wird, entspricht der Levelorder-Durchlauf einer Breitensuche, d.h., auf jedem Niveau des Baumes werden erst alle Knoten besucht, bevor auf das nächste Niveau gewechselt wird. Danach ergibt sich die Reihenfolge:
A → B → C → D → E → F → G
Der Algorithmus zum Levelorder-Durchlauf ist im Gegensatz zu den bisher betrachteten Strategien nicht rekursiv. Stattdessen wird eine Warteschlange verwendet, in der die noch zu verarbeitenden Knoten abgelegt werden. Der Baum wird durchlaufen, indem der nächste zu besuchende Knoten aus der Warteschlange entnommen wird. Nach dem Besuch dieses Knotens werden die Kinder am Ende der Warteschlange eingetragen, bevor mit dem nächsten Knoten fortgefahren wird.
algorithm Levelorder (k)
Eingabe: Knoten k eines binären Baumes
q := leere Warteschlange;
enter (q, k); /* Wurzel in die Warteschlange aufnehmen */
while ¬ is_empty (q) do
Knoten n := leave (q);
Verarbeite n.elem;
enter (q, n.left); /* linken Knoten eintragen */
enter (q, n.right) /* rechten Knoten eintragen */
od
Die Umsetzung der Traversierungsalgorithmen in Java erfolgt am besten in Form von Methoden wahlweise der Klasse TreeNode oder – wie in unserem Fall – .BinaryTree. Dabei gehen wir im Folgenden davon aus, dass die »Verarbeitung« eines besuchten Knotens in der Ausgabe des gespeicherten Elementes besteht.
private void printInorder(TreeNode n) {
if (n != nullNode) {
printInorder(n.getLeft());
System.out.println(n.toString());
printInorder(n.getRight());
}
}
private void printPreorder(TreeNode n) {
if (n != nullNode) {
System.out.println(n.toString());
printPreorder(n.getLeft());
printPreorder(n.getRight());
}
}
private void printPostorder(TreeNode n) {
if (n != nullNode) {
printPostorder(n.getLeft());
System.out.println(n.toString());
}
}
Abbruchkriterium
Traversierungsmethoden
Die In-, Pre- und Postorder-Strategien sind analog den vorgestellten Algorithmen in Form der Methoden printInorder, printPreorder und printPostorder rekursiv implementiert. Als Abbruchkriterium für die Rekursion wird der Aufruf mit einer null-Referenz als Parameter verwendet. Eine iterative Realisierung ist unter Verwendung eines Stacks jedoch auch möglich. Die Traversierungsmethoden werden aus der Methode traverse mit der Wurzel des Baumes als Parameter aufgerufen. Da sie nur intern benutzt werden, sind sie als private vereinbart.
Zur Initiierung der Traversierung eines binären Baumes führen wir die Methode traverse ein, wobei die Strategie über den Parameter der Methode ausgewählt wird. Zu diesem Zweck ist in der Klasse BinaryTree zu jeder Strategie eine Konstante definiert, die als Parameter verwendet werden kann (Programm 14.3).
class BinaryTree {
public static final int INORDER = 1;
public static final int PREORDER = 2;
public static final int POSTORDER = 3;
public static final int LEVELORDER = 4;
public void traverse(int strategy) {
switch (strategy) {
case INORDER:
printInorder(head.getRight());
break;
case PREORDER:
printPreorder(head.getRight());
break;
case POSTORDER:
printPostorder(head.getRight());
break;
case LEVELORDER:
Queue queue = new ArrayQueue();
queue.enter(head.getRight());
printLevelorder(queue);
break;
default:
}
}
}
Warteschlange
Die Levelorder-Strategie ist wie Algorithmus 14.4 iterativ implementiert. Der Aufruf erfolgt wiederum aus der Methode traverse heraus mit einer Warteschlange – einem Objekt mit der Schnittstelle Queue (siehe auch Abschnitt 13.1) – als Parameter, die nur den Wurzelknoten enthält. Sofern der aktuell besuchte Knoten Kinder besitzt, werden diese nach der Verarbeitung in die Warteschlange eingereiht. Das Abbruchkriterium ist hier die leere Warteschlange, d.h., alle Knoten wurden besucht.
private void printLevelorder(Queue q) {
while (! q.isEmpty()) {
TreeNode n = (TreeNode) q.leave();
if (n.getLeft() != nullNode)
q.enter(n.getLeft());
if (n.getRight() != nullNode)
q.enter(n.getRight());
System.out.println(n.toString());
}
}
Die Traversierung eines Baumes, die durch die Ausgabe der Knotenelemente in der entsprechenden Reihenfolge verdeutlicht wird, kann auf einfache Weise durch Aufruf der Methode traverse gestartet werden:
BinaryTree tree = ...;
tree.traverse(BinaryTree.INORDER);
Schlüsselwerte
In Abschnitt 14.2 dienten uns Baumstrukturen im Wesentlichen zur hierarchischen Repräsentation und Organisation von Daten. Eine der wichtigsten Einsatzgebiete von Bäumen ist jedoch die Unterstützung einer effizienten Suche. Hierfür werden in den einzelnen Knoten eines Baumes neben den eigentlichen Nutzdaten (bzw. einen Verweis darauf) zusätzlich noch Schlüsselwerte gespeichert, über die die Suche erfolgt. Man bezeichnet solche Datenstrukturen als Dictionaries oder Wörterbücher. Typische Beispiele sind etwa Telefonbücher mit den Namen oder der Telefonnummer als Schlüssel oder ein Verzeichnis aller Studenten einer Universität mit der Matrikelnummer als Schlüssel.
Binäre Suchbäume
Ein wichtiger Spezialfall von Suchbäumen sind wiederum binäre Suchbäume, auf die wir uns im Folgenden konzentrieren werden. Binäre Suchbäume weisen für jeden inneren Knoten k folgende Eigenschaften auf:
Ordnung der Elemente
Die Konsequenz dieser Eigenschaften ist, dass die Elemente in einem Baum nach ihrem Schlüsselwert geordnet sind. Demzufolge muss auf den Schlüsseln der Elemente eine totale Ordnung definiert sein. Weiterhin wird eine Vergleichsoperation (in Java z.B. durch Implementierung der Schnittstelle java.lang.Comparable) für die Schlüssel benötigt.
Für unsere oben skizzierte Implementierung in der Klasse BinaryTree bedeutet dies, dass der Pseudoknoten head eigentlich das kleinste mögliche Element aufnehmen muss. Dies kann erreicht werden, indem dieser Knoten einen null-Wert als Schlüssel erhält und dieser Umstand in der Vergleichsmethode compareKeyTo entsprechend berücksichtigt wird (Programm 14.5).
static class TreeNode {
...
public int compareKeyTo(Comparable c) {
return (key == null ? -1 :
((Comparable) key).compareTo(c));
}
}
Rekursion
Aus den oben definierten Eigenschaften binärer Suchbäume lässt sich das Suchprinzip einfach ableiten: Der gesuchte Wert wird mit dem Schlüssel des Wurzelknotens verglichen. Ist der Suchwert kleiner, so kann sich das gesuchte Element nur im linken Teilbaum befinden, ist der Wert größer, entsprechend nur im rechten Teilbaum. Andernfalls enthält der Knoten bereits das gesuchte Element. Dieses Prinzip wird nun rekursiv auf den jeweils ausgewählten Teilbaum angewendet, bis das gesuchte Element gefunden wurde oder ein Blatt erreicht ist. In letzterem Fall ist der gesuchte Wert nicht im Baum vorhanden. Abbildung 14–8 verdeutlicht das Vorgehen für die Suche nach dem Element mit dem Schlüssel »5«. Durch den Vergleich mit dem Wurzelknoten (»6«) wird in den linken Teilbaum verzweigt; anschließend ergibt der Vergleich mit dem Schlüssel »3«, dass im rechten Teilbaum dieses Knotens weitergesucht werden muss. Dort liefert dann der letzte Vergleich das gefundene Element.
Abb. 14–8 Suche im binären Suchbaum
Der Algorithmus zur Suche kann sowohl rekursiv als auch iterativ formuliert werden. Bei der rekursiven Variante (Algorithmus 14.5) wird der aktuell zu untersuchende Knoten als Parameter mit übergeben. In Abhängigkeit vom Ergebnis des Vergleichs mit dem Schlüsselwert stoppt die Suche oder wird mit dem linken bzw. rechten Kindknoten fortgesetzt.
algorithm BinTreeSearchRecursive (k, x)
Eingabe: Wurzel k des zu durchsuchenden Teilbaumes
Schlüssel x des gesuchten Elementes
Ausgabe: Element mit dem gesuchten Wert bzw. null,
wenn x nicht gefunden wurde
if k = null then
return null
else if x = k.key then
return k
else if x < k.key then
return BinTreeSearchRecursive (k.left, x)
else
return BinTreeSearchRecursive (k.right, x)
fi fi fi
Cursor
In der iterativen Variante der Suche (Algorithmus 14.6) muss ein Verweis (»Cursor«) auf den aktuell besuchten Knoten verwaltet werden. Mit jeder Verzweigung ist dieser Cursor entsprechend auf den linken oder rechten Nachfolgerknoten zu setzen. Abbruchkriterium ist das Finden eines Knotens mit dem gesuchten Schlüssel bzw. das Erreichen eines Blattes, ohne dass der Schlüssel gefunden wurde. Dies kann als Bedingung einer while-Schleife formuliert werden.
algorithm BinTreeSearchIterative (k, x)
Eingabe: Wurzel k des zu durchsuchenden Baumes
Schlüssel x des gesuchten Elementes
Ausgabe: Element mit dem gesuchten Wert bzw. null,
wenn x nicht gefunden wurde
while k ≠ = null ∧k.key ≠ x do
if x < k.key then
k := k.left
else
k := k.right
fi
od
return k
Bestimmung des minimalen bzw. maximalen Elementes
Die sortierte Organisation der Elemente im Baum ermöglicht auch die Bestimmung des minimalen bzw. maximalen Elementes in einfacher Weise. Da die kleineren Elemente immer links von einem gegebenen Knoten angeordnet sind, muss sich das minimale Element »ganz links« im Baum befinden. Durch Verfolgen der Verweise auf den jeweiligen linken Nachfolgerknoten, ausgehend von der Wurzel, kann dieses Element ermittelt werden (Algorithmus 14.7).
algorithm MinElement (k)
Eingabe: Wurzel k des zu durchsuchenden Baumes
Ausgabe: Knoten k mit dem minimalen Element
while k.left ≠ = null do
k := k.left
od
return k
Die Bestimmung des maximalen Elementes erfolgt analog, wobei natürlich der rechte Zweig zu verfolgen ist, da sich die größeren Elemente immer rechts von einem Knoten befinden müssen.
Implementierung der Suche
Die Suche im binären Suchbaum kann in Java als zusätzliche Methode der Klasse BinaryTree aus Programm 14.6 implementiert werden. Dabei ist sicherzustellen, dass die Knoten im Baum entsprechend ihren Schlüsseln angeordnet werden. Die hierfür notwendige Einfügeoperation werden wir im nächsten Abschnitt vorstellen.
In Programm 14.6 ist die Methode findNode iterativ implementiert. Der Vergleich der Schlüsselwerte der Knoten erfolgt dabei durch Verwendung der Methode compareKeyTo der Klasse TreeNode, die wiederum die Schnittstelle java.lang.Comparable nutzt. Dies bedeutet, dass als Elemente nur Objekte von Klassen, die diese Schnittstelle unterstützen, in den Knoten gespeichert werden können. Die Methode findNode liefert den gefundenen Knoten bzw. null im Fehlerfall zurück.
protected TreeNode findNode(Comparable c) {
TreeNode n = head.getRight();
while (n != nullNode) {
int cmp = n.compareKeyTo(c);
if (cmp == 0)
return n;
else
n = (cmp > 0 ? n.getLeft() : n.getRight());
}
return null;
}
public boolean find(Comparable c) {
return (findNode(c) != null);
}
Auf Basis dieser Methode kann auch die Methode find implementiert werden, die den Wert true liefert, wenn ein Element mit dem gegebenen Wert gefunden werden konnte.
Bei der Manipulation eines binären Suchbaumes, d.h. beim Einfügen oder Löschen von Knoten, müssen die auf Seite 383 formulierten Eigenschaften des Baumes erhalten bleiben, da sonst die Suche nicht mehr funktioniert.
Finden der Einfügeposition
Für die Operation »Einfügen« bedeutet dies zunächst die korrekte Einfügeposition zu finden, so dass die Ordnung der Elemente nicht verletzt wird. Diese Position muss ein Knoten sein, dessen Schlüsselwert größer als der des einzufügenden Elementes ist und der noch keinen linken Nachfolger hat oder einen Knoten mit einem kleineren Schlüsselwert und einen freien Platz für den rechten Nachfolger. Dabei sind im Prinzip zwei Fälle zu unterscheiden:
Werden jedoch wie in unserer Implementierung Pseudoknoten verwendet, so kann der erste Fall ignoriert werden, da nun alle Knoten innere Knoten sind.
In Programm 14.7 ist die Java-Methode insert zum Einfügen eines Elementes für die Klasse BinaryTree dargestellt. Ausgehend von der Wurzel des Baumes wird mithilfe von Algorithmus 14.6 die »Einfügeposition« gesucht. Die Variable child verweist jeweils auf den aktuellen Knoten. Da wir für das Einfügen aber den Elternknoten benötigen, wird in der Variablen parent der jeweilige Vorgänger gespeichert. Ist das »Ende« des Baumes erreicht – child verweist auf den Pseudoknoten nullNode –, so kann das neue Element als Kind von parent eingefügt werden. Ergibt dagegen der Vergleich mit dem aktuellen Knoten, dass das einzufügende Element schon existiert, wird die Methode verlassen und als Ergebnis der Wert false zurückgegeben. Das Einfügen erfolgt einfach, indem der entsprechende Verweis von parent auf den neu erzeugten Knoten node gesetzt wird, wobei durch Vergleich des Elementes mit dem Schlüsselwert von parent geprüft werden muss, ob der neue Knoten als linkes oder rechtes Kind einzufügen ist. Außerdem wird als rechter bzw. linker Kindknoten von node wieder der Pseudoknoten nullNode gesetzt.
public boolean insert(Comparable c) {
Node parent = head, child = head.getRight();
while (child != nullNode) {
parent = child;
int cmp = child.compareKeyTo(c);
if (cmp == 0)
return false;
else
child = (cmp > 0 ? child.getLeft() :
child.getRight());
}
Node node = new Node(c);
if (parent.compareKeyTo(c) > 0)
parent.setLeft (node);
else
parent.setRight (node);
node.setLeft(nullNode); node.setRight(nullNode);
return true;
}
Abbildung 14–9 verdeutlicht dieses Vorgehen für das Einfügen des Elementes »4« in den Suchbaum. Zu Beginn wird child auf das Element »6« gesetzt, parent ist dagegen head. Nach dem Durchlaufen der Schleife verweist parent auf das Element »5«. Da das neue Element kleiner ist, muss es als linker Nachfolger eingefügt werden.
Abb. 14–9 Einfügen im binären Suchbaum
Hochziehen eines Teilbaumes
Die komplizierteste Operation im binären Suchbaum ist das Löschen. Dies liegt daran, dass beim Entfernen eines inneren Knotens einer der beiden Teilbäume des Knotens »hochgezogen« und gegebenenfalls umgeordnet werden muss.
Grundsätzlich müssen beim Löschen eines Knotens k drei Fälle berücksichtigt werden:
Ersetzen eines Knotens
Für das Ersetzen eines Knotens gibt es wiederum zwei Varianten: Entweder werden die Daten der Knoten ausgetauscht oder es werden nur die Verweise auf die Knoten aktualisiert. Die erste Variante ist einfacher zu implementieren, die zweite Methode vermeidet ein unter Umständen aufwendiges Kopieren.
Algorithmus 14.8 zeigt den Vorgang des Löschens in Pseudocode-Notation unter Verwendung der Suchmethode und der Bestimmung des minimalen Elementes.
algorithm RemoveNode (T, x)
Eingabe: Suchbaum T, Schlüssel x des zu löschenden Elementes
k := BinTreeSearchRecursive (T.root, x);
if k = null then return fi;
p := parent (k);
/* 1. Fall */
if k ist Blattknoten then
if k ist linkes Kind then p.left := null
else p.right := null fi
/* 2. Fall */
else if k.left = null then
if k ist linkes Kind then p.left := k.right
else p.right := k.right fi
else if k.right = null then
if k ist linkes Kind then p.left := k.left
else p.right := k.left fi
else /* 3. Fall */
child := MinElement (k.right);
Ersetze k durch child
fi
Der Ausschnitt in Programm 14.8 zeigt mit der Methode remove eine mögliche Implementierung des Löschens. Im ersten Schritt wird in der schon bekannten Weise der Knoten mit dem gesuchten Element im Baum lokalisiert und in der Variablen node gesichert. Hierbei ist auch wieder ein Zeiger parent auf den Elternknoten zu verwalten. Konnte kein Knoten mit dem gegebenen Element gefunden werden, so wird die Methode an dieser Stelle verlassen.
public boolean remove(Comparable c) {
TreeNode parent = head, node = head.getRight(),
child = null, tmp = null;
// zu löschenden Knoten suchen
while (node != nullNode) {
int cmp = node.compareKeyTo(c);
if (cmp == 0)
break;
else {
parent = node;
node = (cmp > 0 ? node.getLeft() : node.getRight());
}
if (node == nullNode)
// Kein Knoten gefunden
return false;
// Fall 1
if (node.getLeft() == nullNode &&
node.getRight() == nullNode)
child = nullNode;
// Fall 2
else if (node.getLeft() == nullNode)
child = node.getRight();
else if (node.getRight() == nullNode)
child = node.getLeft();
else { // Fall 3
// minimales Element suchen
child = node.getRight(); tmp = node;
while (child.getLeft() != nullNode) {
tmp = child;
child = child.getLeft();
}
child.setLeft(node.getLeft());
if (tmp != node) {
tmp.setLeft(child.getRight());
child.setRight(node.getRight());
}
}
if (parent.getLeft() == node)
parent.setLeft(child);
else
parent.setRight(child);
return true;
}
Im zweiten Schritt erfolgt der eigentliche Löschvorgang mit der Behandlung der drei oben aufgeführten Fälle, indem der am weitesten links stehende Knoten des rechten Teilbaumes des node-Knotens ermittelt und durch den Zeiger child referenziert wird. Dieser Knoten wird dann der Ersatzknoten für den zu löschenden Knoten. Der Elternknoten von child wird ebenfalls benötigt und deshalb in der Variablen tmp referenziert. In Abbildung 14–10 ist dies anhand des Löschens des Knotens »3« verdeutlicht. Die Zeiger node und parent verweisen auf den zu löschenden Knoten und dessen Elternknoten. Als »Ersatzknoten« (bezeichnet mit child) wird der Knoten »4« ausgewählt, entsprechend verweist tmp auf dessen Vorgänger »5«. Die Kinder von node müssen nun so umgehängt werden, dass der Knoten »1« linkes Kind und der Knoten »5« rechtes Kind des child-Knotens werden, der an die Stelle von node gesetzt wird.
Allgemein muss der rechte Teilbaum des child-Knotens als linker Teilbaum von tmp umgehängt und der rechte Nachfolger auf den rechten Nachfolger des gelöschten Knotens gesetzt werden. Die beiden letzteren Aktionen dürfen jedoch nur dann durchgeführt werden, wenn der child-Knoten kein direkter Nachfolger des gelöschen Knotens ist, d.h., es muss tmp != node gelten.
Nach diesen Aktionen ist der node-Knoten isoliert und damit aus dem Baum entfernt. Im letzten Schritt wird schließlich noch die Verbindung vom parent-Knoten zum child-Knoten hergestellt.
Abb. 14–10 Löschen im binären Suchbaum
Eine Sonderbehandlung des Wurzelknotens ist hier nicht nötig, da dieser aufgrund des Pseudoknotens head im Prinzip auch ein innerer Knoten ist.
Höhe
Analysiert man die Operationen für binäre Suchbäume, so wird deutlich, dass jeweils nur ein Pfad von der Wurzel bis zum entsprechenden Knoten bearbeitet wird. Der Aufwand wird daher ausschließlich durch die Höhe des Baumes bestimmt, so dass wir als Komplexität O(h) für einen Baum der maximalen Höhe h angeben können.
Problematisch ist dabei jedoch, dass bei einfachen Suchbäumen in der hier betrachteten Form für eine gegebene Menge von Elementen verschiedene Bäume durch eine unterschiedliche Einfügereihenfolge entstehen können. So ergibt beispielsweise die Folge
6, 3, 9, 1, 5, 7, 10
den Suchbaum in Abbildung 14–11(a), der mit einer Höhe von 3ausgeglichen ist, während die Folge
1, 3, 5, 6, 7, 9, 10
zu einem entarteten Baum (Abbildung 14–11(b)) mit der Höhe 7 führt.
Abb. 14–11 »Gute« und »schlechte« Suchbäume
Entarteter Baum
Logarithmische Höhe
Welche Höhe kann nun ein Baum mit n Knoten erreichen? Für den schlechtesten Fall entartet der Baum zu einer Liste und hat damit die Höhe n. Hat dagegen jeder innere Knoten zwei Nachfolger, so gibt es 1 Knoten auf Niveau 0, 2 Knoten auf Niveau 1, 4 Knoten auf Niveau 2 usw. bis 2k Knoten auf Niveau k. Insgesamt kann ein Baum der Höhe k + 1 damit 2k + 2k−1 + … 4 + 2 + 1 = 2k+1 − 1 Suchwerte fassen! Demzufolge hat ein solcher Baum bei n Knoten eine Höhe von log2n. Suchbäume mit einer logarithmischen Höhe nennt man auch ausgeglichene oder balancierte Bäume. Sie zeichnen sich dadurch aus, dass für eine vorgegebene Zahl n von Elementen die Höhe h möglichst klein ist. Wie diese Eigenschaft erreicht werden kann, werden wir im folgenden Abschnitt näher betrachten.
t, empty, empty
