[X] Binärer Suchbaum

Ben04

Die neuste Version befindet sich am Ende dieses Threads.

Edit : Hab den Titel geändert.

--- Original Post ---

Dies ist die erste Fassung die ich hochlade. Mich interessiert vor allem ob in der Theorie irgendwo Fehler sind und ob es verständlich ist.

Die Implementation ist auch noch recht ungetestet und ich würde mich freuen falls da jemand Fehler findet. Text zur Implementierung gibt es erst wenn ich sicher bin, dass da nicht noch etwas in externe Funktionen ausgelagert wird oder sonst wie umgeschrieben wird. Soll ich die Debugdump Funktion drin lassen oder nicht? Die sind nur alle public um das Debuggen zu erleichterten.

Die Überschriften haben noch keine Nummerierung und ein Index gibt es auch noch nicht. Das mache ich ganz zum Schluss wenn ich weiß, dass sich da nichts mehr ändert.

Wie macht man besten eine Tabelle? Ich hab noch eine im HTML Format drin, die kann natürlich nicht so stehen bleiben.

-------------------------------------------

Einfacher binär Baum

Darstellung

Eine geordnete Liste kann in einem binäre Baum dargestellt werden, indem man jedem Knoten einen Wert zuweist und dafür sorgt, dass sämtliche Werte des linken Unterbaums kleiner und des rechten Unterbaums größer sind.

Suchen

Um ein Element zu suchen beginnt man die Suche an der Wurzel. Falls die Wurzel den Wert darstellt ist man schon fertig. Sonst vergleicht man ob der gesuchte Wert kleiner oder größer ist und setzt seine Suche im entsprechenden Unterbaum fort. Wenn man auf der untersten Ebene des Baums angelangt ohne den Wert gefunden zu haben dann ist er nicht im Baum enthalten.

In folgendem Beispiel wird die 7 gesucht.

Um ein Element zu finden müssen wir im schlimmsten Fall von der Wurzel bis zur untersten Ebene wandern. Im besten Fall hat der Baum eine Höhe die logarithmisch von der Anzahl seiner Elemente abhängt. Dies gibt also in etwa eine Komplexität von O(log(n)) um ein Element zu suchen wenn wir ungünstige Bäume ignorieren. n ist die Gesamtanzahl der Elemente im Baum.

Einfügen

Um einen Wert einzufügen geht man ähnlich vor wie bei der Suche. Man wandert solange nach unten, bis man einen Knoten gefunden hat der noch ein Kind frei hat.

In folgendem Beispiel wird die 8 eingefügt.

Da es sich an sich um den gleichen Algorithmus handelt wie bei er Suche ist auch die Komplexität die gleiche und zwar O(log(n)).

Löschen

Als erstes sucht man den zu löschenden Knoten nach bekannter Methode. Wie man danach vorgeht hängt von der Position im Baum ab.

Löschen eines Blatts

Um ein Blatt zu löschen trennt man es einfach vom Elternknoten ab.

Folgendes Beispiel zeigt wie die 5 aus dem Baum gelöscht wird:

Löschen eines Knoten mit einem Kind

Man trennt den Knoten von Kind und von Elternknoten ab. Anschließend verbindet man Kind und Elternknoten.

Im nächsten Beispiel wird die 3 gelöscht.

Löschen eines Knoten mit zwei Kindern

Man sucht im linken Unterbaum das größte Element. Dieses befindet sich ganz rechts im Unterbaums. Es genügt also den rechten Kindern zu folgen bis dies nicht mehr geht. Dieses Element ist immer ein Blatt oder hat nur ein Kind da es ja kein rechtes Kind hat. Es kann also mit einer der beiden oben genannten Operationen gelöscht werden. Man vertauscht den Knoten den man löschten will mit diesem und löscht ihn raus. Da beide Werte direkt hintereinander in der Liste liegen wird diese auch nicht durcheinander gebracht.

In folgendem Beispiel wird die 7 gelöscht.

Alternative kann man auch das kleinste Element des rechten Unterbaums suchen und mit dem tauschen. Keine der beiden Methoden bringt aber wirklich einen Vorteil deswegen ist es an sich egal für welche man sich entscheidet.

Die Geschwindigkeit der eigentlichen Löschverfahren sind alle unabhängig von der Größe des Baums. Legendlich die Suche des zu löschenden Elements und die Suche des größten Elements hängen von der Größe ab, darum ist die Komplexität einer Löschoperation in etwa O(log(n)).

Ausbalancierte Bäume und die die es nicht sind

Eines der großen Probleme solcher Bäume ist, dass wenn die Reihenfolge der Einfügungen ungünstig ist der Baum sehr schnell aus dem Gleichgewicht kommt und zu einer Seite hinkt. Dies macht den Baum viel höher als nötig und somit die Suche viel langsamer da diese ja von der Höhe des Baums abhängt.

In folgendem Baum wird die 8 gesucht und der Arbeitsaufwand kommt schon nahe an den einer sequenziellen Suche heran.

Um dem entgegen zu wirken kann man Rotationen einsetzen.

Rotationen

Es gibt Rotationen nach links und welche nach rechts. Da die Operationen genau spiegelverkehrt sind werde ich nur die links Rotation eingehen.

Als erstes trennt man das linke Enkelkind vom rechten Kind ab und anschießend das rechte Kind.

Nun wird das rechte Kind zur neuen Wurzel und die alte Wurzel wird ihr neues rechtes Kind. Das Enkelkind wird zum neuen rechten Kind der alten Wurzel.

Nun ist der Baum wieder im Gleichgewicht.

Man sagt links Rotation da das Gleichgewicht sich nach links verlagert. Man kann es sich wie eine Balkenwaage vorstellen welche man in das Gleichgewicht bringt indem man den Balken an einer anderen Stelle aufhängt.

Das Beispiel hinkt zwar da nach der Rotation beide Gewichte gleich schwer sind.

Die Geschwindigkeit einer Rotation hängt nicht von der Größe des Baums ab. Die Komplexität ist also O(1).

Das große Problem mit Rotationen ist zu wissen wann man sie einsetzen soll. Sie verbessern nämlich nicht immer die Darstellung eines Baums. Es gibt verschiedene Strategien um hier vorzugehen.

AVL Baum

Darstellung

Ein AVL Baum ist ein Baum der sich selbst ausbalanciert. Jedes Mal wo eine Operation ihn aus dem Gleichgewicht bringt rotiert er sich so, dass er wieder ausgewogen da steht.

Der Name AVL hat nichts mit seiner Funktionsweise zu tun sondern geht auf seine Erfinder Adelson-Velsky und Landis zurück.

Um nicht jedes Mal von neuem den gesamten Baum untersuchen zu müssen speichert jeder Knoten noch eine zusätzliche Information über die Balance und zwar die vorzeichenbehaftete Differenz der Höhen des rechten und linken Unterbaums. Also wie sehr er nach rechts hängt.

Der erste Baum ist recht gut ausbalanciert und besser wird es mit ein paar Rotationen auch nicht. Der zweite hingegen ist stark aus dem Gleichgewicht, bei ihm würden ein paar Rotationen sicher helfen. In einem AVL Baum müssen sämtliche Knoten eine Balance von -1, 0 oder 1 haben. Diese Bedingung ergibt zwar nicht immer den perfekten Baum jedoch immer einen sehr guten. Der erste der beiden Bäume oben ist ein AVL Baum, der zweite nicht.

Notation

Mit h(X) ist die Höhe des Unterbaums unter dem Knoten X gemeint. Falls einen Knoten einen neuen Platz im Baum im Laufe einer Operation erhält so wird die Anfangshöhe des Unterbaums mit h(X) und die Endhöhe mit h(X*) notiert.

Wenn auf einer Grafik sich keine Angaben zu der Balance befinden so ist irgendein ausbalancierter Unterbaum gemeint. Falls die Balance als ? angegeben wird dann kann sie entweder nicht genau bestimmt werden oder ihr Wert interessiert uns nicht.

Buchstaben die vorne im Alphabet vorkommen stehen für einen bestimmten Knoten und die die hinten im Alphabet vorkommen für irgendeinen ausbalancierten Unterbaum.

Rotationen in einem AVL Baum

Bei Rotationen in AVL Bäumen müssen nicht nur die Knoten neu verbunden werden, sondern es müssen auch die Balancen neu ausgerechnet werden. Da auch bei AVL Bäumen die Rotationen spiegelverkehrt sind werde ich erneut nur die links Rotation im Detail behandeln.

Da die Unterbäume der Knoten X, Y und Z nicht verändert werden ändert sich ihre Balance auch nicht. Es müssen also nur die neuen Balancen von A und B bestimmt werden. a und b sind bekannt und a* und b* werden gesucht.

a = h(B) - h(X) (1)
b = h(Z) - h(Y) (2)
a* = h(Y) - h(X) (3)
b* = h(Z) - h(A*) (4)

Über die Höhen von A* und B wissen wir folgendes:

h(A*) = max(h(Y), h(X)) + 1 (5)
h(B) = max(h(Y), h(Z)) + 1 (6)

Folgende Formeln sollten dem Leser bekannt sein damit er dem Beweis folgen kann:

max(u, v) - u = max(u-u, v-u) = max(0, v -u)
-max(u, v) = min(-u, -v)

(2) - (1) ergibt:

b - a = h(Z) - h(Y) - h(B) + h(X)
h(Y) - h(X) = - h(B) + h(Z) - b + a
a* = - max(h(Y), h(Z)) - 1 + h(Z) - b + a | durch (5) und (3)
a* = min(-h(Y), -h(Z)) - 1 + h(Z) - b + a
a* = min(h(Z)-h(Y), 0) - 1 - b + a
a* = min(b, 0) - 1 - b + a | durch (2)
a* = a - 1 - max(0, b) (7)

(7) gibt uns eine Formel um a* zu bestimmen.

h(Z) - h(A*) = h(Z) - h(A*) - b + b
b* = h(Z) - h(A*) - h(Z) + h(Y) + b | durch (2) und (4)
b* = - h(A*) + h(Y) + b
b* = - max(h(Y), h(X)) - 1 + h(Y) + b | durch (3)
b* = min(-h(Y), -h(X)) - 1 + h(Y) + b
b* = min(0, h(Y) - h(X)) - 1 + b
b* = min(0, a*) - 1 + b | durch (3)
b* = b - 1 + min(0, a*) (8)

(8) gibt uns eine Formel um b* zu berechnen.

Zusammenfassung

Links Rotation

a* = a - 1 - max(0, b)
b* = b - 1 + min(0, a*)

Rechts Rotation

a* = a + 1 - min(0, b)
b* = b + 1 + max(0, a*)

Ausbalancieren

Der Baum kann nur aus der Balance geraten wenn wir einen Knoten anhängen oder abschneiden. Da wir den Baum danach wieder ins Gleichgewicht bringen können wir davon ausgehen, dass kein Knoten mehr aus der Balance gerät als -2 oder +2. Des Weiteren verändert das Einfügen oder Löschen nur die Balance der Elternknoten. Also können wir den Baum von unten nach oben ausbalancieren. Durch diese Vorgehensweise können wir sicher sein, dass Rotationen nur auf Knoten ausgeführt werden, die ausbalancierte Kinder haben.

Da die Methoden um einen Knoten mit einer Balance von -2 oder +2 zu behandeln nur spiegelverkehrt sind werde ich nur den Fall +2 beschreiben.

Da der Baum nach rechts hängt liegt eine links Rotation nahe. Diese führt aber nicht immer zum gewünschten Ergebnis. In folgendem Beispiel tut sie es:

Doch in dem nächsten nicht, da eine Balance von -2 auftaucht.

Nehmen wir mal an, dass der Erfolg nur von der Balance des rechten Kindes abhängt. Da dieser Unterbaum im Gleichgewicht sein muss ergeben sich drei Fälle.

Neben den eigentlichen Rotationen interessiert uns auch um wie viel der Baum in der Höhe gekürzt wird weil dies die Balance der Elternknoten beeinflusst.

Das Kind hat eine Balance von +1

Per Definition der Balance wissen wir, dass:

h(Z) - h(Y) = 1 also h(Y) = h(Z) - 1 (1)
h(B) - h(X) = 2 also h(X) = h(B) - 2 (2)

Aus (1) können wir schließen, dass h(Z) > h(Y) und daraus:

h(B) = h(Z) + 1 (3)

(3) in (2) gibt uns einen Wert für h(X):

h(X) = h(Z) + 1 - 2 = h(Z) - 1 (4)

Nach einer links Rotation sieht unser Baum wie folgend aus:

Aus (4) und (3) ergibt sich h(X) = h(Y) also ist

Die Balance von A* : h(X) - h(Y) = 0
h(A) = h(X) + 1 = h(Z) - 1 + 1 = h(Z) (5)

Aus (5) ergibt sich, die neue Balance von B:

Die Balance von B* : h(A) - h(Z) = 0

Da alle Knoten eine Balance von 0 haben ist der Baum im Gleichgewicht.

Errechnen wir die Anfangshöhe des Baums.

h(A) = max(h(X)+1, h(B)+1)
h(A) = max(h(X)+1, max(h(Y)+1, h(Z)+1)+1)
h(A) = max(h(X)+1, h(Y)+2, h(Z)+2)
h(A) = max(h(Z), h(Z)+1, h(Z)+2) | durch (1) und (4)
h(A) = h(Z)+2

Nun die Endhöhe des Baums.

h(B*) = max(h(A*)+1, h(Z)+1)
h(B*) = max(max(h(X)+1, h(Y)+1)+1, h(Z)+1)
h(B*) = max(h(X)+2, h(Y)+2, h(Z)+1)
h(B*) = max(h(Z)+1, h(Z)+1, h(Z)+1) | durch (1) und (4)
h(B*) = h(Z) + 1

Da h(A) - h(B*) = 1 wurde der Baum um 1 in der Höhe gekürzt.

Das Kind hat eine Balance von 0

Durch eine ähnliche Überlegung wie oben kommen wir auf folgende Gleichungen:

h(X) = h(Z)-1 (1)
h(Y) = h(Z) (2)

Daraus folgt folgende Rotation:

Die Rotation bringt den Baum also ins Gleichgewicht.

Errechnen wir die Anfangshöhe des Baums.

h(A) = max(h(X)+1, h(Y)+2, h(Z)+2)
h(A) = max(h(Z)+2, h(Z)+2, h(Z)+2) | durch (1) und (2)
h(A) = h(Z) + 2

Nun die Endhöhe des Baums.

h(B*) = max(h(X)+2, h(Y)+2, h(Z)+1)
h(B*) = max(h(Z)+1, h(Z)+2, h(Z)+1) | durch (1) und (2)
h(B*) = h(Z) + 2

Da h(A) - h(B*) = 0 wurde der Baum nicht in der Höhe geändert.

Das Kind hat eine Balance von -1

In diesem Fall führt eine einfache links Rotation nicht zum Ziel. Als erstes muss das rechte Kind rechts rotiert werden und anschließend erst die Wurzel nach links.

Die Berechung der Balancen ist hier schwieriger. Als erstes definieren wir M = max(h(Y), h(Z)). Da der Unterbaum in C im Gleichgewicht ist wissen wir:

M - h(Y) = 0 oder 1
M - h(Z) = 0 oder 1

Analog zu der Vorgehensweise bei den zwei bereits genannten Fällen können wir sagen, dass:

h(C) = M + 1
h(B) = M + 2
h(W) = M
h(X) = M

Die neue Balance von A und B kann wie folgt eingegrenzt werden:

h(Y) - h(X) = h(Y) - M = -(0 oder 1) = 0 oder -1
h(W) - h(Z) = M - h(Z) = 0 oder 1

Es ist also egal was die Ausgangsbalance von C ist, die neue Balancen von A und B sind immer im Zielbereich.

Die neue Balance von C kann auch eingeschränkt werden:

h(B*) - h(A*) = [h(W) - h(Z)] - [h(Y) - h(X)] = M - h(Z) - h(Y) + M = [M - h(Y)] + [M - h(Z)] = (0 oder 1) + (0 oder 1) = 0 oder 1 oder 2

Für den Fall 2 müssten aber sowohl M - h(Y) = 1 und M - h(Z) = 1 was aber nicht möglich ist da in diesem Fall M größer wäre als das Maximum von h(Y) und h(Z). Der Baum ist also in der Balance.

Die Anfangshöhe kann wie folgt berechnet werden:

h(A) = max(h(X) + 1, h(B) + 1)
h(A) = max(h(X) + 1, h(C) + 2, h(W) + 2)
h(A) = max(M + 1, M + 3, M + 2)
h(A) = M + 3

Und die Endhöhe folgendermaßen:

h(C*) = max(h(A*)+1, h(B*)+1)
h(C*) = max(h(X)+2, h(Y)+2, h(Z)+2, h(W)+2)
h(C*) = max(h(X), h(Y), h(Z), h(W))+2
h(C*) = max(h(X), max(h(Y), h(Z)), h(W))+2
h(C*) = max(M, M, M)+2
h(C*) = M+2

Da h(A) = h(C*) + 1 wurde die Höhe des Baums um 1 gekürzt.

Zusammenfassung

Die Kolonnen sind die Balance der Wurzel und die Reihen die des entsprechenden Kindes

<table>
<tr><td></td><td>-2</td><td>+2</td></tr>
<tr><td>-1</td><td>rechts Rotation der Wurzel/Höhe um 1 gekürzt</td><td>rechts Rotation des Kindes danach links Rotation der Wurzel/Höhe um 1 gekürzt</td></tr>
<tr><td>0</td><td>rechts Rotation der Wurzel/Höhe unverändert</td><td>links Rotation der Wurzel/Höhe unverändert</td></tr>
<tr><td>1</td><td>links Rotation des Kindes danach rechts Rotation der Wurzel/Höhe um 1 gekürzt</td><td>links Rotation der Wurzel/Höhe um 1 gekürzt</td></tr>
</table>

Suchen

Da das Suchen den Baum nicht verändert gibt es auch nichts auszubalancieren und nichts unterscheidet sie von der normalen Suche.

Einfügen

Zuerst fügen wir wie bei einem normalen Baum einen Knoten an. Anschließend wandern wir den Baum hinauf und hängen ein Gewicht an den Knoten. Dieses Gewicht entspricht der Verlängerung des Unterbaums. Am Anfang ist dieses Gewicht 1 da wir ja einen Knoten angehängt haben.

Bei jedem Knoten korrigieren wir als allererstes die Balance indem wir das Gewicht entweder hinzu addieren oder subtrahieren je nachdem ob das Gewicht an den linken oder rechten Unterbaum kommt. Danach berechnen wir wie sich die Höhe verändert hat um das Gewicht zu berechnen welches an den Elternknoten kommt.

Mit Hilfe des Vorzeichens der Balance können wir bestimmen welcher Unterbaum höher ist und die Höhe bestimmt. Falls wir etwas an den höheren gehängt haben so ändert sich am Gewicht nichts und das Alte hat den gleichen Wert wie das Neue. Falls es der kleinere ist so ist das neue Gewicht 0 solange die Balance nicht kippt da sich die Gesamthöhe nicht ändert weil diese vom anderen Unterbaum bestimmt wird.

Ist das neue Gewicht bestimmt dann wird der Unterbaum ausbalanciert. Wenn dadurch die Höhe gekürzt wird so muss das Gewicht natürlich auch dem entsprechend verändert werden.

Sollte das Gewicht 0 werden bevor die Wurzel erreicht wird dann können wir abbrechen.

Die Komplexität ist logarithmisch da wir den Baum im schlimmsten Fall einmal von oben nach unten und dann wieder nach oben durchlaufen und die Höhe logarithmisch von der Gesamtanzahl der Elemente abhängt.

Löschen

Falls der zu löschende Knoten zwei Kinder hat so tauschen wir ihn zuerst mit dem ihm vorhergehenden Element aus wie wir es auch in einem normalen Baum tun würden.

Danach hängen wir derselben Vorgehensweise wie beim Einfügen ein Gewicht an den Knoten und zwar mit dem Wert -1 und anschießend wird der Knoten aus dem Baum gelöscht.

Aufmerksame Leser werden wahrscheinlich befürchten, dass das Gewicht, das wir anhängen, eine Rotation heraufbeschwört welche den Baum so verändert, dass der Knoten sich auf einmal im Baum befindet und zwei Kinder besitzt. Dies kann aber nicht passieren, da das Gewicht negativ ist. Der Baum wird also zu dem anderen Unterbaum hinhinken und dieser wird durch eine eventuelle Rotation verändert werden.

Implementation

#include<iostream>
#include<algorithm>
#include<sstream>
#include<string>
#include <cassert>
using namespace std;

template<class T>
struct Tree{
	// Data structure

	struct Node{
		Node*parent, *left, *right;
		T value;
		int balance;

		explicit Node(const T&value, Node*parent = 0):
			parent(parent), left(0), right(0), value(value), balance(0){}
	};

	Node*root;

	Tree():root(0){

	}

	// Debug print

	static unsigned get_height(const Node*node){
		if(node)
			return std::max(get_height(node->left), get_height(node->right))+1;
		else
			return 0;
	}

	static std::string get_node_label(const Node*node){
		if(node){
			std::ostringstream out;
			out<<node->value<<"["<<node->balance<<"]";
			return out.str();
		}else
			return "";
	}

	static unsigned get_width(const Node*node){
		if(node)
			return get_width(node->left) + get_node_label(node).length() + get_width(node->right);
		else
			return 0;
	}

	static void print_white_spaces(std::ostream&out, unsigned count){
		for(unsigned i=0; i<count; ++i)
			out<<' ';
	}

	static void print_tree_level(std::ostream&out, const Node*node, int level){
		if(node){
			if(level == 1){
				print_white_spaces(out, get_width(node->left));
				out<<get_node_label(node);
				print_white_spaces(out, get_width(node->right));
			}else{
				print_tree_level(out, node->left, level-1);
				print_white_spaces(out, get_node_label(node).length());
				print_tree_level(out, node->right, level-1);
			}
		}
	}

	static void print_node(std::ostream&out, const Node*node){
		for(unsigned level=1, h=get_height(node); level <= h; ++level){
			print_tree_level(out, node, level);
			out<<'\n';
		}
	}

	void dump(std::ostream&out){
		print_node(out, root);
	}

	// rotation

	Node**get_parent_ptr(Node*node){
		if(node->parent){
			if(node->parent->left == node)
				return &node->parent->left;
			else
				return &node->parent->right;
		}else
			return &root;
	}

	static bool is_left_child(Node*node){
		if(node->parent)
			return node->parent->left == node;
		else
			return false;
	}

	static bool is_right_child(Node*node){
		if(node->parent)
			return node->parent->left == node;
		else
			return false;
	}

	Node*rotate_left(Node*A){
		Node
			**root_ptr = get_parent_ptr(A),
			*parent = A->parent,
			*B = A->right,
			*X = A->left,
			*Y = B->left,
			*Z = B->right;

		*root_ptr = B;
		B->left = A;
		B->right = Z;
		A->left = X;
		A->right = Y;

		B->parent = parent;
		A->parent = B;
		if(Z)
			Z->parent = B;
		if(X)
			X->parent = A;
		if(Y)
			Y->parent = A;

		A->balance = A->balance - 1 - std::max(0, B->balance);
		B->balance = B->balance - 1 + std::min(0, A->balance);

		return B;
	}

	Node*rotate_right(Node*A){
		Node
			**root_ptr = get_parent_ptr(A),
			*parent = A->parent,
			*B = A->left,
			*X = B->left,
			*Y = B->right,
			*Z = A->right;

		*root_ptr = B;
		B->left = X;
		B->right = A;
		A->left = Y;
		A->right = Z;

		B->parent = parent;
		A->parent = B;
		if(Z)
			Z->parent = A;
		if(X)
			X->parent = B;
		if(Y)
			Y->parent = A;

		A->balance = A->balance + 1 - std::min(0, B->balance);
		B->balance = B->balance + 1 + std::max(0, A->balance);

		return B;
	}

	int balance(Node*&root){
		if(root->balance == 2){
			Node*child = root->right;
			if(child->balance == 1){
				root = rotate_left(root);
				return 1;
			}else if(child->balance == 0){
				root = rotate_left(root);
				return 0;
			}else if(child->balance == -1){
				rotate_right(child);
				root = rotate_left(root);
				return 1;
			}
		}else if(root->balance == -2){
			Node*child = root->left;
			if(child->balance == 1){
				rotate_left(child);
				root = rotate_right(root);
				return 1;
			}else if(child->balance == 0){
				root = rotate_right(root);
				return 0;
			}else if(child->balance == -1){
				root = rotate_right(root);
				return 1;
			}
		}else if(root->balance >= -1 && root->balance <= 1)
			return 0;
		assert(false);
	}

	static bool did_balance_side_changed(int old_balance, int new_balance){
		return old_balance * new_balance <= 0;
	}

	void add_weight(Node*now, int weigth){
		while(now != root && weigth != 0){		
			if(is_left_child(now)){
				now = now->parent;

				now->balance -= weigth;
				if(now->balance <= 0)
					weigth = std::min(weigth, -now->balance);
				else
					weigth = 0;

				weigth -= balance(now);
			}else{
				now = now->parent;

				now->balance += weigth;
				if(now->balance >= 0)
					weigth = std::min(weigth, now->balance);
				else
					weigth = 0;

				weigth -= balance(now);

			}
		}
	}

	bool search(const T&value)const{
		Node*now = root;
		while(now){
			if(value < now->value)
				now = now->left;
			else if(now->value < value)
				now = now->right;
			else
				return true;
		}
		return false;
	}

	bool insert(const T&value){
		Node*parent = 0;
		Node**child_ptr = &root;

		while(*child_ptr){
			Node*child = *child_ptr;
			if(value < child->value){
				child_ptr = &child->left;
				parent = child;
			}else if(child->value < value){
				child_ptr = &child->right;
				parent = child;
			}else
				return false;
		}

		Node*new_node = new Node(value, parent);
		*child_ptr = new_node;

		add_weight(new_node, 1);
		return true;
	}

	static bool is_leaf(Node*node){
		return !node->left && !node->right;
	}

	static Node*find_min(Node*now){
		while(now->left)
			now = now->left;
		return now;
	}

	void swap_nodes(Node*a, Node*b){
		*get_parent_ptr(a) = b;
		*get_parent_ptr(b) = a;

		if(a->left)
			a->left->parent = b;
		if(b->left)
			b->left->parent = a;
		if(a->right)
			a->right->parent = b;
		if(b->right)
			b->right->parent = a;

		std::swap(a->parent, b->parent);
		std::swap(a->left, b->left);
		std::swap(a->right, b->right);
		std::swap(a->balance, b->balance);
	}

	void remove(Node*node){
		if(is_leaf(node)){
			add_weight(node, -1);
			*get_parent_ptr(node) = 0;
			delete node;
		}else if(node->left == 0){
			add_weight(node, -1);
			*get_parent_ptr(node) = node->right;
			node->right->parent = node->parent;
			delete node;
		}else if(node->right == 0){
			add_weight(node, -1);
			*get_parent_ptr(node) = node->left;
			node->left->parent = node->parent;
			delete node;
		}else{
			Node*other = find_min(node->right);
			swap_nodes(node, other);
			dump(std::cout);
			remove(node);
		}
	}

	bool remove(const T&value){
		Node*now = root;
		while(now){
			if(value < now->value)
				now = now->left;
			else if(now->value < value)
				now = now->right;
			else{
				remove(now);
				return true;
			}
		}
		return false;
	}

};

int main(){
	Tree<int>t;

	srand(time(0));

	for(int i=0; i<10;++i){
		t.insert(rand()%20);
	}

	for(;;){
		t.dump(std::cout);
		std::cout<<"Enter value : ";
		int val;
		std::cin>>val;
		t.remove(val);
	}
}

Anwendungen

Die Anwendungen sind sehr vielfältig. Zum Beispiel kann man einen AVL Baum benutzen um std::set und std::map zu implementieren. Wie man die Implementation eines std::set aussehen könnte sollte nun eigentlich klar sein. Eine std::map kann man als AVL Baum implementieren wo man in jedem Knoten Schlüssel und Wert speichert und den Baum nach dem Schlüssel sortiert.

Quellen

Die Grafiken wurden mit Inkscape erstellt.

GPC

Hi,

cool, dass du den Artikel schreibst
Sieht schon ziemlich gut aus

Ben04 schrieb:

Wie macht man besten eine Tabelle? Ich hab noch eine im HTML Format drin, die kann natürlich nicht so stehen bleiben.

Screenshot machen und so reinhängen. Oder von Hand schreiben und in code-Tags packen.

Grüße

Christian

estartu

Wow, also für mich ist das ziemlich starker Tobak.
Was bitte ist eine "Komplexität"?

Es wäre schön, wenn du Theorie und Praxis nicht so strikt trennen würdest.
Als Unwisserder wird man zuerst von der Theorie erschlagen und wer sich da durchgekämpft hat wird mit einem auf den ersten Blick sehr unübersichtlichen Brocken Code konfrontiert.
Ich fände es schöner, wenn man den Code leichter den Bildern zuordnen könnte.
Vielleicht könntest du ja immer nach einem Abschnitt Theorie den damit erarbeiteten Code zeigen?

Den Teil mit den vielen Formeln habe ich leider nur angelesen und kaum ansatzweise begriffen... dazu muss ich erstmal den Einführungsteil sacken lassen.

Wegen der Tabelle: Du kannst auch eine Html-Datei in unser Ftp-Verzeichnis hochladen und hier verlinken.

Jester

estartu schrieb:

Was bitte ist eine "Komplexität"?

Überzeugt -- Ich werde schaun, dass ich nen Artikel zum Thema O-Kalkül schreibe.
Btw, wäre Laufzeitkomplexität vielleicht noch etwas "korrekter".
Ich finde nicht, dass man die Theorie zu sehr mit der Implementierung vermischen sollte. Bei sowas hilft ein Blick in die Implementierung nicht mehr wirklich die Theorie zu klären.

Zum Artikel: Gefällt mir sehr gut. Allerdings sind die Beweispassagen doch recht heftig und nicht besonders schön zu lesen. Geht das irgendwie anders?

Ansonsten ziemlich gut. Etwas störend finde ich, dass manchmal ne Überschrift kommt und danach direkt ne Unterüberschrift. Imho ist es schöner, diese Stelle dazu zu nutzen schonmal zu verraten worum's in dem Abschnitt gehen soll. Generell wäre ein bißchen mehr Motivation und manchmal ein behutsames daran erinnern, was Du gerade machst nicht schlecht.

Noch ein Trick: oft hilft es, sich den Leser als Ochsen vorzustellen, der dem Text des Schreibenden
zwar meist gutmütig folgt, den man aber immer wieder motivieren muss, dem man besser alles
gaaanz langsam und gründlich erklären muss und der immer wieder wissen will, wohin die Reise geht.

Auf Korrektheit habe ich jetzt noch nicht gelesen. Aber ich gehe davon aus, dass da außer dem ein oder anderen Flüchtigkeitsfehler nichts drin ist. Die Zeichnungen sind prima. Die Trennung zwischen Theorie und Implementierung finde ich gut. Vorausgesetzt der versprochene Text zur Implementierung kommt noch.

Ben04

estartu schrieb:

Wow, also für mich ist das ziemlich starker Tobak.
Was bitte ist eine "Komplexität"?

Kurz gesagt : Eine Mathefunktion die die Anzahl der Elemente als Parameter nimmt und die Zeit zurück gibt die die Operation braucht. Dabei interessiert uns nur der Fall wenn es viele Elemente gibt. Desweiteren ist es nur grob geschätzt darum lässt man konstante Faktoren einfach weg.

Also mit der Komplexität kannst du sagen, ob du es noch erleben wirst, dass der Algorithmus bei einer Million Elementen fertig wird oder nicht.

estartu schrieb:

Es wäre schön, wenn du Theorie und Praxis nicht so strikt trennen würdest.

Vielleicht wäre es besser den Artikel zu splitten und einen zu einfachen Suchbäumen zu machen also ohne ausbalancieren und mit Implementation. Das wäre dann die Theorie bis zum AVL Baum und danach eine sehr abgespeckte Version der Implementation. Falls mal ein Artikel zum Thema rot schwarz Baum oder Splay Baum käme dann müsste dieser die Grundlagen auch nicht wiederholen und könnte einfach auf diesen Artikel verweisen.

estartu schrieb:

Als Unwisserder wird man zuerst von der Theorie erschlagen und wer sich da durchgekämpft hat wird mit einem auf den ersten Blick sehr unübersichtlichen Brocken Code konfrontiert.

Wie bereits gesagt, den Code werde ich erst erklären wenn ich weiß, dass sich da nichts mehr ändert. Dann wird das auch übersichtlicher.

estartu schrieb:

Ich fände es schöner, wenn man den Code leichter den Bildern zuordnen könnte. Vielleicht könntest du ja immer nach einem Abschnitt Theorie den damit erarbeiteten Code zeigen?

Gefällt mir nicht sonderlich die Idee. Dies würde die Theorie ja nur noch mehr aufblähen. Es gibt zwei Sorten von Leser : Die die es zum ersten Mal lesen und die die nachschlagen wollen. Bei ersteren würde das Mischen von Theorie und Implementation wahrscheinlich nicht schaden allerdings beim nachschlagen würde es mich zu mindest gewaltig stören.

estartu schrieb:

Den Teil mit den vielen Formeln habe ich leider nur angelesen und kaum ansatzweise begriffen... dazu muss ich erstmal den Einführungsteil sacken lassen.

Zu verstehen brauchst du ihn auch nicht, alles was du nachher brauchst ist die Zusammenfassung und die sollte kurz und einfach zu verstehen sein.

In der ersten Version hatte ich die Formel einfach so hingeschrieben ohne Erklärung wie man darauf kommt und zu jedem Fall ein Zahlen Beispiel. Das war auch nicht das wahre.

estartu schrieb:

Wegen der Tabelle: Du kannst auch eine Html-Datei in unser Ftp-Verzeichnis hochladen und hier verlinken.

Wäre eine Idee, jedoch wird die nicht so groß, dass das sich lohnen würde. Ich werde die Variante mit dem Bild wählen.

Jester schrieb:

Allerdings sind die Beweispassagen doch recht heftig und nicht besonders schön zu lesen. Geht das irgendwie anders?

Über kürzere Beweise würde ich mich freuen. Vielleicht zuerst die Zusammenfassung mit einem Hinweis, dass man den Beweis überspringen kann wenn es einen nicht interessiert?

Jester schrieb:

Etwas störend finde ich, dass manchmal ne Überschrift kommt und danach direkt ne Unterüberschrift.

Ich könnte die Unterüberschrift "Darstellung" einfach weg nehmen.

Jester schrieb:

Generell wäre ein bißchen mehr Motivation und manchmal ein behutsames daran erinnern, was Du gerade machst nicht schlecht.

Wo würdest du noch etwas ändern. Die beiden Abschnitte "Einfügen" und "Löschen" beim AVL Baum werde ich stark überarbeiten.

Soll ich bei der Implementation des AVL Baums auch darauf eingehen wie man so ein Biest debuget oder nicht?

Was noch fehlt ist ein iterativer Zugang zu den Daten. Ein kompletter Iterator wäre wahrscheinlich zu aufgeblasen und würde seinen eigenen Artikel verdienen, jedoch empfinde ich das Thema als zu wichtig, als dass man es einfach unter den Tisch fallen lassen könnte. Falls gesplittet wird könnte man im ersten Artikel noch einen Iterator hinzufügen.

estartu

Ben04 schrieb:

estartu schrieb:

Wow, also für mich ist das ziemlich starker Tobak.
Was bitte ist eine "Komplexität"?

Kurz gesagt : Eine Mathefunktion die die Anzahl der Elemente als Parameter nimmt und die Zeit zurück gibt die die Operation braucht. Dabei interessiert uns nur der Fall wenn es viele Elemente gibt. Desweiteren ist es nur grob geschätzt darum lässt man konstante Faktoren einfach weg.

Also mit der Komplexität kannst du sagen, ob du es noch erleben wirst, dass der Algorithmus bei einer Million Elementen fertig wird oder nicht.

Ah cool. DAS habe ich verstanden.

estartu schrieb:

Es wäre schön, wenn du Theorie und Praxis nicht so strikt trennen würdest.

Vielleicht wäre es besser den Artikel zu splitten und einen zu einfachen Suchbäumen zu machen also ohne ausbalancieren und mit Implementation. Das wäre dann die Theorie bis zum AVL Baum und danach eine sehr abgespeckte Version der Implementation. Falls mal ein Artikel zum Thema rot schwarz Baum oder Splay Baum käme dann müsste dieser die Grundlagen auch nicht wiederholen und könnte einfach auf diesen Artikel verweisen.

Das wäre wirklich sinnvoll.

estartu schrieb:

Als Unwisserder wird man zuerst von der Theorie erschlagen und wer sich da durchgekämpft hat wird mit einem auf den ersten Blick sehr unübersichtlichen Brocken Code konfrontiert.

Wie bereits gesagt, den Code werde ich erst erklären wenn ich weiß, dass sich da nichts mehr ändert. Dann wird das auch übersichtlicher.

Okay, dann warte ich mit Meckern nochmal, bis da Erklärungen stehen.

estartu schrieb:

Ich fände es schöner, wenn man den Code leichter den Bildern zuordnen könnte. Vielleicht könntest du ja immer nach einem Abschnitt Theorie den damit erarbeiteten Code zeigen?

Gefällt mir nicht sonderlich die Idee. Dies würde die Theorie ja nur noch mehr aufblähen. Es gibt zwei Sorten von Leser : Die die es zum ersten Mal lesen und die die nachschlagen wollen. Bei ersteren würde das Mischen von Theorie und Implementation wahrscheinlich nicht schaden allerdings beim nachschlagen würde es mich zu mindest gewaltig stören.

Ok. Ich gehöre ja zu Ersteren.

estartu schrieb:

Den Teil mit den vielen Formeln habe ich leider nur angelesen und kaum ansatzweise begriffen... dazu muss ich erstmal den Einführungsteil sacken lassen.

Zu verstehen brauchst du ihn auch nicht, alles was du nachher brauchst ist die Zusammenfassung und die sollte kurz und einfach zu verstehen sein.

Wie weit unten muss man für die Zusammenfassung gucken? Die die ich gesehen habe ist auch wieder formelkryptisch.

Jester schrieb:

Allerdings sind die Beweispassagen doch recht heftig und nicht besonders schön zu lesen. Geht das irgendwie anders?

Über kürzere Beweise würde ich mich freuen. Vielleicht zuerst die Zusammenfassung mit einem Hinweis, dass man den Beweis überspringen kann wenn es einen nicht interessiert?

Ja, sowas wäre gut, aber bitte denk an den Hinweis, ab wo man weiterlesen soll.

Soll ich bei der Implementation des AVL Baums auch darauf eingehen wie man so ein Biest debuget oder nicht?

Das wäre eine gute Idee. Falls du sowieso den Artikel teilst, könnte sowas (falls es viel Text ist) ein Teil 3 werden.

Jester

Ben04 schrieb:

Jester schrieb:

Allerdings sind die Beweispassagen doch recht heftig und nicht besonders schön zu lesen. Geht das irgendwie anders?

Über kürzere Beweise würde ich mich freuen. Vielleicht zuerst die Zusammenfassung mit einem Hinweis, dass man den Beweis überspringen kann wenn es einen nicht interessiert?

Wie wäre es, wenn Du die Ergebnis-Formeln angibst (evtl. als Lemma o.ä. formuliert) und für den Beweis auf einen Anhang am Ende des Artikels verweist? Dann wird niemand erschlagen und wen's interessiert, der kann sich nach der Lektüre noch die Beweise anschaun.

Ben04 schrieb:

Ich könnte die Unterüberschrift "Darstellung" einfach weg nehmen.

Ja, ich denke das ist ne ganz gute Idee.

Ben04 schrieb:

Jester schrieb:

Generell wäre ein bißchen mehr Motivation und manchmal ein behutsames daran erinnern, was Du gerade machst nicht schlecht.

Wo würdest du noch etwas ändern. Die beiden Abschnitte "Einfügen" und "Löschen" beim AVL Baum werde ich stark überarbeiten.

Ich nehm jetzt trotzdem mal das Löschen als Beispiel.
Du beschreibst was man tun muß und verpackst wichtige Infos auch in Überschriften: Fallunterscheidung Blatt/kein Blatt. Imho isses schöner, wenn das noch im vorigen Text deutlich dabeisteht welche Fälle es gibt.

Was noch fehlt ist ein iterativer Zugang zu den Daten. Ein kompletter Iterator wäre wahrscheinlich zu aufgeblasen und würde seinen eigenen Artikel verdienen, jedoch empfinde ich das Thema als zu wichtig, als dass man es einfach unter den Tisch fallen lassen könnte. Falls gesplittet wird könnte man im ersten Artikel noch einen Iterator hinzufügen.

Das geht ja normalerweise mit dem Standardtrick einher, die Knoten zusätzlich noch in ner doppelt verketteten List zu halten. Damit wird dann auch der Iterator sehr einfach und schnell. Vielleicht passt das in ne Schlußbemerkung?

Ben04

Ich hab den Artikel nun gesplittet. Der Implementationsteil ist länger geworden als ursprünglich geplant. Platz für den AVL-Teil ist da wirklich nicht mehr.

=================================

Suchen das Problem

Sei es eine Datenbank oder ein Dateisystem: Das Suchen nach Werten ist eines der häufigsten Probleme in der Informatik. Das im Grunde einfach klingende Problem erweist sich als ein außerordentlich komplexes Biest sobald man über den Tellerrand der trivialen Ansätze blickt.

Für viele Anwendungen recht ein Array in das man sämtliche Werte reinschmeißt und anschließend von Anfang bis Ende durchläuft. Wenn die Datenbank aber wächst dann wird dieser Ansatz aber unvertretbar langsam. Der erste Verbesserungsvorschlag wird dann wohl sein das Array zu sortieren und es dann mit der Hilfe einer binären Suche zu durchwühlen. Solange sich die Element des Arrays nur wenig verändert ist dieser Ansatz gut andernfalls stößt auch er an seine Grenzen.

Wer noch mehr Geschwindigkeit braucht der muss sich vom einfachen Array verabschieden und auf eine andere Datenstruktur ausweichen. Ein Ansatz ist die Werte in einer Hash-Tabelle zu speichern. Dies wird aber nicht das Thema dieses Artikels sein, vielmehr wird es eine Weiterentwickelung der binären Suche sein: Der binäre Suchbaum.

Binäre Suchbäum

Binäre Bäume können dazu genutzt werden um eine Liste so darzustellen, dass man schnell nach einem Element suchen kann und schnell welche einfügen oder löschen kann. Dazu weist man jedem Knoten ein Element der Liste zu und sorgt dafür, dass sämtliche Elemente des linken Unterbaums kleiner und die des rechten Unterbaums größer sind.

Suchen

Um ein Element zu suchen beginnt man die Suche an der Wurzel. Falls die Wurzel den Wert darstellt ist man schon fertig. Sonst vergleicht man ob der gesuchte Wert kleiner oder größer ist und setzt seine Suche im entsprechenden Unterbaum fort. Wenn man auf der untersten Ebene des Baums angelangt ist ohne den Wert gefunden zu haben dann ist er nicht im Baum enthalten.

In folgendem Beispiel wird die 7 gesucht.

Um ein Element zu finden müssen wir im schlimmsten Fall von der Wurzel bis zur untersten Ebene wandern. Im besten Fall hat der Baum eine Höhe die logarithmisch von der Anzahl seiner Elemente abhängt. Dies gibt also in etwa eine Laufzeitkomplexität von O(log(n)) um ein Element zu suchen wenn wir ungünstige Bäume ignorieren. n ist die Gesamtanzahl der Elemente im Baum.

Einfügen

Um einen Wert einzufügen geht man ähnlich vor wie bei der Suche. Man wandert solange nach unten, bis man einen Knoten gefunden hat der noch ein Kind frei hat.

In folgendem Beispiel wird die 8 eingefügt.

Da es sich an sich um den gleichen Algorithmus handelt wie bei er Suche ist auch die Komplexität die gleiche und zwar O(log(n)).

Löschen

Als erstes sucht man den zu löschenden Knoten nach bekannter Methode. Wie man danach vorgeht hängt von der Position im Baum ab, das heißt wie viele Kinder der Knoten hat.

Löschen eines Knoten ohne Kinder

Um ein Blatt zu löschen trennt man es einfach vom Elternknoten ab.

Folgendes Beispiel zeigt wie die 5 aus dem Baum gelöscht wird:

Löschen eines Knoten mit einem Kind

Man trennt den Knoten von Kind und von Elternknoten ab. Anschließend verbindet man Kind und Elternknoten.

Im nächsten Beispiel wird die 3 gelöscht.

Löschen eines Knoten mit zwei Kindern

Man sucht im linken Unterbaum das größte Element. Dieses befindet sich ganz rechts in diesem. Es genügt also den rechten Kindern zu folgen bis dies nicht mehr geht. Dieses Element ist immer ein Blatt oder hat nur ein Kind da es ja kein rechtes Kind haben kann. Es kann also mit einer der beiden oben genannten Operationen gelöscht werden. Man vertauscht den Knoten den man löschten will mit diesem und löscht ihn raus.

Da beide Werte direkt hintereinander in der Liste liegen wird diese auch nicht durcheinander gebracht solange eines der beiden Elemente gelöscht wird.

In folgendem Beispiel wird die 7 gelöscht.

Alternative kann man auch das kleinste Element des rechten Unterbaums suchen und mit dem tauschen. Keine der beiden Methoden bringt aber wirklich einen Vorteil deswegen ist es an sich egal für welche man sich entscheidet.

Die Geschwindigkeit der eigentlichen Löschverfahren sind alle unabhängig von der Größe des Baums. Legendlich die Suche des zu löschenden Elements und die Suche des größten Elements hängen von der Größe ab, darum ist die Komplexität einer Löschoperation in etwa O(log(n)).

Ausbalancierte Bäume und die die es nicht sind

Eines der großen Probleme solcher Bäume ist, dass wenn die Reihenfolge der Einfügungen ungünstig ist der Baum sehr schnell aus dem Gleichgewicht kommt und zu einer Seite hinkt. Dies macht den Baum viel höher als nötig und somit die Suche viel langsamer da diese ja von der Höhe des Baums abhängt.

In folgendem Baum wird die 8 gesucht und der Arbeitsaufwand kommt schon nahe an den einer sequenziellen Suche heran.

Um dem entgegen zu wirken kann man Rotationen einsetzen.

Rotationen

Es gibt Rotationen nach links und welche nach rechts. Da die Operationen genau spiegelverkehrt sind werde ich nur auf die links Rotation eingehen.

Als erstes trennt man das linke Kind vom rechten Kind der Wurzel ab und anschießend auch das rechte Kind.

Danach wird das rechte Kind zur neuen Wurzel und die alte Wurzel wird ihr neues rechtes Kind. Das Enkelkind wird zum neuen rechten Kind der alten Wurzel.

Nun ist der Baum wieder im Gleichgewicht.

Man sagt links Rotation da das Gleichgewicht sich nach links verlagert. Man kann es sich wie eine Balkenwaage vorstellen welche man in das Gleichgewicht bringt indem man den Balken an einer anderen Stelle aufhängt.

Das Beispiel hinkt zwar da nach der Rotation beide Gewichte gleich schwer sind.

Die Geschwindigkeit einer Rotation hängt nicht von der Größe des Baums ab. Die Komplexität ist also O(1).

Das große Problem mit Rotationen ist zu wissen wann man sie einsetzen soll. Sie verbessern nämlich nicht immer die Darstellung eines Baums. Es gibt verschiedene Strategien um hier vorzugehen.

Implementation

Das erste was man bei einer Implementation festlegen muss ist die Darstellung. Die Knoten werden durch eine Struktur dargestellt und dann mit Pointern verbunden. Dies sieht in etwa so aus:

template<class T>
struct Node{
	Node*parent, *left, *right;
	T value;

	explicit Node(const T&value):
		parent(0), left(0), right(0), value(value){}
};

parent zeigt auf den Elternknoten. Falls es sich um die Wurzel handelt ist dieser NULL. left und right zeigen jeweils auf die Wurzel des linken oder rechten Unterbaums oder NULL falls es diesen nicht gibt.

Um zu verhindern, dass Unbefugte an unserem Baum rumbasteln wird dieser durch eine Klasse gekapselt. Dies sieht dann in etwa folgendermaßen aus:

template<class T>
class Tree{
private:
	struct Node{
		Node*parent, *left, *right;
		T value;

		explicit Node(const T&value):
			parent(0), left(0), right(0), value(value){}

	Node*root;
public:
	Tree():root(0){}

	bool is_empty()const{
		return !root;
	}
};

root zeigt dabei auf die Wurzel des Baumes oder NULL falls der Baum leer ist. Ob der Baum leer ist kann mittels is_empty überprüft werden.

Navigation

Um uns beim navigieren im Baum zu helfen wäre es sicher nicht verkehrt Funktionen zu schreiben die prüfen ob es sich um ein linkes oder rechtes Kind handelt.

private:
static bool is_left_child(const Node*node){
	if(node->parent == 0)
		return false; // Die Wurzel ist kein Kind
	else
		return node->parent->left == node;
}

static bool is_right_child(const Node*node){
	if(node->parent == 0)
		return false; // Die Wurzel ist kein Kind
	else
		return node->parent->right == node;
}

Um die Position eines Knoten ändern zu können muss man auch einen einfachen Zugriff auf den Zeiger im Elternknoten haben.

private:
Node**get_parent_ptr(Node*node){
	if(node->parent == 0)
		return &root;
	else if(is_left_child(node))
		return &node->parent->left;
	else
		return &node->parent->right;
}

Debuggen

Da es sehr schwer ist einen Baum fehlerfrei zu implementieren müssen wir uns auch Gedanken machen wie wir ihn debuggen. Wer sich nur für den eigentlichen Code interessiert kann diesen Teil des Artikels getrost überspringen.

Konsolenausgabe

Eine Funktion die den Baum einfach komplett auf die Konsole ausgibt wäre sehr nützlich da die meisten Debugger nicht sonderlich gut sind um solche Datastrukturen zu inspizieren und nur Zeigersalat anzeigen.

Ziel ist es den Baum ähnlich wie auf den Grafiken oben auszugeben. Dazu müssen wir als erstes festlegen welche Informationen über einen Knoten ausgegeben werden. Dies mach folgende Funktion:

private:
static std::string format_label(Node*node){
	if(node){
		std::ostringstream out;
		out<<node->value;
		return out.str();
	}else
		return "";
}

Wir müssen auch wissen wie breit und hoch der Baum wird damit wir wissen genügend Platz frei gelassen werden muss. Folgende Funktionen berechnen diese Informationen für den Baum und jeden Unterbaum.

private:
static unsigned get_height(Node*node){
	if(!node)
		return 0;
	unsigned left_height = 0, right_height = 0;

	if(node->left)
		left_height = get_height(node->left);
	if(node->right)
		right_height = get_height(node->right);

	// Der höchste Unterbaum bestimmt die Gesamthöhe
	return std::max(left_height, right_height) + 1;
}

static unsigned get_width(Node*node){
	if(!node)
		return 0;
	unsigned left_width = 0, right_width = 0;

	if(node->left)
		left_width = get_width(node->left);
	if(node->right)
		right_width = get_width(node->right);

	return left_width + format_label(node).length() + right_width;
}

Da wir nur zeilenweise auf die Konsole schreiben können müssen wir den Baum auch Zeile für Zeile ausgeben.

private:
static void dump_spaces(std::ostream&out, unsigned count){
	for(unsigned i=0; i<count; ++i)
		out.put(' ');
}

static void dump_line(std::ostream&out, Node*node, unsigned line){
	if(!node)
		return;
	if(line == 1){
		// Die Wurzel der Unterbaums soll ausgegeben werden
		dump_spaces(out, get_width(node->left));
		out<<format_label(node);
		dump_spaces(out, get_width(node->right));
	}else{
		// Im linken Unterbaum ist die Wurzel um eins niedriger und darum verändert
		// sich die Zeilennumerirung.
		dump_line(out, node->left, line-1);
		dump_spaces(out, format_label(node).length());
		dump_line(out, node->right, line-1);
	}
}

Nun benötigen wir noch eine Möglichkeit den gesamten Baum auszugeben und nicht nur eine Zeile.

private:
static void dump_node(std::ostream&out, Node*node){
	for(unsigned line=1, height = get_height(node); line <= height; ++line){
		dump_line(out, node, line);
		out.put('\n');
	}
	out.flush();
}

public:
void dump(std::ostream&out){
	dump_node(out, root);
}

Man könnte den Ausgabealgorithmus sicher noch sehr viel verbessern was die Geschwindigkeit betrifft. Ich glaube jedoch kaum, dass er bei großen Bäumen überhaupt zum Einsatz kommen wird und deshalb werde ich dies sein lassen.

Tod dem Zeigersalat

Bei Bäumen ist es auch leicht mit den Zeiger durcheinander zu kommen. Eine Funktion die testet ob der Baum so überhaupt richtig sein kann hilft viele Fehler zu finden. Man testet zum Beispiel ob der Elternknoten des Kindes eines Knoten dieser selbst ist.

private:
bool is_wellformed(Node*node){
	if(node == 0)
		return true;
	if(*get_parent_ptr(node) != node)
		return false;
	if(!is_wellformed(node->left))
		return false;
	if(!is_wellformed(node->right))
		return false;
	return true;
}

Mit Hilfe eines assert(is_wellformed(root)) können wir sehr viele Fehler vorzeitig abfangen. Durch ein Paar geschickte gesetzte Breakpoints innerhalb dieser Funktion kann man auch sehr genau erfahren welcher Zeiger falsch ist.

Kopiekonstruktor, Destruktor und Zuweisung

Da ein Baum keine triviale Datenstruktur ist muss man auch den Kopiekonstruktor, den Destruktor und den Zuweisungsoperator implementieren.

Als erstes implementiere ich den Destruktor. Dieser ist leicht rekursive zu realisieren.

private:
static void destroy_node(Node*node){
	if(node){
		destroy_node(node->left);
		destroy_node(node->right);
		delete node;
	}
}

public:
~Tree(){
	destroy_node(root);
}

Bei sehr großen Bäumen kann es im Destruktor zu einem Stapelüberlauf kommen. In diesem Fall muss man ihn iterative formulieren. Die Idee ist immer das Blatt zu löschen das den kleinsten Wert aller Blätter darstellt also sich auf der linken Seite des Baums befindet. Durch das Abschneiden der ersten Blätter entstehen neue und der Baum schrumpft zusammen, bis dass er schlussendlich nicht mehr existiert.

~Tree(){
	Node*now = root;
	while(now){	
		if(now->left)
			now = now->left;
		else if(now->right)
			now = now->right;
		else{
			Node*next = now->parent;
			*get_parent_ptr(now) = 0;
			delete now;
			now = next;
		}
	}
}

Der Kopiekonstruktor kann auch rekursive implementiert werden man muss jedoch aufpassen ob eine Ausnahme fliegt oder nicht. Dies wird schnell unüberschitlich und fehleranfällig. Darum bevorzuge ich die iterative Version. Die Idee ist den alten und neuen Baum so durchzulaufen wie wir es im Destruktor tuen und dabei alle Knoten klonen welche im alten Baum vorhanden sind jedoch nicht im neuen.

Mit dieser Methode ist der Baum immer in einem gesundem Zustand und kann vom Destruktor auch im unvollendeten Zustand gelöscht werden. Falls eine Ausnahme fliegt brauchen wir nur den Destruktor mit der Arbeit zu beauftragen den halbfertigen Baum zu löschen.

Tree(const Tree&other){
	if(!other.is_empty()){
		root = new Node(other.root->value);
		try{
			Node
				*now = root,
				*other_now = other.root;
			while(other_now){
				if(other_now->left && !now->left){
					now->left = new Node(other_now->left->value);
					now->left->parent = now;
					now = now->left;
					other_now = other_now->left;
				}else if(other_now->right && !now->right){
					now->right = new Node(other_now->right->value);
					now->right->parent = now;
					now = now->right;
					other_now = other_now->right;
				}else{
					now = now->parent;
					other_now = other_now->parent;
				}
				is_wellformed(root);
			}
		}catch(...){
			this->~Tree();
			throw;
		}
	}
}

Der Zuweisungs-Operator kann leicht mit Hilfe des Swap-Idioms implementiert werden.

public:
void swap(Tree&other){
	std::swap(root, other.root);
}

Tree&operator=(const Tree&other){
	Tree temp(other);
	swap(temp);
	return *this;
}

Suchen

Implementieren wir nun die Suchfunktion. Da wir die innere Struktur der Klasse verstecken wollen stellen wir dem Außenstehenden nur eine Funktion zur Verfügung die testet ob ein Wert im Baum enthalten ist.

Man sollte bemerken, dass man es dem Benutzer nicht erlauben sollte, dass der Wert des Knoten verändert wird da dies die Position im Baum durcheinander bringen kann. Wenn er dies beabsichtig, dann soll er den alten Wert rauslöschen und den neuen einfügen.

Durch den Einsatz von Templates spare ich mir eine const und eine nicht-const Version zu schreiben.

private:
template<class NodeT>
static NodeT*search(NodeT*root, const T&value){
	NodeT*now = root;
	while(now){
		if(value < now->value)
			now = now->left;
		else if(now->value < value)
			now = now->right;
		else
			return now;
	}
	return 0;
}

public:
bool contains(const T&t)const{
	return search(root, t);
}

Einfügen

Um ein Element einzufügen verfahren wir ähnlich jedoch behalten wir uns wo der Elternknoten ist.

public:
bool insert(const T&value){
	Node
		*parent = 0,
		*now = root;
	bool is_left_child = false;
	while(now){
		parent = now;
		if(value < now->value){
			is_left_child = true;
			now = now->left;
		}else if(now->value < value){
			is_left_child = false;
			now = now->right;
		}else
			return false; // Das Element ist bereits im Baum
	}
	Node*new_node = new Node(value);
	new_node->parent = parent;

	if(parent == 0)
		root = new_node;
	else if(is_left_child)
		parent->left = new_node;
	else
		parent->right = new_node;

	// Wenn etwas mit den Zeigern falsch ist
	// dann knallt es wahrscheinlich hier.
	assert(is_wellformed(root));
	return true;
}

Austauschen

Knoten können durch austauschen der Werte getauscht werden. Dies ist sicherlich der beste Weg falls man Ganzzahlen speichern will. Es gibt jedoch auch Klassen welche sehr teuer zu tauschen sind oder die gar nicht getauscht werden können. Es ist auch möglich, dass es Zeiger auf das Element gibt die außerhalb des Baums liegen und verändert werden müssten, oder dass beim Tauschen eine Ausnahme fliegen kann.

Diese Probleme kann man dadurch umgehen, dass man die Zeiger der Knoten neuverbindet. Hierbei ist der allgemeine Fall vom Fall wo einer der beiden Knoten das Kind des anderen ist zu unterscheiden.

Man sollte beachten, dass das Tauschen von Knoten wahrscheinlich die Ordnung im Baum durcheinander bringt. Man sollte also sichergehen, dass diese nachdem diese Funktion ihre Arbeit getan hat wiederhergestellt wird.

private:
void swap_near_nodes(Node*child, Node*parent){
	// Als erstes passen wir den unbeteiligten Großelternknoten an.
	*get_parent_ptr(parent) = child;

	// Anschließend werden die Kind- und Elternzeiger ausgetauscht.
	std::swap(parent->left, child->left);
	std::swap(parent->right, child->right);
	std::swap(parent->parent, child->parent);

	// Da eines der Kinder getauscht wird benötigt es eine
	// sonder Behandlung.
	if(child->left == child)
		child->left = parent;
	else
		child->right = parent;

	// Nun sind alle Kindzeiger richtig und die Elternzeiger können
	// dem angepasst werden.
	if(child->left)
		child->left->parent = child;
	if(child->right)
		child->right->parent = child;
	if(parent->left)
		parent->left->parent = parent;
	if(parent->right)
		parent->right->parent = parent;

	// Na wer ist sich noch sicher ob wir nicht
	// bereits Zeigersalat haben? Besser testen!
	assert(is_wellformed(root));
}

void swap_far_nodes(Node*a, Node*b){
	// Zuerst updaten wir die Zeiger der Eltern
	*get_parent_ptr(a) = b;
	*get_parent_ptr(b) = a;

	// Danach der Kinder
	if(a->left)
		a->left->parent = b;
	if(a->right)
		a->right->parent = b;
	if(b->left)
		b->left->parent = a;
	if(b->right)
		b->right->parent = a;

	// Und als letztes die der beiden Knoten
	std::swap(a->left, b->left);
	std::swap(a->right, b->right);
	std::swap(a->parent, b->parent);

	assert(is_wellformed(root));
}

void swap_nodes(Node*a, Node*b){
	if(a->parent == b)
		swap_near_nodes(a, b);
	else if(b->parent == a)
		swap_near_nodes(b, a);
	else
		swap_far_nodes(a, b);
}

Minimum und Maximum

Das Minimum eines Unterbaums findet man indem man einfach den links Zeigern folgt bis es nicht mehr geht. Ähnlich geht man beim Maximum vor.

private:
template<class NodeT>
static NodeT*get_min(NodeT*node){
	NodeT*now = node;
	while(now->left)
		now = now->left;
	return now;
}

template<class NodeT>
static NodeT*get_max(NodeT*node){
	NodeT*now = node;
	while(now->right)
		now = now->right;
	return now;
}

public:
const T&min()const{
	return get_min(root)->value;
}

const T&max()const{
	return get_max(root)->value;
}

Löschen

Wie bereits gesagt gibt es drei verschiedene Arten von Knoten im Baum und wie man vorgeht hängt von Art zu Art ab.

private:
void remove(Node*node){
	// Ein Blatt
	if(!node->left && !node->right){
		*get_parent_ptr(node) = 0;
		delete node;
	}
	// Nur ein Kind
	else if(node->left && !node->right){
		*get_parent_ptr(node) = node->left;
		node->left->parent = node->parent;
		delete node;
	}else if(!node->left && node->right){
		*get_parent_ptr(node) = node->right;
		node->right->parent = node->parent;
		delete node;
	}
	// Zwei Kinder
	else{
		Node*other = get_max(node->left);
		swap_nodes(node, other);
		// Löschen des Knoten durch benutzen von einer 
		// der beiden anderen Methoden 
		remove(node);
	}
	assert(is_wellformed(root));
}
public:
bool remove(const T&value){
	Node*node = search(value);
	if(node){
		remove(node);
		return true;
	}else
		return false;
}

Rotationen

Bei der Implementation von Rotationen kommt sehr leicht mit den Zeigern durcheinander. Darum ist es sehr nützlich den Baum zuerst zu zeichenen.

Die Rotationsfunktion gibt die neue Wurzel zurück.

private:
Node*rotate_left(Node*A){
	Node
		**root_ptr = get_parent_ptr(A),
		*parent = A->parent,
		*B = A->right,
		*X = A->left,
		*Y = B->left,
		*Z = B->right;

	*root_ptr = B;
	B->left = A;
	B->right = Z;
	A->left = X;
	A->right = Y;

	B->parent = parent;
	A->parent = B;
	if(Z)
		Z->parent = B;
	if(X)
		X->parent = A;
	if(Y)
		Y->parent = A;

	return B;
}

private:
Node*rotate_right(Node*A){
	Node
		**root_ptr = get_parent_ptr(A),
		*parent = A->parent,
		*B = A->left,
		*X = B->left,
		*Y = B->right,
		*Z = A->right;

	*root_ptr = B;
	B->left = X;
	B->right = A;
	A->left = Y;
	A->right = Z

	B->parent = parent;
	A->parent = B;
	if(Z)
		Z->parent = A;
	if(X)
		X->parent = B;
	if(Y)
		Y->parent = A;

	return B;
}

Ausblick

In diesem Artikel habe ich gezeigt wie Suchbäume aufgebaut sind und wie sie funktionieren jedoch auch ihre Schwächen. Der Suchbaum so wie er in diesem Artikel beschrieben wird ist recht nutzlos weil er sehr einfach aus dem Gleichgewicht kommt. Um dagegen vorzugehen gibt es verschiedene Ansätze: AVL-Baum, Rot-Schwarz Baum oder Splay-Baum um nur einige zu nennen. Alle haben ihre Stärken und Schwächen. In den nächsten Artikeln werde den hier vorgestellten Baum zu diesen Spezialbäumen umbauen.

Jester

Noch ein paar Kleinigkeiten.

- Du erwähnst kurz Hash-Tabellen. Die sind auch insofern kein Ersatz für das was Du vorstellst, als sie nicht sortiert sind und man damit zum beispiel nicht das nächstgrößere enthaltene element zu einem gegebenen Schlüssel finden kann. Da darfste imho ruhig noch ein bißchen Werbung für das Thema machen.

- Du stellst eine Liste von Werten als Baum dar. Bei Liste denke ich in nem algorithmischen Kontext immer an die Datenstruktur Liste. Vielleicht ne Menge? Vielleicht isses aber auch nur mein persönliches Problem.

- Beim Einfügen sagst Du, man müsse Laufen bis man zu einem Knoten kommt, der noch ein Kind frei hat. Das stimmt so nicht. Eventuell muß man weiter runter als bis zum ersten Knoten der noch keine zwei Kinder hat.

- Afaik heißt das Idiom "Copy&Swap-Idiom".

Der Teil über Rotationen paßt imho nicht mehr so gut ins Gesamtkonzept, da der AVL-Baum fehlt. Wie wäre es stattdessen lieber das auffädeln der Knoten auf eine doppelt verkettete sortierte Liste dazuzunehmen und nen Iterator mit anzugeben?

Alles nur Vorschläge!
Weiter so, sehr cooler Artikel.
Jester

Ben04

Jester schrieb:

- Du erwähnst kurz Hash-Tabellen. Die sind auch insofern kein Ersatz für das was Du vorstellst, als sie nicht sortiert sind und man damit zum beispiel nicht das nächstgrößere enthaltene element zu einem gegebenen Schlüssel finden kann.

In Hash-Tabellen kann man schon schnell Werte speichern und suchen. Sie unterscheiden sich natürlich darin, dass sie keine Ordnung vorgeben aber wie gesagt : Das soll nicht das Thema sein. Wann man was einsetzen soll ist ein ganz eigenes Thema und einen Artikel wert. Ein AVL-Baum ist ja noch nicht einmal immer dem ganz banalen Array überlegen. Es gibt noch sehr viel zu schreiben wenn man will.

Jester schrieb:

Da darfste imho ruhig noch ein bißchen Werbung für das Thema machen.

Wo würdest du die unterbringen?

Jester schrieb:

- Du stellst eine Liste von Werten als Baum dar. Bei Liste denke ich in nem algorithmischen Kontext immer an die Datenstruktur Liste. Vielleicht ne Menge? Vielleicht isses aber auch nur mein persönliches Problem.

Anfangs hatte ich auch Menge da stehen. Das Problem das ich mit dem Wort habe ist, dass es mathematisch vorbelastet ist und daher komplex erscheint für nicht Mathematiker. Ich will den Leser doch nicht schon in der ersten Zeile vergrauen. Der soll wenigstens bis zum AVL-Baum lesen. Array ist einfach fachlich zu fehl am Platz, da bleibt nur noch Liste oder kennst du noch ein anderes Wort?

Jester schrieb:

- Beim Einfügen sagst Du, man müsse Laufen bis man zu einem Knoten kommt, der noch ein Kind frei hat. Das stimmt so nicht. Eventuell muß man weiter runter als bis zum ersten Knoten der noch keine zwei Kinder hat.

Den Fehler werde ich verbessern.

Jester schrieb:

- Afaik heißt das Idiom "Copy&Swap-Idiom".

Das Idiom hat sehr viele Namen. Gib nur mal bei google "Swap Idiom" ein. Copy&Swap klingt aber besser also werde ich es übernehmen.

Jester schrieb:

Der Teil über Rotationen paßt imho nicht mehr so gut ins Gesamtkonzept, da der AVL-Baum fehlt.

Das ist schon richtig aber ich will sie aber nicht rausnehmen da sie an sich nichts mit dem AVL Baum zu tun haben. Egal was für eine Baumart, Rotationen sind immer mit im Spiel und sie in jedem Artikel zu wiederholen schafft nur Verwirrung. Desweiteren schaffen sie eine Art Spannung wie es denn weiter geht.

Jester schrieb:

Wie wäre es stattdessen lieber das auffädeln der Knoten auf eine doppelt verkettete sortierte Liste dazuzunehmen und nen Iterator mit anzugeben?

Ich hab mal in der libstdc++ nachgesehen. Die nehmen dafür keine sortierte Liste sondern durchwandern den Baum. An sich ist es auch kein sonderlich komplizierter Algorithmus um das nächste Element zu finden. Er hat eine gewisse Ähnlichkeit mit der dem im Copyctor zu Einsatz kommt. Und den gesamten Baum zu durchlaufen hat eine Laufzeit von O(n) da jede Kante genau zwei mal begangen wird und es n-1 Kanten gibt.

Der Einsatz eines Iterator gefällt mir nicht. Viele Leser werden nicht genug mit dem Thema vertraut sein um folgen zu können. Das gehört in einen eigenen Artikel. Ich glaub ich werde mich auf eine Funktion zum finden des nächsten Elements beschränken. Also so in etwa T next(const T&).

Ben04

Fehl in folgender Version inhaltlich noch etwas?

=====

Suchen das Problem

Sei es eine Datenbank oder ein Dateisystem: Das Suchen nach Werten ist eines der häufigsten Probleme in der Informatik. Das im Grunde einfach klingende Problem erweist sich als ein außerordentlich komplexes Biest sobald man über den Tellerrand der trivialen Ansätze blickt.

Für viele Anwendungen recht ein Array in das man sämtliche Werte rein schmeißt und anschließend von Anfang bis Ende durchläuft. Wenn die Datenbank aber wächst dann wird dieser Ansatz aber unvertretbar langsam. Der erste Verbesserungsvorschlag wird dann wohl sein das Array zu sortieren und es dann mit der Hilfe einer binären Suche zu durchwühlen. Solange sich die Element des Arrays nur wenig verändert ist dieser Ansatz gut andernfalls stößt auch er an seine Grenzen.

Wer noch mehr Geschwindigkeit braucht der muss sich vom einfachen Array verabschieden und auf eine andere Datenstruktur ausweichen. Ein Ansatz ist die Werte in einer Hash-Tabelle zu speichern. Dies wird aber nicht das Thema dieses Artikels sein, vielmehr wird es eine Weiterentwickelung der binären Suche sein: Der binäre Suchbaum.

Binäre Suchbäume

Binäre Bäume können dazu genutzt werden um eine Liste so darzustellen, dass man schnell nach einem Element suchen kann und schnell welche einfügen oder löschen kann. Dazu weist man jedem Knoten ein Element der Liste zu und sorgt dafür, dass sämtliche Elemente des linken Unterbaums kleiner und die des rechten Unterbaums größer sind.

Suchen

Um ein Element zu suchen beginnt man die Suche an der Wurzel. Falls die Wurzel den Wert darstellt ist man schon fertig. Sonst vergleicht man ob der gesuchte Wert kleiner oder größer ist und setzt seine Suche im entsprechenden Unterbaum fort. Wenn man auf der untersten Ebene des Baums angelangt ist ohne den Wert gefunden zu haben dann ist er nicht im Baum enthalten.

In folgendem Beispiel wird die 7 gesucht.

Um ein Element zu finden müssen wir im schlimmsten Fall von der Wurzel bis zur untersten Ebene wandern. Im besten Fall hat der Baum eine Höhe die logarithmisch von der Anzahl seiner Elemente abhängt. Dies gibt also in etwa eine Laufzeitkomplexität von O(log(n)) um ein Element zu suchen wenn wir ungünstige Bäume ignorieren. n ist die Gesamtanzahl der Elemente im Baum.

Maximum und Minimum

Da die Elemente geordnet im Baum vorliegen ist das kleinste Element das was sich am linken Ende des Baums befindet. Man findet es indem man die Suche an der Wurzel beginnt und sie dann nach links fort setzt bis es nicht mehr geht. Das größte Element findet man ähnlich, nur dass man bei dem nach rechts wandern muss.

Im schlimmsten Fall müssen wir den Baum von oben nach unten durchwandern also ist die Laufzeitkomplexität dieselbe wie die bei der Suche eines Elements also O(log(n)).

Durchwandern

Um die Elemente eines Baums in geordneter Reihenfolge zu durchwandern beginnt man seine Suche beim Minimum und sucht dann immer das nächste größere Element, bis dass man beim Maximum angelangt ist.

Wo man suchen muss um das nächste Element zu finden hängt von der Position im Baum ab. Genauer gesagt hängt es davon ab ob der Ausgangsknoten ein rechtes Kind besitzt oder nicht.

Knoten mit rechtem Kind

In diesem Fall ist das nächste Element das Minimum des rechten Unterbaums.

In folgendem Beispiel suchen wir das Element das der 5 folgt. Dazu begeben wir uns zuerst in den rechten Unterbaum und dann suchen wir das Minimum indem wir solange nach links wandern wie nur möglich.

Knoten ohne rechtes Kind

Falls es kein rechtes Kind gibt so muss man Richtung Wurzel des Baums klettern. Falls man unterwegs auf einen Knoten stößt welchen man von seinem linken Kind aus erreicht hat so hat man das nächste Element gefunden.

Der Algorithmus um den Baum in der anderen Richtung zu durchwandern ist genau spiegelverkehrt darum werde ich nicht weiter darauf eingehen.

Jede Kante wird genau zweimal begangen wenn man das Suchen des Anfangsknoten und Endknoten hinzuzählt. Da es nur einen Knoten mehr gibt als Kanten hat das Durchwandern eine Laufzeitkomplexität von O(n). Um das nächste Element zu finden muss man im schlimmsten Fall von der untersten Ebene bis zur Wurzel oder andersrum wandern. Diese hat Operation hat also eine Laufzeitkomplexität von O(log(n)) im ungünstigsten Fall.

Es gibt einen alternativen Ansatz der die Knoten noch zusätzlich zum Baum in einer geordneten verketteten Liste zusammen strikt. Dies beschleunigt das Durchwandern um einen konstanten Faktor und sorgt dafür, dass das Suchen des nächsten Elements immer eine konstante Laufzeit besitzt. Der Preis ist allerdings der Mehraufwand um die verkettete Liste zu verwalten. Falls man den Baum oft durchwandern muss sollte man diese Option in betracht ziehen.

Einfügen

Um einen Wert einzufügen geht man ähnlich vor wie bei der normalen Suche. Man wandert solange nach unten, bis man einen Knoten gefunden hat der noch ein Kind, an der richtigen Seite, frei hat.

In folgendem Beispiel wird die 8 eingefügt.

Da es sich an sich um den gleichen Algorithmus handelt wie bei er Suche ist auch die Komplexität die gleiche und zwar O(log(n)).

Löschen

Als erstes sucht man den zu löschenden Knoten nach bekannter Methode. Wie man danach vorgeht hängt von der Position im Baum ab, das heißt wie viele Kinder der Knoten hat.

Löschen eines Knoten ohne Kinder

Um ein Blatt zu löschen trennt man es einfach vom Elternknoten ab.

Folgendes Beispiel zeigt wie die 5 aus dem Baum gelöscht wird:

Löschen eines Knoten mit einem Kind

Man trennt den Knoten von Kind und von Elternknoten ab. Anschließend verbindet man Kind und Elternknoten.

Im nächsten Beispiel wird die 3 gelöscht.

Löschen eines Knoten mit zwei Kindern

Man sucht das nächst kleinere Element. Dieses Element ist immer ein Blatt oder hat nur ein Kind weil es kein rechtes Kind haben kann da es sich um den Maximum des linken Unterbaums handelt. Ein kleineres Element gibt es auch immer da sonst der Knoten höchsten ein Kind hätte. Es kann also mit einer der beiden oben genannten Operationen gelöscht werden. Man vertauscht den Knoten den man löschten will mit diesem und löscht ihn raus.

Da beide Werte direkt hintereinander in der Liste liegen wird die Ordnung auch nicht durch das Tauschen gestört, solange eines der beiden Elemente gelöscht wird.

In folgendem Beispiel wird die 7 gelöscht.

Alternative kann man auch das nachfolgende Element wählen und mit dem tauschen. Keine der beiden Methoden bringt aber wirklich einen Vorteil deswegen ist es an sich egal für welche man sich entscheidet.

Die Geschwindigkeit der eigentlichen Löschverfahren sind alle unabhängig von der Größe des Baums. Legendlich die Suche des zu löschenden Elements und die Suche des größten Elements hängen von der Größe ab, darum ist die Komplexität einer Löschoperation in etwa O(log(n)).

Ausbalancierte Bäume und die die es nicht sind

Eines der großen Probleme solcher Bäume ist, dass wenn die Reihenfolge der Einfügungen ungünstig ist der Baum sehr schnell aus dem Gleichgewicht kommt und zu einer Seite hinkt. Dies macht den Baum viel höher als nötig und somit die Suche viel langsamer da diese ja von der Höhe des Baums abhängt.

In folgendem Baum wird die 8 gesucht und der Arbeitsaufwand kommt schon nahe an den einer sequenziellen Suche heran.

Um dem entgegen zu wirken kann man Rotationen einsetzen.

Rotationen

Es gibt Rotationen nach links und welche nach rechts. Da die Operationen genau spiegelverkehrt sind werde ich nur auf die links Rotation eingehen.

Als erstes trennt man das linke Kind vom rechten Kind der Wurzel ab und anschießend auch das rechte Kind.

Danach wird das rechte Kind zur neuen Wurzel und die alte Wurzel wird ihr neues rechtes Kind. Das Enkelkind wird zum neuen rechten Kind der alten Wurzel.

Nun ist der Baum wieder im Gleichgewicht.

Man sagt links Rotation da das Gleichgewicht sich nach links verlagert. Man kann es sich wie eine Balkenwaage vorstellen welche man in das Gleichgewicht bringt indem man den Balken an einer anderen Stelle aufhängt.

Das Beispiel hinkt zwar da nach der Rotation beide Gewichte gleich schwer sind.

Die Geschwindigkeit einer Rotation hängt nicht von der Größe des Baums ab. Die Komplexität ist also O(1).

Das große Problem mit Rotationen ist zu wissen wann man sie einsetzen soll. Sie verbessern nämlich nicht immer die Darstellung eines Baums. Es gibt verschiedene Strategien um hier vorzugehen.

Implementierung

Das erste was man bei einer Implementierung festlegen muss ist die Darstellung. Die Knoten werden durch eine Struktur dargestellt und dann mit Pointern verbunden. Dies sieht in etwa so aus:

template<class T>
struct Node{
	Node*parent, *left, *right;
	T value;

	explicit Node(const T&value):
		parent(0), left(0), right(0), value(value){}
};

parent zeigt auf den Elternknoten. Falls es sich um die Wurzel handelt ist dieser NULL. left und right zeigen jeweils auf die Wurzel des linken oder rechten Unterbaums oder NULL falls es diesen nicht gibt.

Um zu verhindern, dass Unbefugte an unserem Baum rumbasteln wird dieser durch eine Klasse gekapselt. Dies sieht dann in etwa folgendermaßen aus:

template<class T>
class Tree{
private:
	struct Node{
		Node*parent, *left, *right;
		T value;

		explicit Node(const T&value):
			parent(0), left(0), right(0), value(value){}

	Node*root;
public:
	Tree():root(0){}

	bool is_empty()const{
		return !root;
	}
};

root zeigt dabei auf die Wurzel des Baumes oder NULL falls der Baum leer ist. Ob der Baum leer ist kann mittels is_empty überprüft werden.

Navigation

Um uns beim navigieren im Baum zu helfen wäre es sicher nicht verkehrt Funktionen zu schreiben die prüfen ob es sich um ein linkes oder rechtes Kind handelt.

private:
static bool is_left_child(const Node*node){
	if(node->parent == 0)
		return false; // Die Wurzel ist kein Kind
	else
		return node->parent->left == node;
}

static bool is_right_child(const Node*node){
	if(node->parent == 0)
		return false; // Die Wurzel ist kein Kind
	else
		return node->parent->right == node;
}

Um die Position eines Knoten ändern zu können muss man auch einen einfachen Zugriff auf den Zeiger im Elternknoten haben.

private:
Node**get_parent_ptr(Node*node){
	if(node->parent == 0)
		return &root;
	else if(is_left_child(node))
		return &node->parent->left;
	else
		return &node->parent->right;
}

Debuggen

Da es sehr schwer ist einen Baum fehlerfrei zu implementieren müssen wir uns auch Gedanken machen wie wir ihn debuggen. Wer sich nur für den eigentlichen Code interessiert kann diesen Teil des Artikels getrost überspringen.

Konsolenausgabe

Eine Funktion die den Baum einfach komplett auf die Konsole ausgibt wäre sehr nützlich da die meisten Debugger nicht sonderlich gut sind um solche Datenstrukturen zu inspizieren und nur Zeigersalat anzeigen.

Ziel ist es den Baum ähnlich wie auf den Grafiken oben auszugeben. Dazu müssen wir als erstes festlegen welche Informationen über einen Knoten ausgegeben werden. Dies mach folgende Funktion:

private:
static std::string format_label(Node*node){
	if(node){
		std::ostringstream out;
		out<<node->value;
		return out.str();
	}else
		return "";
}

Wir müssen auch wissen wie breit und hoch der Baum wird damit wir wissen genügend Platz frei gelassen werden muss. Folgende Funktionen berechnen diese Informationen für den Baum und jeden Unterbaum.

private:
static unsigned get_height(Node*node){
	if(!node)
		return 0;
	unsigned left_height = 0, right_height = 0;

	if(node->left)
		left_height = get_height(node->left);
	if(node->right)
		right_height = get_height(node->right);

	// Der höchste Unterbaum bestimmt die Gesamthöhe
	return std::max(left_height, right_height) + 1;
}

static unsigned get_width(Node*node){
	if(!node)
		return 0;
	unsigned left_width = 0, right_width = 0;

	if(node->left)
		left_width = get_width(node->left);
	if(node->right)
		right_width = get_width(node->right);

	return left_width + format_label(node).length() + right_width;
}

Da wir nur zeilenweise auf die Konsole schreiben können müssen wir den Baum auch Zeile für Zeile ausgeben.

private:
static void dump_spaces(std::ostream&out, unsigned count){
	for(unsigned i=0; i<count; ++i)
		out.put(' ');
}

static void dump_line(std::ostream&out, Node*node, unsigned line){
	if(!node)
		return;
	if(line == 1){
		// Die Wurzel der Unterbaums soll ausgegeben werden
		dump_spaces(out, get_width(node->left));
		out<<format_label(node);
		dump_spaces(out, get_width(node->right));
	}else{
		// Im linken Unterbaum ist die Wurzel um eins niedriger und darum verändert
		// sich die Zeilennumerirung.
		dump_line(out, node->left, line-1);
		dump_spaces(out, format_label(node).length());
		dump_line(out, node->right, line-1);
	}
}

Nun benötigen wir noch eine Möglichkeit den gesamten Baum auszugeben und nicht nur eine Zeile.

private:
static void dump_node(std::ostream&out, Node*node){
	for(unsigned line=1, height = get_height(node); line <= height; ++line){
		dump_line(out, node, line);
		out.put('\n');
	}
	out.flush();
}

public:
void dump(std::ostream&out){
	dump_node(out, root);
}

Man könnte den Ausgabealgorithmus sicher noch sehr viel verbessern was die Geschwindigkeit betrifft. Ich glaube jedoch kaum, dass er bei großen Bäumen überhaupt zum Einsatz kommen wird und deshalb werde ich dies sein lassen.

Tod dem Zeigersalat

Bei Bäumen ist es auch leicht mit den Zeiger durcheinander zu kommen. Eine Funktion die testet ob der Baum so überhaupt richtig sein kann hilft viele Fehler zu finden. Man testet zum Beispiel ob der Elternknoten des Kindes eines Knoten dieser selbst ist.

private:
bool is_wellformed(Node*node){
	if(node == 0)
		return true;
	if(*get_parent_ptr(node) != node)
		return false;
	if(!is_wellformed(node->left))
		return false;
	if(!is_wellformed(node->right))
		return false;
	return true;
}

Mit Hilfe eines assert(is_wellformed(root)) können wir sehr viele Fehler vorzeitig abfangen. Durch ein Paar geschickte gesetzte Breakpoints innerhalb dieser Funktion kann man auch sehr genau erfahren welcher Zeiger falsch ist.

Kopiekonstruktor, Destruktor und Zuweisung

Da ein Baum keine triviale Datenstruktur ist muss man auch den Kopiekonstruktor, den Destruktor und den Zuweisungsoperator implementieren.

Als erstes implementiere ich den Destruktor. Dieser ist leicht rekursive zu realisieren.

private:
static void destroy_node(Node*node){
	if(node){
		destroy_node(node->left);
		destroy_node(node->right);
		delete node;
	}
}

public:
~Tree(){
	destroy_node(root);
}

Bei sehr großen Bäumen kann es im Destruktor zu einem Stapelüberlauf kommen. In diesem Fall muss man ihn iterative formulieren. Die Idee ist immer das Blatt zu löschen das den kleinsten Wert aller Blätter darstellt also sich auf der linken Seite des Baums befindet. Durch das Abschneiden der ersten Blätter entstehen neue und der Baum schrumpft zusammen, bis dass er schlussendlich nicht mehr existiert.

~Tree(){
	Node*now = root;
	while(now){	
		if(now->left)
			now = now->left;
		else if(now->right)
			now = now->right;
		else{
			Node*next = now->parent;
			*get_parent_ptr(now) = 0;
			delete now;
			now = next;
		}
	}
}

Der Kopiekonstruktor kann auch rekursive implementiert werden man muss jedoch aufpassen ob eine Ausnahme fliegt oder nicht. Dies wird schnell unübersichtlich und fehleranfällig. Darum bevorzuge ich die iterative Version. Die Idee ist den alten und neuen Baum so zu durchlaufen wie wir es im Destruktor tun und dabei alle Knoten klonen welche im alten Baum vorhanden sind jedoch nicht im neuen.

Mit dieser Methode ist der Baum immer in einem gesunden Zustand und kann vom Destruktor auch im unvollendeten Zustand gelöscht werden. Falls eine Ausnahme fliegt brauchen wir nur den Destruktor mit der Arbeit zu beauftragen den halbfertigen Baum zu löschen.

Tree(const Tree&other){
	if(!other.is_empty()){
		root = new Node(other.root->value);
		try{
			Node
				*now = root,
				*other_now = other.root;
			while(other_now){
				if(other_now->left && !now->left){
					now->left = new Node(other_now->left->value);
					now->left->parent = now;
					now = now->left;
					other_now = other_now->left;
				}else if(other_now->right && !now->right){
					now->right = new Node(other_now->right->value);
					now->right->parent = now;
					now = now->right;
					other_now = other_now->right;
				}else{
					now = now->parent;
					other_now = other_now->parent;
				}
				is_wellformed(root);
			}
		}catch(...){
			this->~Tree();
			throw;
		}
	}
}

Der Zuweisungs-Operator kann leicht mit Hilfe des Copy&Swap-Idioms implementiert werden.

public:
void swap(Tree&other){
	std::swap(root, other.root);
}

Tree&operator=(const Tree&other){
	Tree temp(other);
	swap(temp);
	return *this;
}

Suchen

Implementieren wir nun die Suchfunktion. Da wir die innere Struktur der Klasse verstecken wollen stellen wir dem Außenstehenden nur eine Funktion zur Verfügung die testet ob ein Wert im Baum enthalten ist.

Man sollte bemerken, dass man es dem Benutzer nicht erlauben sollte, dass der Wert des Knoten verändert wird da dies die Position im Baum durcheinander bringen kann. Wenn er dies beabsichtig, dann soll er den alten Wert rauslöschen und den neuen einfügen.

Durch den Einsatz von Templates spare ich mir eine const und eine nicht-const Version zu schreiben.

private:
template<class NodeT>
static NodeT*search(NodeT*root, const T&value){
	NodeT*now = root;
	while(now){
		if(value < now->value)
			now = now->left;
		else if(now->value < value)
			now = now->right;
		else
			return now;
	}
	return 0;
}

public:
bool contains(const T&t)const{
	return search(root, t);
}

Einfügen

Um ein Element einzufügen verfahren wir ähnlich jedoch behalten wir uns wo der Elternknoten ist.

public:
bool insert(const T&value){
	Node
		*parent = 0,
		*now = root;
	bool is_left_child = false;
	while(now){
		parent = now;
		if(value < now->value){
			is_left_child = true;
			now = now->left;
		}else if(now->value < value){
			is_left_child = false;
			now = now->right;
		}else
			return false; // Das Element ist bereits im Baum
	}
	Node*new_node = new Node(value);
	new_node->parent = parent;

	if(parent == 0)
		root = new_node;
	else if(is_left_child)
		parent->left = new_node;
	else
		parent->right = new_node;

	// Wenn etwas mit den Zeigern falsch ist
	// dann knallt es wahrscheinlich hier.
	assert(is_wellformed(root));
	return true;
}

Austauschen

Knoten können durch austauschen der Werte getauscht werden. Dies ist sicherlich der beste Weg falls man Ganzzahlen speichern will. Es gibt jedoch auch Klassen welche sehr teuer zu tauschen sind oder die gar nicht getauscht werden können. Es ist auch möglich, dass es Zeiger auf das Element gibt die außerhalb des Baums liegen und verändert werden müssten, oder dass beim Tauschen eine Ausnahme fliegen kann.

Diese Probleme kann man dadurch umgehen, dass man die Zeiger der Knoten neuverbindet. Hierbei ist der allgemeine Fall vom Fall wo einer der beiden Knoten das Kind des anderen ist zu unterscheiden.

Man sollte beachten, dass das Tauschen von Knoten wahrscheinlich die Ordnung im Baum durcheinander bringt. Man sollte also sichergehen, dass diese nachdem diese Funktion ihre Arbeit getan hat wiederhergestellt wird.

private:
void swap_near_nodes(Node*child, Node*parent){
	// Als erstes passen wir den unbeteiligten Großelternknoten an.
	*get_parent_ptr(parent) = child;

	// Anschließend werden die Kind- und Elternzeiger ausgetauscht.
	std::swap(parent->left, child->left);
	std::swap(parent->right, child->right);
	std::swap(parent->parent, child->parent);

	// Da eines der Kinder getauscht wird benötigt es eine
	// sonder Behandlung.
	if(child->left == child)
		child->left = parent;
	else
		child->right = parent;

	// Nun sind alle Kindzeiger richtig und die Elternzeiger können
	// dem angepasst werden.
	if(child->left)
		child->left->parent = child;
	if(child->right)
		child->right->parent = child;
	if(parent->left)
		parent->left->parent = parent;
	if(parent->right)
		parent->right->parent = parent;

	// Na wer ist sich noch sicher ob wir nicht
	// bereits Zeigersalat haben? Besser testen!
	assert(is_wellformed(root));
}

void swap_far_nodes(Node*a, Node*b){
	// Zuerst updaten wir die Zeiger der Eltern
	*get_parent_ptr(a) = b;
	*get_parent_ptr(b) = a;

	// Danach der Kinder
	if(a->left)
		a->left->parent = b;
	if(a->right)
		a->right->parent = b;
	if(b->left)
		b->left->parent = a;
	if(b->right)
		b->right->parent = a;

	// Und als letztes die der beiden Knoten
	std::swap(a->left, b->left);
	std::swap(a->right, b->right);
	std::swap(a->parent, b->parent);

	assert(is_wellformed(root));
}

void swap_nodes(Node*a, Node*b){
	if(a->parent == b)
		swap_near_nodes(a, b);
	else if(b->parent == a)
		swap_near_nodes(b, a);
	else
		swap_far_nodes(a, b);
}

Minimum und Maximum

Das Minimum eines Unterbaums findet man indem man einfach den links Zeigern folgt bis es nicht mehr geht. Ähnlich geht man beim Maximum vor.

private:
template<class NodeT>
static NodeT*get_min(NodeT*node){
	NodeT*now = node;
	while(now->left)
		now = now->left;
	return now;
}

template<class NodeT>
static NodeT*get_max(NodeT*node){
	NodeT*now = node;
	while(now->right)
		now = now->right;
	return now;
}

public:
const T&min()const{
	return get_min(root)->value;
}

const T&max()const{
	return get_max(root)->value;
}

Durchwandern

Um dem Benutzer die Möglichkeit zu geben den Baum zu durchwandern bietet sich der Einsatz von Iteratoren förmlich an. Da ich mich in diesem Artikel allerdings auf die Implementierung des Baum beschränken möchte und nicht eine Schnelleinführung zum Thema Iteratoren geben möchte werde ich nur eine Funktion implementieren die den nächst größeren Wert sucht. next nimmt einen Wert als Parameter und gibt einen Zeiger auf das nächste Element zurück oder ein NULL Zeiger falls der Parameter das Maximum war oder ein Wert der sich gar nicht im Baum befindet. prev ist eine ähnliche Funktion die jedoch das nächst kleinere Element sucht.

private:
template<class NodeT>
static NodeT*get_next_node(NodeT*now){
	if(now->right)
		return get_min(now->right);
	else{
		while(now){
			if(is_left_child(now))
				return now->parent;
			else
				now = now->parent;
		}
		return 0; // Wir sind am Ende angekommen
	}
}

template<class NodeT>
static NodeT*get_prev_node(NodeT*now){
	if(now->left)
		return get_max(now->left);
	else{
		while(now){
			if(is_right_child(now))
				return now->parent;
			else
				now = now->parent;
		}
		return 0; // Wir sind am Anfang angekommen
	}
}

public:
const T*next(const T&value)const{
	const Node*now = search(root, value);
	if(!now)
		return 0;
	now = get_next_node(now);
	if(now)
		return &now->value;
	else
		return 0;
}

const T*prev(const T&value)const{
	const Node*now = search(root, value);
	if(!now)
		return 0;
	now = get_prev_node(now);
	if(now)
		return &now->value;
	else
		return 0;
}

Löschen

Wie bereits gesagt gibt es drei verschiedene Arten von Knoten im Baum und wie man vorgeht hängt von Art zu Art ab.

private:
void remove(Node*node){
	// Ein Blatt
	if(!node->left && !node->right){
		*get_parent_ptr(node) = 0;
		delete node;
	}
	// Nur ein Kind
	else if(node->left && !node->right){
		*get_parent_ptr(node) = node->left;
		node->left->parent = node->parent;
		delete node;
	}else if(!node->left && node->right){
		*get_parent_ptr(node) = node->right;
		node->right->parent = node->parent;
		delete node;
	}
	// Zwei Kinder
	else{
		Node*other = get_prev_node(node->left);
		swap_nodes(node, other);
		// Löschen des Knoten durch benutzen von einer 
		// der beiden anderen Methoden 
		remove(node);
	}
	assert(is_wellformed(root));
}
public:
bool remove(const T&value){
	Node*node = search(value);
	if(node){
		remove(node);
		return true;
	}else
		return false;
}

Rotationen

Bei der Implementierung von Rotationen kommt sehr leicht mit den Zeigern durcheinander. Darum ist es sehr nützlich den Baum zuerst zu zeichnen.

Die Rotationsfunktion gibt die neue Wurzel zurück.

private:
Node*rotate_left(Node*A){
	Node
		**root_ptr = get_parent_ptr(A),
		*parent = A->parent,
		*B = A->right,
		*X = A->left,
		*Y = B->left,
		*Z = B->right;

	*root_ptr = B;
	B->left = A;
	B->right = Z;
	A->left = X;
	A->right = Y;

	B->parent = parent;
	A->parent = B;
	if(Z)
		Z->parent = B;
	if(X)
		X->parent = A;
	if(Y)
		Y->parent = A;

	return B;
}

private:
Node*rotate_right(Node*A){
	Node
		**root_ptr = get_parent_ptr(A),
		*parent = A->parent,
		*B = A->left,
		*X = B->left,
		*Y = B->right,
		*Z = A->right;

	*root_ptr = B;
	B->left = X;
	B->right = A;
	A->left = Y;
	A->right = Z

	B->parent = parent;
	A->parent = B;
	if(Z)
		Z->parent = A;
	if(X)
		X->parent = B;
	if(Y)
		Y->parent = A;

	return B;
}

Ausblick

In diesem Artikel habe ich gezeigt wie Suchbäume aufgebaut sind und wie sie funktionieren jedoch auch ihre Schwächen. Der Suchbaum so wie er in diesem Artikel beschrieben wird ist recht nutzlos weil er sehr einfach aus dem Gleichgewicht kommt. Um dagegen vorzugehen gibt es verschiedene Ansätze: AVL-Baum, Rot-Schwarz Baum oder Splay-Baum um nur einige zu nennen. Alle haben ihre Stärken und Schwächen. In den nächsten Artikeln werde den hier vorgestellten Baum zu diesen Spezialbäumen umbauen und die Rotationsfunktionen die jetzt noch etwas in der Luft hängen werden ihren Teil dazu beitragen.

Jester

Ben04 schrieb:

Jester schrieb:

- Du erwähnst kurz Hash-Tabellen. Die sind auch insofern kein Ersatz für das was Du vorstellst, als sie nicht sortiert sind und man damit zum beispiel nicht das nächstgrößere enthaltene element zu einem gegebenen Schlüssel finden kann.

In Hash-Tabellen kann man schon schnell Werte speichern und suchen.

Da hast Du mich falsch verstanden. Ich meinte nicht, dass man in Hasttabellen nicht schnell suchen kann, sondern dass man nicht schnell den nächstgrößeren vorhandenen Eintrag zu einem Schlüssel finden kann. Das liegt genau an der fehlenden Sortierung.

Ben04 schrieb:

Jester schrieb:

Da darfste imho ruhig noch ein bißchen Werbung für das Thema machen.

Wo würdest du die unterbringen?

Und das ist genau die Stelle. Deine Bäume sind zwar bei suchen/einfügen/löschen eines Knotens langsamer als als ne Hasttable, aber sie können eben das nächstgrößere existierende Element finden. Nur für suchen/einfügen/löschen wäre die Hasttabelle ja tatsächlich meist besser (und sogar einfacher). Das klarzustellen meine ich mit "Werbung für Dein Thema".

Die aktuelle Version lese ich mir heute abend mal noch durch.

Ben04

Dies wird (hoffentlich) die letzte Version sein in der es große Änderungen gab. Bitte lest ihn euch durch und meldet falls eine Stelle undeutlich oder gar falsch ist. Ich bin für jedes Feedback egal ob positiv oder negativ dankbar.

Das Inhaltsverzeichnis mach ich glaub ich aber noch weg. Es verscheucht glaub ich zu viele Leser.

================

Inhaltsverzeichnis

1 Suchen das Problem
2 Binäre Suchbäume
2.1 Suchen
2.2 Maximum und Minimum
2.3 Durchwandern
2.3.1 Knoten mit rechtem Kind
2.3.2 Knoten ohne rechtes Kind
2.4 Einfügen
2.5 Löschen
2.5.1 Löschen eines Knoten ohne Kinder
2.5.2 Löschen eines Knoten mit einem Kind
2.5.3 Löschen eines Knoten mit zwei Kindern
2.6 Ausbalancierte Bäume und die die es nicht sind
2.7 Rotationen
3 Implementierung
3.1 Navigation
3.2 Debuggen
3.2.1 Konsolenausgabe
3.2.2 Tod dem Zeigersalat
3.3 Kopiekonstruktor, Destruktor und Zuweisung
3.4 Suchen
3.5 Einfügen
3.6 Austauschen
3.7 Minimum und Maximum
3.8 Durchwandern
3.9 Löschen
3.10 Rotationen
4 Bäume in der STL
5 Ausblick

1 Suchen das Problem

Sei es eine Datenbank oder ein Dateisystem: Das Suchen nach Werten ist eines der häufigsten Probleme in der Informatik. Das im Grunde einfach klingende Problem erweist sich als ein außerordentlich komplexes Biest sobald man über den Tellerrand der trivialen Ansätze blickt.

Für viele Anwendungen recht ein Array in das man sämtliche Werte rein schmeißt und anschließend von Anfang bis Ende durchläuft. Wenn die Datenbank aber wächst dann wird dieser Ansatz aber unvertretbar langsam. Der erste Verbesserungsvorschlag wird dann wohl sein das Array zu sortieren und es dann mit der Hilfe einer binären Suche zu durchwühlen. Solange sich die Element des Arrays nur wenig verändert ist dieser Ansatz gut andernfalls stößt auch er an seine Grenzen.

Wer noch mehr Geschwindigkeit braucht der muss sich vom einfachen Array verabschieden und auf eine andere Datenstruktur ausweichen. Ein Ansatz ist die Werte in einer Hash-Tabelle zu speichern. Diese sind in manchen Anwendungen kaum zu überbieten. Aber auch sie haben ihre Schwächen wenn die Anzahl der Elemente unerwartete Größen annimmt. Des Weiteren schneiden sie schlecht ab wenn man mehr tun will als nur Suchen wie zum Beispiel der iterative Zugriff auf die Elemente. Ist die Tabelle zu groß so wird es ewig dauern sie zu durchforsten um sämtliche Elemente wieder zu finden.

Hash-Tabelle werden aber nicht das Thema dieses Artikels sein, vielmehr wird es eine Weiterentwickelung der binären Suche sein: Der binäre Suchbaum. Dieser passt sich hervorragend einer großen Anzahl von Elementen an und erlaubt es die Element sogar sortiert aufzulisten.

2 Binäre Suchbäume

In einem Suchbaum weist man jedem Knoten ein Element zu und sorgt dafür, dass alle Elemente des linken Unterbaums kleiner und die des rechten Unterbaums größer sind.

2.1 Suchen

Um ein Element zu suchen beginnt man die Suche an der Wurzel. Falls die Wurzel den gesuchten Wert darstellt ist man schon fertig. Sonst vergleicht man ob der dieser kleiner oder größer ist und setzt seine Suche im entsprechenden Unterbaum fort. Wenn man auf der untersten Ebene des Baums angelangt ist ohne den Wert gefunden zu haben dann ist er nicht im Baum enthalten.

In folgendem Beispiel wird die 7 gesucht.

Um ein Element zu finden müssen wir im schlimmsten Fall von der Wurzel bis zur untersten Ebene wandern. Im besten Fall hat der Baum eine Höhe die logarithmisch von der Anzahl seiner Elemente abhängt. Dies gibt also in etwa eine Laufzeitkomplexität von O(log(n)) um ein Element zu suchen wenn wir ungünstige Bäume ignorieren. n ist die Gesamtanzahl der Elemente im Baum.

2.2 Maximum und Minimum

Da die Elemente geordnet im Baum vorliegen ist das kleinste Element das was sich am linken Ende des Baums befindet. Man findet es indem man die Suche an der Wurzel beginnt und sie dann nach links fort setzt bis man an einem Knoten angelangt welcher keinen linken Unterbaum mehr hat. Das größte Element findet man ähnlich, nur dass man nach rechts wandern muss.

Im schlimmsten Fall müssen wir den Baum von oben nach unten durchwandern also ist die Laufzeitkomplexität dieselbe wie die bei der Suche eines Elements das heißt O(log(n)).

2.3 Durchwandern

Um die Elemente eines Baums in geordneter Reihenfolge zu durchwandern beginnt man seine Suche beim Minimum und sucht dann immer das nächste größere Element, bis dass man beim Maximum angelangt ist.

Wie man zum nachfolgenden Knoten im Baum gelangt hängt von der Position im Baum ab von der man startet. Genauer gesagt hängt es davon ab ob der Ausgangsknoten ein rechtes Kind besitzt oder nicht.

2.3.1 Knoten mit rechtem Kind

Falls es einen rechten Unterbaum gibt so ist das nächste Element das Minimum dieses Unterbaums.

In folgendem Beispiel suchen wir das Element das der 5 folgt. Dazu begeben wir uns zuerst in den rechten Unterbaum und dann suchen wir das Minimum indem wir solange nach links wandern wie nur möglich.

2.3.2 Knoten ohne rechtes Kind

Sollte es kein rechtes Kind geben, so muss man Richtung Wurzel des Baums klettern. Falls man unterwegs auf einen Knoten stößt welchen man von seinem linken Kind aus erreicht hat so hat man das nächste Element gefunden.

Der Algorithmus um den Baum vom Maximum zum Minimum zu durchwandern ist genau spiegelverkehrt und darum werde ich nicht weiter auf ihn eingehen.

Beim durchwandern des gesamten Baums wird jede Kante genau zweimal begangen wenn man das Bestimmen des Minimum und Maximum hinzuzählt. Da es nur einen Knoten mehr gibt als Kanten hat das Durchwandern eine Laufzeitkomplexität von O(n). Um das nächste Element zu finden muss man im schlimmsten Fall von der untersten Ebene bis zur Wurzel oder andersherum wandern. Diese hat Operation hat also eine Laufzeitkomplexität von O(log(n)) im ungünstigsten Fall ist aber meisten wesentlich besser.

Es gibt einen alternativen Ansatz der die Knoten noch zusätzlich zum Baum in einer geordneten verketteten Liste zusammen strikt. Dies beschleunigt das Durchwandern um einen konstanten Faktor und sorgt dafür, dass das Bestimmen des nächsten Elements immer eine konstante Laufzeit besitzt. Der Preis ist allerdings der Mehraufwand um die verkettete Liste zu verwalten. Falls man den Baum oft durchwandern muss sollte man diese Option in betracht ziehen.

2.4 Einfügen

Um einen Wert einzufügen geht man ähnlich vor wie bei der normalen Suche. Man wandert solange nach unten, bis man einen Knoten gefunden hat der noch ein Kind, an der richtigen Seite, frei hat.

In folgendem Beispiel wird die 8 eingefügt.

Da es sich im Wesentlichen um den gleichen Algorithmus handelt wie bei der Suche ist auch die Komplexität die gleiche und zwar O(log(n)).

2.5 Löschen

Als erstes sucht man den zu löschenden Knoten nach bekannter Methode. Wie man danach vorgeht hängt von der Position des Knoten im Baum ab, das heißt wie viele Kinder der Knoten hat.

2.5.1 Löschen eines Knoten ohne Kinder

Um ein Blatt zu löschen trennt man es einfach vom Elternknoten ab.

Folgendes Beispiel zeigt wie die 5 aus dem Baum gelöscht wird:

2.5.2 Löschen eines Knoten mit einem Kind

Falls es es nur ein Kind gibt so wandert dieses den Platz des Knoten. Man trennt den zu löschenden Knoten von Kind- und Elternknoten und verbindet danach diese zwei.

Im nächsten Beispiel wird die 3 gelöscht.

2.5.3 Löschen eines Knoten mit zwei Kindern

Ein Knoten mit zwei Kindern lässt sich nicht einfach löschen. Wer aber leicht gelöscht werden kann ist das vorhergehende oder nachfolgende Element. Bei beiden handelt es sich nämlich um das Maximum respektiv dem Minimum des linken beziehungsweise rechten Unterbaums. Aus diesem Grund haben sie höchstens ein Kind und können daher mit einem der beiden oben genannten Methoden gelöscht werden.

Ob man sich für das nachfolgende oder vorhergehende Element entscheidet spielt keine große Rolle. Keine der beiden Optionen hat einen wirklichen Vorteil oder Nachteil.

In folgendem Beispiel wird die 7 gelöscht.

Manche Leser werden sich an diesem Punkt vielleicht fragen ob es denn immer ein nachfolgendes und vorhergehendes Element gibt. Es könnte ja sein, dass man den Auftrag erhalten hat das erste oder letzte Element zu löschen. Da es sich bei beiden allerdings um ein Minimum oder Maximum handelt können sie keine zwei Kinder besitzen und daher ist ein Austauschen gar nicht erst nötig.

Die Geschwindigkeit der eigentlichen Löschverfahren sind alle unabhängig von der Größe des Baums. Legendlich die Suche des zu löschenden Elements und das Bestimmen des nachfolgenden oder vorhergehenden Elements hängen von der Größe ab, darum ist die Komplexität einer Löschoperation in etwa O(log(n)).

2.6 Ausbalancierte Bäume und die die es nicht sind

Eines der großen Probleme solcher Bäume ist, dass wenn die Reihenfolge der Einfügungen ungünstig ist der Baum sehr schnell aus dem Gleichgewicht kommt und zu einer Seite hinkt. Dies macht den Baum sehr viel höher als nötig und somit die Suche viel langsamer da diese ja von der Höhe des Baums abhängt.

In folgendem Baum wird die 8 gesucht und der Arbeitsaufwand kommt schon nahe an den einer sequenziellen Suche heran.

Um dem entgegen zu wirken kann man Rotationen einsetzen.

2.7 Rotationen

Es gibt Rotationen nach links und nach rechts. Da beide Operationen genau spiegelverkehrt sind werde ich nur auf die links Rotation eingehen.

Als erstes trennt man das linke Kind vom rechten Kind der Wurzel ab und anschießend auch das rechte Kind.

Danach wird das rechte Kind zur neuen Wurzel und die alte Wurzel wird ihr neues rechtes Kind. Das Enkelkind wird zum neuen rechten Kind der alten Wurzel.

Nun ist der Baum wieder im Gleichgewicht.

Man sagt links Rotation da das Gleichgewicht sich nach links verlagert. Man kann es sich wie eine Balkenwaage vorstellen welche man in das Gleichgewicht bringt indem man den Balken an einer anderen Stelle aufhängt.

Das Beispiel hinkt zwar da nach der Rotation beide Gewichte gleich schwer sind.

Die Geschwindigkeit einer Rotation hängt nicht von der Größe des Baums ab. Die Komplexität ist also O(1).

Das große Problem von Rotationen ist zu wissen wann man sie einsetzen soll. Sie verbessern nämlich nicht immer das Gleichgewicht eines Baums wie folgendes Beispiel zeigt.

Es gibt verschiedene Strategien um hier vorzugehen. Keine ist allerdings wirklich trivial und verdienen alle ihren eigenen Artikel. Da alle aber Rotationen nutzen hab ich sie bereits jetzt eingeführt damit nicht jeder Artikel diese Operation neu beschreiben muss und direkt mit dem wirklich interessanten Teil beginnen kann. Ich werde in diesem Artikel nicht weiter auf ihre Verwendung eingehen.

3 Implementierung

Das erste was man bei einer Implementierung festlegen muss ist die Darstellung. Die Knoten werden durch eine Struktur dargestellt und dann mit Pointern verbunden. Dies sieht in etwa so aus:

template<class T>
struct Node{
	Node*parent, *left, *right;
	T value;

	explicit Node(const T&value):
		parent(0), left(0), right(0), value(value){}
};

parent zeigt auf den Elternknoten. Falls es sich um die Wurzel handelt ist dieser NULL. left und right zeigen jeweils auf die Wurzel des linken oder rechten Unterbaums oder NULL falls es diesen nicht gibt.

Um zu verhindern, dass Unbefugte an unserem Baum rumbasteln wird dieser durch eine Klasse gekapselt. Dies sieht dann in etwa folgendermaßen aus:

template<class T>
class Tree{
private:
	struct Node{
		Node*parent, *left, *right;
		T value;

		explicit Node(const T&value):
			parent(0), left(0), right(0), value(value){}

	Node*root;
public:
	Tree():root(0){}

	bool is_empty()const{
		return !root;
	}
};

root zeigt dabei auf die Wurzel des Baumes oder NULL falls der Baum leer ist. Ob der Baum leer ist kann mittels is_empty überprüft werden.

Es gibt Variationen in denen die Knoten keinen Zeiger auf den Elternknoten besitzen. Dies spart Speicher und erleichtert die Verwaltung der zusätzlichen Zeiger jedoch macht es auch die Implementierung mancher Operationen wie zum Beispiel des Durchwanderns komplizierter. Oft sind diese nur noch durch den Einsatz eines Stapels oder von Rekursivität überhaupt möglich. Welche Option nun die beste ist hängt von Einsatzfall ab.

Manche Leser werden vielleicht auch auf den Gedanken gekommen sein die Elemente in einem Array abzulegen und das Navigieren durch Multiplizieren der Indexe mit 2 abzuwickeln. Für manche Bäume ist dies sicherlich ein sinnvoll Ansatz wie zum Beispiel Heaps wie man in Jesters Artikel dazu nachlesen kann. Für Suchbäume ist dieser Ansatz aber unbrauchbar da Rotationen sich nur sehr schwer implementieren lassen und unausbalancierte Bäume in dieser Darstellung echte Speicherfresser sind.

3.1 Navigation

Um uns beim navigieren im Baum zu helfen schreiben wir uns Funktionen die prüfen ob es sich um ein linkes oder rechtes Kind handelt.

private:
static bool is_left_child(const Node*node){
	if(node->parent == 0)
		return false; // Die Wurzel ist kein Kind
	else
		return node->parent->left == node;
}

static bool is_right_child(const Node*node){
	if(node->parent == 0)
		return false; // Die Wurzel ist kein Kind
	else
		return node->parent->right == node;
}

Um die Position eines Knoten ändern zu können muss man auch einen einfachen Zugriff auf den Zeiger im Elternknoten haben. Dies bietet folgende Funktion:

private:
Node**get_parent_ptr(Node*node){
	if(node->parent == 0)
		return &root;
	else if(is_left_child(node))
		return &node->parent->left;
	else
		return &node->parent->right;
}

3.2 Debuggen

Da es sehr schwer ist einen Baum fehlerfrei zu implementieren müssen wir uns auch Gedanken machen wie wir ihn debuggen. Wer sich nur für den eigentlichen Code interessiert kann diesen Teil des Artikels getrost überspringen.

3.2.1 Konsolenausgabe

Eine Funktion die den Baum einfach komplett auf die Konsole ausgibt wäre sehr nützlich da die meisten Debugger nicht sonderlich gut sind um solche Datenstrukturen zu inspizieren und nur Zeigersalat anzeigen.

Ziel ist es den Baum ähnlich wie auf den Grafiken oben auszugeben. Dazu müssen wir als erstes festlegen welche Informationen über einen Knoten ausgegeben werden. Dies macht folgende Funktion:

private:
static std::string format_label(const Node*node){
	if(node){
		std::ostringstream out;
		out<<node->value;
		return out.str();
	}else
		return "";
}

Wir müssen auch wissen wie breit und hoch der Baum wird damit wir wissen wie viel Platz frei gelassen werden muss. Folgende Funktionen berechnen diese Informationen für den Baum und jeden Unterbaum.

private:
static unsigned get_height(const Node*node){
	if(!node)
		return 0;
	unsigned left_height = 0, right_height = 0;

	if(node->left)
		left_height = get_height(node->left);
	if(node->right)
		right_height = get_height(node->right);

	// Der höchste Unterbaum bestimmt die Gesamthöhe
	return std::max(left_height, right_height) + 1;
}

static unsigned get_width(const Node*node){
	if(!node)
		return 0;
	unsigned left_width = 0, right_width = 0;

	if(node->left)
		left_width = get_width(node->left);
	if(node->right)
		right_width = get_width(node->right);

	return left_width + format_label(node).length() + right_width;
}

Da wir nur zeilenweise auf die Konsole schreiben können müssen wir den Baum auch Zeile für Zeile ausgeben.

private:
static void dump_spaces(std::ostream&out, unsigned count){
	for(unsigned i=0; i<count; ++i)
		out.put(' ');
}

static void dump_line(std::ostream&out, const Node*node, unsigned line){
	if(!node)
		return;
	if(line == 1){
		// Die Wurzel des Unterbaums soll ausgegeben werden
		dump_spaces(out, get_width(node->left));
		out<<format_label(node);
		dump_spaces(out, get_width(node->right));
	}else{
		// In beiden Unterbäumen sind die Wurzeln um eins niedriger und darum verändert
		// sich die Zeilennumerirung.
		dump_line(out, node->left, line-1);
		dump_spaces(out, format_label(node).length());
		dump_line(out, node->right, line-1);
	}
}

Nun benötigen wir noch eine Möglichkeit den gesamten Baum auszugeben und nicht nur eine Zeile.

private:
static void dump_node(std::ostream&out, const Node*node){
	for(unsigned line=1, height = get_height(node); line <= height; ++line){
		dump_line(out, node, line);
		out.put('\n');
	}
	out.flush();
}

public:
void dump(std::ostream&out)const{
	dump_node(out, root);
}

Mit der Hilfe der dump Funktion können wir nun den Baum für den Menschen lesbar anzeigen. Eine mögliche Ausgabe wäre:

6     
 3   10  
1 5 7  12

Man könnte den Ausgabealgorithmus sicher noch sehr viel verbessern was die Geschwindigkeit betrifft. Ich glaube jedoch kaum, dass er bei großen Bäumen überhaupt zum Einsatz kommen wird und deshalb werde ich dies sein lassen.

3.2.2 Tod dem Zeigersalat

Bei dem Implementieren von Bäumen wird man oft Zeigern die nicht dahin zeigen wo sie eigentlich sollten. Eine Funktion die testet ob der Baum so überhaupt richtig sein kann hilft viele Fehler zu finden. Man testet zum Beispiel ob der Elternknoten des Kindes eines Knoten dieser selbst ist.

private:
bool is_wellformed(Node*node){
	if(node == 0)
		return true;
	if(*get_parent_ptr(node) != node)
		return false;
	if(!is_wellformed(node->left))
		return false;
	if(!is_wellformed(node->right))
		return false;
	return true;
}

Mit Hilfe eines assert(is_wellformed(root)) können sehr viele Fehler vorzeitig abgefangen werden. Durch ein Paar geschickte gesetzte Breakpoints innerhalb dieser Funktion kann man auch sehr genau erfahren welcher Zeiger falsch ist.

3.3 Kopiekonstruktor, Destruktor und Zuweisung

Da ein Baum keine triviale Datenstruktur ist muss man auch den Kopiekonstruktor, den Destruktor und den Zuweisungsoperator implementieren.

Als erstes implementiere ich den Destruktor. Dieser ist leicht rekursive zu realisieren.

private:
static void destroy_node(Node*node){
	if(node){
		destroy_node(node->left);
		destroy_node(node->right);
		delete node;
	}
}

public:
~Tree(){
	destroy_node(root);
}

Bei sehr großen Bäumen kann es bei diesem Destruktor zu einem Stapelüberlauf kommen. In diesem Fall muss man ihn iterative formulieren. Die Idee ist immer das Blatt zu löschen das den kleinsten Wert aller Blätter darstellt also sich auf der linken Seite des Baums befindet. Durch das Abschneiden der ersten Blätter entstehen neue und der Baum schrumpft zusammen, bis dass er schlussendlich nicht mehr existiert.

~Tree(){
	Node*now = root;
	while(now){	
		if(now->left)
			now = now->left;
		else if(now->right)
			now = now->right;
		else{
			Node*next = now->parent;
			*get_parent_ptr(now) = 0;
			delete now;
			now = next;
		}
	}
}

Der Kopiekonstruktor kann auch rekursive implementiert werden man muss jedoch aufpassen ob eine Ausnahme fliegt oder nicht. Dies wird schnell unübersichtlich und fehleranfällig. Darum bevorzuge ich die iterative Version. Die Idee ist den alten und neuen Baum so zu durchlaufen wie wir es im Destruktor tun und dabei alle Knoten klonen welche im alten Baum vorhanden sind jedoch nicht im neuen.

Mit dieser Methode ist der Baum immer in einem gesunden Zustand und kann vom Destruktor auch im unvollendeten Zustand gelöscht werden. Falls eine Ausnahme fliegt brauchen wir nur den Destruktor mit der Arbeit zu beauftragen den halbfertigen Baum zu löschen.

Tree(const Tree&other){
	if(!other.is_empty()){
		root = new Node(other.root->value);
		try{
			Node
				*now = root,
				*other_now = other.root;
			while(other_now){
				if(other_now->left && !now->left){
					now->left = new Node(other_now->left->value);
					now->left->parent = now;
					now = now->left;
					other_now = other_now->left;
				}else if(other_now->right && !now->right){
					now->right = new Node(other_now->right->value);
					now->right->parent = now;
					now = now->right;
					other_now = other_now->right;
				}else{
					now = now->parent;
					other_now = other_now->parent;
				}
				is_wellformed(root);
			}
		}catch(...){
			this->~Tree();
			throw;
		}
	}
}

Der Zuweisungs-Operator kann leicht mit Hilfe des Copy&Swap-Idioms implementiert werden.

public:
void swap(Tree&other){
	std::swap(root, other.root);
}

Tree&operator=(const Tree&other){
	Tree temp(other);
	swap(temp);
	return *this;
}

3.4 Suchen

Implementieren wir nun die Suchfunktion. Da wir die innere Struktur der Klasse verstecken wollen stellen wir dem Außenstehenden nur eine Funktion zur Verfügung die testet ob ein Wert im Baum enthalten ist.

Man sollte bemerken, dass man es dem Benutzer nicht erlauben sollte den Wert des Knoten zu verändert, da dies die Position im Baum durcheinander bringen kann. Falls er dies beabsichtig, dann soll er den alten Wert rauslöschen und den neuen einfügen damit sich das Element an der richtigen Stelle befindet.

Durch den Einsatz von Templates spare ich mir eine const und eine nicht-const Version zu schreiben.

private:
template<class NodeT>
static NodeT*search(NodeT*root, const T&value){
	NodeT*now = root;
	while(now){
		if(value < now->value)
			now = now->left;
		else if(now->value < value)
			now = now->right;
		else
			return now;
	}
	return 0;
}

public:
bool contains(const T&t)const{
	return search(root, t);
}

3.5 Einfügen

Um ein Element einzufügen verfahren wir ähnlich jedoch behalten wir uns wo sich der Elternknoten befindet.

public:
bool insert(const T&value){
	Node
		*parent = 0,
		*now = root;
	bool is_left_child = false;
	while(now){
		parent = now;
		if(value < now->value){
			is_left_child = true;
			now = now->left;
		}else if(now->value < value){
			is_left_child = false;
			now = now->right;
		}else
			return false; // Das Element ist bereits im Baum
	}
	Node*new_node = new Node(value);
	new_node->parent = parent;

	if(parent == 0)
		root = new_node;
	else if(is_left_child)
		parent->left = new_node;
	else
		parent->right = new_node;

	// Wenn etwas mit den Zeigern falsch ist
	// dann knallt es wahrscheinlich hier.
	assert(is_wellformed(root));
	return true;
}

3.6 Austauschen

Knoten können durch austauschen der Werte getauscht werden. Dies ist sicherlich der beste Weg falls man Ganzzahlen speichern will. Es gibt jedoch auch Klassen welche sehr teuer zu tauschen sind oder die gar nicht getauscht werden können. Es ist auch möglich, dass es Zeiger auf das Element gibt die außerhalb des Baums liegen und verändert werden müssten, oder dass beim Tauschen eine Ausnahme fliegen kann. Diese Probleme kann man dadurch umgehen, dass man die Zeiger der Knoten neuverbindet. Hierbei ist der allgemeine Fall vom Fall wo einer der beiden Knoten das Kind des anderen ist zu unterscheiden.

Man sollte beachten, dass das Tauschen von Knoten wahrscheinlich die Ordnung im Baum durcheinander bringt. Es sollte also sicher gestellt sein, dass diese nachdem diese Funktion ihre Arbeit getan hat wiederhergestellt wird.

private:
void swap_near_nodes(Node*child, Node*parent){
	// Als erstes passen wir den unbeteiligten Großelternknoten an.
	*get_parent_ptr(parent) = child;

	// Anschließend werden die Kind- und Elternzeiger ausgetauscht.
	std::swap(parent->left, child->left);
	std::swap(parent->right, child->right);
	std::swap(parent->parent, child->parent);

	// Da eines der Kinder getauscht wird benötigt es eine
	// sonder Behandlung.
	if(child->left == child)
		child->left = parent;
	else
		child->right = parent;

	// Nun sind alle Kindzeiger richtig und die Elternzeiger können
	// dem angepasst werden.
	if(child->left)
		child->left->parent = child;
	if(child->right)
		child->right->parent = child;
	if(parent->left)
		parent->left->parent = parent;
	if(parent->right)
		parent->right->parent = parent;

	// Na wer ist sich noch sicher ob wir nicht
	// bereits Zeigersalat haben? Besser testen!
	assert(is_wellformed(root));
}

void swap_far_nodes(Node*a, Node*b){
	// Zuerst updaten wir die Zeiger der Eltern
	*get_parent_ptr(a) = b;
	*get_parent_ptr(b) = a;

	// Danach der Kinder
	if(a->left)
		a->left->parent = b;
	if(a->right)
		a->right->parent = b;
	if(b->left)
		b->left->parent = a;
	if(b->right)
		b->right->parent = a;

	// Und als letztes die der beiden Knoten
	std::swap(a->left, b->left);
	std::swap(a->right, b->right);
	std::swap(a->parent, b->parent);

	assert(is_wellformed(root));
}

void swap_nodes(Node*a, Node*b){
	if(a->parent == b)
		swap_near_nodes(a, b);
	else if(b->parent == a)
		swap_near_nodes(b, a);
	else
		swap_far_nodes(a, b);
}

3.7 Minimum und Maximum

Das Minimum eines Unterbaums findet man indem man einfach den links Zeigern folgt bis man an einem Knoten ohne linken Unterbaum angelangt ist. Ähnlich geht man beim Maximum vor.

private:
template<class NodeT>
static NodeT*get_min(NodeT*node){
	NodeT*now = node;
	while(now->left)
		now = now->left;
	return now;
}

template<class NodeT>
static NodeT*get_max(NodeT*node){
	NodeT*now = node;
	while(now->right)
		now = now->right;
	return now;
}

public:
const T&min()const{
	return get_min(root)->value;
}

const T&max()const{
	return get_max(root)->value;
}

3.8 Durchwandern

Um dem Benutzer die Möglichkeit zu geben den Baum zu durchwandern bietet sich der Einsatz von Iteratoren förmlich an. Da ich mich in diesem Artikel allerdings auf die Implementierung des Baum beschränken möchte und nicht eine Schnelleinführung zum Thema Iteratoren geben möchte werde ich nur eine Funktion implementieren die den nächst größeren Wert sucht. next nimmt einen Wert als Parameter und gibt einen Zeiger auf das nächste Element zurück oder ein NULL Zeiger falls der Parameter das Maximum war oder ein Wert der sich gar nicht im Baum befindet. prev ist eine ähnliche Funktion die jedoch das nächst kleinere Element sucht.

private:
template<class NodeT>
static NodeT*get_next_node(NodeT*now){
	if(now->right)
		return get_min(now->right);
	else{
		while(now){
			if(is_left_child(now))
				return now->parent;
			else
				now = now->parent;
		}
		return 0; // Wir sind am Ende angekommen
	}
}

template<class NodeT>
static NodeT*get_prev_node(NodeT*now){
	if(now->left)
		return get_max(now->left);
	else{
		while(now){
			if(is_right_child(now))
				return now->parent;
			else
				now = now->parent;
		}
		return 0; // Wir sind am Anfang angekommen
	}
}

public:
const T*next(const T&value)const{
	const Node*now = search(root, value);
	if(!now)
		return 0;
	now = get_next_node(now);
	if(now)
		return &now->value;
	else
		return 0;
}

const T*prev(const T&value)const{
	const Node*now = search(root, value);
	if(!now)
		return 0;
	now = get_prev_node(now);
	if(now)
		return &now->value;
	else
		return 0;
}

3.9 Löschen

Das Löschverfahren von Knoten wurde tiefgehend in der Theorie behandelt und darum gibt es nicht viel zur Implementierung zu sagen.

private:
void remove(Node*node){
	// Ein Blatt
	if(!node->left && !node->right){
		*get_parent_ptr(node) = 0;
		delete node;
	}
	// Nur ein Kind
	else if(node->left && !node->right){
		*get_parent_ptr(node) = node->left;
		node->left->parent = node->parent;
		delete node;
	}else if(!node->left && node->right){
		*get_parent_ptr(node) = node->right;
		node->right->parent = node->parent;
		delete node;
	}
	// Zwei Kinder
	else{
		Node*other = get_prev_node(node);
		swap_nodes(node, other);
		// Löschen des Knoten durch benutzen von einer 
		// der beiden anderen Methoden 
		remove(node);
	}
	assert(is_wellformed(root));
}
public:
bool remove(const T&value){
	Node*node = search(value);
	if(node){
		remove(node);
		return true;
	}else
		return false;
}

3.10 Rotationen

Rotationen können sehr viel Stress verursachen bevor sämtliche Zeiger richtig gestellt werden. Darum ist es sehr nützlich den Baum zuerst zu zeichnen: wie er vorher aussieht und danach.

Die Rotationsfunktionen geben einen Zeiger auf die neue Wurzel zurück.

private:
Node*rotate_left(Node*A){
	Node
		**root_ptr = get_parent_ptr(A),
		*parent = A->parent,
		*B = A->right,
		*X = A->left,
		*Y = B->left,
		*Z = B->right;

	*root_ptr = B;
	B->left = A;
	B->right = Z;
	A->left = X;
	A->right = Y;

	B->parent = parent;
	A->parent = B;
	if(Z)
		Z->parent = B;
	if(X)
		X->parent = A;
	if(Y)
		Y->parent = A;

	return B;
}

private:
Node*rotate_right(Node*A){
	Node
		**root_ptr = get_parent_ptr(A),
		*parent = A->parent,
		*B = A->left,
		*X = B->left,
		*Y = B->right,
		*Z = A->right;

	*root_ptr = B;
	B->left = X;
	B->right = A;
	A->left = Y;
	A->right = Z

	B->parent = parent;
	A->parent = B;
	if(Z)
		Z->parent = A;
	if(X)
		X->parent = B;
	if(Y)
		Y->parent = A;

	return B;
}

4 Bäume in der STL

Die Spezifikation der STL gibt wie immer keine Implementierung vor, allerdings ist es sehr wahrscheinlich, dass hinter std::set und std::map Bäume am Werk sind.

Wie der Baum eingesetzt wird um std::set umzusetzen sollte eigentlich nach dem Lesen dieses Artikels klar sein da es doch gewaltige Ähnlichkeiten mit der hier entwickelten Baumklasse und std::set gibt. Bei std::map könnte es weniger deutlich sein. Hier weist man jedem Knoten einen Schlüssel und den entsprechenden Wert zu und sortiert den Baum dem Schlüssel entsprechend. Ein Suchen nach dem Schlüssel liefert also auch den Knoten in dem der entsprechende Wert gespeichert ist.

5 Ausblick

In diesem Artikel habe ich gezeigt wie Suchbäume aufgebaut sind und wie sie funktionieren jedoch auch ihre Schwächen. Der Suchbaum so wie er in diesem Artikel beschrieben wird ist recht nutzlos weil er sehr einfach aus dem Gleichgewicht kommt. Um dagegen vorzugehen gibt es verschiedene Ansätze: AVL-Baum, Rot-Schwarz Baum oder Splay-Baum um nur einige zu nennen. Alle haben ihre Stärken und Schwächen. In den nächsten Artikeln wird der hier vorgestellten Baum zu diesen Spezialbäumen umbauen und die Rotationsfunktionen die jetzt noch etwas in der Luft hängen werden ihren Teil dazu beitragen.

estartu

Wow.

Also das Inhaltsverzeichnis würde ich drin lassen. Das ist schöner für die, die mal schnell etwas nachschlagen wollen und die, die sich einen groben Überblick holen wollen, was in dem Artikel steht.

Ich finde es schade, dass dein Code so platzsparend formatiert ist.
Wenigtens zwischen Rückgabetyp und Funktionsname wäre ein Leerzeichen nett, den Zeichensalat leserlicher zu machen.
Ich persönlich finde sowas

private:
static std::string format_label(const Node* node)
{
    if (node)
    {
        std::ostringstream out;
        out<<node->value;
        return out.str();
    }
    return "";
}

lesbarer als

private:
static std::string format_label(const Node*node){
    if(node){
        std::ostringstream out;
        out<<node->value;
        return out.str();
    }else
        return "";
}

Aber das ist persönlicher Stil.

Ansonsten hilft einem Anfänger wohl nur, Zettel und Stift bereitzulegen und nachzumalen, was der Quellcode da tut. Da helfen auch Kommentare wenig. Daher finde ich die jetzt ausreichend.

Wenn jetzt noch alles thematisch korrekt ist und der Code funktioniert, dann gibts ein .

Ben04

estartu schrieb:

Also das Inhaltsverzeichnis würde ich drin lassen. Das ist schöner für die, die mal schnell etwas nachschlagen wollen und die, die sich einen groben Überblick holen wollen, was in dem Artikel steht.

Dann bleibt es drin. Wäre es vielleicht eine Idee es ans Ende des Artikels zu verfrachten? Ich hab einfach Angst, dass einige Leser das Verzeichnis sehen, das alleine einen ganze Bildschirm füllt und verschreckt sind.

estartu schrieb:

Wenn jetzt noch alles thematisch korrekt ist und der Code funktioniert, dann gibts ein .

Danke

Heute ist mir noch die Idee gekommen vielleicht über die Geschwindigkeit von new und delete zu schreiben und die Verwendung eines Memorypools vorzuschlagen, keine Details. Wäre das sinnvoll oder würde das nur unnötig aufblähen da es direkt nicht mit dem Thema zu tun hat?

Ich bin im Moment dabei den AVL Teil zu überarbeiten und frage mich wie ich die Beweise darstellen soll. Hat da irgendwer eine Idee wie man das besser machen könnte. Latex-tags halte ich für keine gute Idee da diese des öfteren den Dienst verweigern und somit den Artikel unlesbar machen. Wenn Latex dann statische Bilder.

Jester

Ben04 schrieb:

Wäre es vielleicht eine Idee es ans Ende des Artikels zu verfrachten?

Oder Du nimmst die niedrigen Ebenen aus der Hierarchie aus dem Inhaltsverzeichnis, dann ist es auch nicht mehr so umfangreich.

Heute ist mir noch die Idee gekommen vielleicht über die Geschwindigkeit von new und delete zu schreiben und die Verwendung eines Memorypools vorzuschlagen, keine Details. Wäre das sinnvoll oder würde das nur unnötig aufblähen da es direkt nicht mit dem Thema zu tun hat?

Ich finde sowas immer gut. Ein paar Ausblicke schaden nicht und sie zeigen, dass es da nicht aufhört, wo der Artikel endet. Also immer her damit.

Ich bin im Moment dabei den AVL Teil zu überarbeiten und frage mich wie ich die Beweise darstellen soll. Hat da irgendwer eine Idee wie man das besser machen könnte.

Meine Idee wäre, die Aussagen, die Du benötigst, als Aussage (oder auch Lemma/Satz) zu formulieren und die Beweise dann in einen Anhang zu packen. So wird es ja auch in wissenschaftlichen Einreichungen gemacht, wenn der Platz nicht reicht um alle Beweise in vollen Details reinzunehmen. Außerdem stehen dann die Aussagen und deren Anwendung nah beieinander. Im ersten Schritt glaubt man einfach die Aussagen und sieht dann, dass alles prima funktioniert und wer dann noch Lust hat, der schaut ob die Aussagen auch wirklich richtig sind.

estartu

Wenn man nicht zu großzügig mit Zeilenumbrüchen in List-Tags ist, kann man das Inhaltsverzeichnis nochmal stauchen.

1 Suchen das Problem
2 Binäre Suchbäume
2.1 Suchen
2.2 Maximum und Minimum
2.3 Durchwandern
2.3.1 Knoten mit rechtem Kind
2.3.2 Knoten ohne rechtes Kind
2.4 Einfügen
2.5 Löschen
2.5.1 Löschen eines Knoten ohne Kinder
2.5.2 Löschen eines Knoten mit einem Kind
2.5.3 Löschen eines Knoten mit zwei Kindern
2.6 Ausbalancierte Bäume und die die es nicht sind
2.7 Rotationen
3 Implementierung
3.1 Navigation
3.2 Debuggen
3.2.1 Konsolenausgabe
3.2.2 Tod dem Zeigersalat
3.3 Kopiekonstruktor, Destruktor und Zuweisung
3.4 Suchen
3.5 Einfügen
3.6 Austauschen
3.7 Minimum und Maximum
3.8 Durchwandern
3.9 Löschen
3.10 Rotationen
4 Bäume in der STL
5 Ausblick

Ben04

Damit wäre das Problem gelöst. (Könnte das Forum aber auch selber machen...)

===

3.11 Tunen von new und delete

Bäume spielen ihren Vorteil gegenüber alternativen Datenstrukturen vor allem aus wenn es viele Elemente gibt doch auch bei kleinen Listen sind sie nicht hoffnungslos Unterlegen. Wenn es nur sehr wenige Elemente gibt dann wird nichts in der Liga einfacher Arrays spielen können jedoch gilt es so nahe ran zu kommen wie möglich. Bei kleinen Bäumen fällte die Zeit die durch die Speicherverwaltung, das heißt direkt in new und delete, verbracht wird, viel mehr ins Gewicht und darum bietet es sich an hier was zu tun. Da sämtliche Knoten die gleiche Größe haben kann der Einsatz von Memory Pools Wunder wirken. Bei großen Bäumen ist ihr Einsatz sicherlich nicht verkehrt auch wenn der Gewinn proportional gesehen kleiner ausfallen wird. Zum Nachteil wird der Einsatz von Pools eigentlich so gut wie nie.

Ben04

Ich hab noch ein paar Fehler im Code gefunden und hab noch eine Experimentier-Konsole hinzugefügt. Ich hab den Code nur mit MinGW und VC Express getestet. Könntet ihr bitte andere Compiler testen und sehe ob die irgendwelche Probleme machen. Bitte auch Warnungen posten.

Ich hab nicht vor noch etwas zu ändern aber vielleicht findet irgendwer ja noch einen Fehler. Falls keine Fehler mehr auftauchen werde ich den Artikel in ein paar Tagen auf [R] setzen.

==================

Inhaltsverzeichnis

1 Suchen das Problem
2 Binäre Suchbäume
2.1 Suchen
2.2 Maximum und Minimum
2.3 Durchwandern
2.3.1 Knoten mit rechtem Kind
2.3.2 Knoten ohne rechtes Kind
2.4 Einfügen
2.5 Löschen
2.5.1 Löschen eines Knoten ohne Kinder
2.5.2 Löschen eines Knoten mit einem Kind
2.5.3 Löschen eines Knoten mit zwei Kindern
2.6 Ausbalancierte Bäume und die die es nicht sind
2.7 Rotationen
3 Implementierung
3.1 Navigation
3.2 Debuggen
3.2.1 Konsolenausgabe
3.2.2 Tod dem Zeigersalat
3.3 Kopiekonstruktor, Destruktor und Zuweisung
3.4 Suchen
3.5 Einfügen
3.6 Austauschen
3.7 Minimum und Maximum
3.8 Durchwandern
3.9 Löschen
3.10 Rotationen
3.11 Tunen von new und delete
3.12 Download und Experimentierkonsole
4 Bäume in der STL
5 Ausblick

1 Suchen das Problem

Sei es eine Datenbank oder ein Dateisystem: Das Suchen nach Werten ist eines der häufigsten Probleme in der Informatik. Das im Grunde einfach klingende Problem erweist sich als ein außerordentlich komplexes Biest sobald man über den Tellerrand der trivialen Ansätze blickt.

Für viele Anwendungen recht ein Array in das man sämtliche Werte rein schmeißt und anschließend von Anfang bis Ende durchläuft. Wenn die Datenbank aber wächst dann wird dieser Ansatz aber unvertretbar langsam. Der erste Verbesserungsvorschlag wird dann wohl sein das Array zu sortieren und es dann mit der Hilfe einer binären Suche zu durchwühlen. Solange sich die Element des Arrays nur wenig verändert ist dieser Ansatz gut andernfalls stößt auch er an seine Grenzen.

Wer noch mehr Geschwindigkeit braucht der muss sich vom einfachen Array verabschieden und auf eine andere Datenstruktur ausweichen. Ein Ansatz ist die Werte in einer Hash-Tabelle zu speichern. Diese sind in manchen Anwendungen kaum zu überbieten. Aber auch sie haben ihre Schwächen wenn die Anzahl der Elemente unerwartete Größen annimmt. Desweiteren schneiden sie schlecht ab wenn man mehr tuen will als nur Suchen wie zum Beispiel der iterative Zugriff auf die Elemente. Ist die Tabelle zu groß so wird es ewig dauern sie zu durchforsten um sämtliche Elemente wieder zu finden.

Hash-Tabelle werden aber nicht das Thema dieses Artikels sein, vielmehr wird es eine Weiterentwickelung der binären Suche sein: Der binäre Suchbaum. Dieser passt sich hervoragend einer großen Anzahl von Elementen an und erlaubt es die Element sogar sortiert aufzulisten.

2 Binäre Suchbäume

In einem Suchbaum weist man jedem Knoten ein Element zu und sorgt dafür, dass alle Elemente des linken Unterbaums kleiner und die des rechten Unterbaums größer sind.

2.1 Suchen

Um ein Element zu suchen beginnt man die Suche an der Wurzel. Falls die Wurzel den gesuchten Wert darstellt ist man schon fertig. Sonst vergleicht man ob der dieser kleiner oder größer ist und setzt seine Suche im entsprechenden Unterbaum fort. Wenn man auf der untersten Ebene des Baums angelangt ist ohne den Wert gefunden zu haben dann ist er nicht im Baum enthalten.

In folgendem Beispiel wird die 7 gesucht.

Um ein Element zu finden müssen wir im schlimmsten Fall von der Wurzel bis zur untersten Ebene wandern. Im besten Fall hat der Baum eine Höhe die logarithmisch von der Anzahl seiner Elemente abhängt. Dies gibt also in etwa eine Laufzeitkomplexität von O(log(n)) um ein Element zu suchen wenn wir ungünstige Bäume ignorieren. n ist die Gesamtanzahl der Elemente im Baum.

2.2 Maximum und Minimum

Da die Elemente geordnet im Baum vorliegen ist das kleinste Element das was sich am linken Ende des Baums befindet. Man findet es indem man die Suche an der Wurzel beginnt und sie dann nach links fort setzt bis man an einem Knoten angelangt welcher keinen linken Unterbaum mehr hat. Das größte Element findet man ähnlich, nur dass man nach rechts wandern muss.

Im schlimmsten Fall müssen wir den Baum von oben nach unten durchwandern also ist die Laufzeitkomplexität dieselbe wie die bei der Suche eines Elements das heißt O(log(n)).

2.3 Durchwandern

Um die Elemente eines Baums in geordneter Reihenfolge zu durchwandern beginnt man seine Suche beim Minimum und sucht dann immer das nächste größere Element, bis dass man beim Maximum angelangt ist.

Wie man zum nachfolgenden Knoten im Baum gelangt hängt von der Position im Baum ab von der man startet. Genauer gesagt hängt es davon ab ob der Ausgangsknoten ein rechtes Kind besitzt oder nicht.

2.3.1 Knoten mit rechtem Kind

Falls es einen rechten Unterbaum gibt so ist das nächste Element das Minimum dieses Unterbaums.

In folgendem Beispiel suchen wir das Element das der 5 folgt. Dazu begeben wir uns zuerst in den rechten Unterbaum und dann suchen wir das Minimum indem wir solange nach links wandern wie nur möglich.

2.3.2 Knoten ohne rechtes Kind

Sollte es kein rechtes Kind geben, so muss man Richtung Wurzel des Baums klettern. Falls man unterwegs auf einen Knoten stößt welchen man von seinem linken Kind aus erreicht hat so hat man das nächste Element gefunden.

Der Algorithmus um den Baum vom Maximum zum Minimum zu durchwandern ist genau spiegelverkehrt und darum werde ich nicht weiter auf ihn eingehen.

Beim durchwandern des gesamten Baums wird jede Kante genau zweimal begangen wenn man das Bestimmen des Minimum und Maximum hinzuzählt. Da es nur einen Knoten mehr gibt als Kanten hat das Durchwandern eine Laufzeitkomplexität von O(n). Um das nächste Element zu finden muss man im schlimmsten Fall von der untersten Ebene bis zur Wurzel oder andersherum wandern. Diese hat Operation hat also eine Laufzeitkomplexität von O(log(n)) im ungünstigsten Fall ist aber meisten wesentlich besser.

Es gibt einen alternativen Ansatz der die Knoten noch zusätzlich zum Baum in einer geordneten verketteten Liste zusammen strikt. Dies beschleunigt das Durchwandern um einen konstanten Faktor und sorgt dafür, dass das Bestimmen des nächsten Elements immer eine konstante Laufzeit besitzt. Der Preis ist allerdings der Mehraufwand um die verkettete Liste zu verwalten. Falls man den Baum oft durchwandern muss sollte man diese Option in betracht ziehen.

2.4 Einfügen

Um einen Wert einzufügen geht man ähnlich vor wie bei der normalen Suche. Man wandert solange nach unten, bis man einen Knoten gefunden hat der noch ein Kind, an der richtigen Seite, frei hat.

In folgendem Beispiel wird die 8 eingefügt.

Da es sich im wesentlichen um den gleichen Algorithmus handelt wie bei der Suche ist auch die Komplexität die gleiche und zwar O(log(n)).

2.5 Löschen

Als erstes sucht man den zu löschenden Knoten nach bekannter Methode. Wie man danach vorgeht hängt von der Position des Knoten im Baum ab, das heißt wie viele Kinder der Knoten hat.

2.5.1 Löschen eines Knoten ohne Kinder

Um ein Blatt zu löschen trennt man es einfach vom Elternknoten ab.

Folgendes Beispiel zeigt wie die 5 aus dem Baum gelöscht wird:

2.5.2 Löschen eines Knoten mit einem Kind

Falls es es nur ein Kind gibt so wandert dieses den Platz des Knoten. Man trennt den zu löschenden Knoten von Kind- und Elternknoten und verbindet danach diese zwei.

Im nächsten Beispiel wird die 3 gelöscht.

2.5.3 Löschen eines Knoten mit zwei Kindern

Ein Knoten mit zwei Kinder lässt sich nicht einfach löschen. Wer aber leicht gelöscht werden kann ist das vorhergehende oder nachfolgende Element. Bei beiden handelt es sich nämlich um das Maximum respektiv dem Minimum des linken beziehungsweise rechten Unterbaums. Aus diesem Grund haben sie höchstens ein Kind und können daher mit einem der beiden oben genannten Methoden gelöscht werden.

Ob man sich für das nachfolgende oder vorhergehende Element entscheidet spielt keine große Rolle. Keine der beiden Optionen hat einen wirklichen Vorteil oder Nachteil.

In folgendem Beispiel wird die 7 gelöscht.

Manche Leser werden sich an diesem Punkt vielleicht fragen ob es denn immer ein nachfolgendes und vorhergehendes Element gibt. Es könnte ja sein, dass man den Auftrag erhalten hat das erste oder letzte Element zu löschen. Da es sich bei beiden allerdings um ein Minimum oder Maximum handelt können sie keine zwei Kinder besitzen und daher ist ein Austauschen gar nicht erst nötig.

Die Geschwindigkeit der eigentlichen Löschverfahren sind alle unabhängig von der Größe des Baums. Legendlich die Suche des zu löschenden Elements und das Bestimmen des nachfolgenden oder vorhergehenden Elements hängen von der Größe ab, darum ist die Komplexität einer Löschoperation in etwa O(log(n)).

2.6 Ausbalancierte Bäume und die die es nicht sind

Eines der großen Probleme solcher Bäume ist, dass wenn die Reihenfolge der Einfügungen ungünstig ist der Baum sehr schnell aus dem Gleichgewicht kommt und zu einer Seite hinkt. Dies macht den Baum sehr viel höher als nötig und somit die Suche viel langsamer da diese ja von der Höhe des Baums abhängt.

In folgendem Baum wird die 8 gesucht und der Arbeitsaufwand kommt schon nahe an den einer sequenziellen Suche heran.

Um dem entgegen zu wirken kann man Rotationen einsetzen.

2.7 Rotationen

Es gibt Rotationen nach links und nach rechts. Da beide Operationen genau spiegelverkehrt sind werde ich nur auf die links Rotation eingehen.

Als erstes trennt man das linke Kind vom rechten Kind der Wurzel ab und anschießend auch das rechte Kind.

Danach wird das rechte Kind zur neuen Wurzel und die alte Wurzel wird ihr neues rechtes Kind. Das Enkelkind wird zum neuen rechten Kind der alten Wurzel.

Nun ist der Baum wieder im Gleichgewicht.

Man sagt links Rotation da das Gleichgewicht sich nach links verlagert. Man kann es sich wie eine Balkenwaage vorstellen welche man in das Gleichgewicht bringt indem man den Balken an einer anderen Stelle aufhängt.

Das Beispiel hinkt zwar da nach der Rotation beide Gewichte gleich schwer sind.

Die Geschwindigkeit einer Rotation hängt nicht von der Größe des Baums ab. Die Komplexität ist also O(1).

Das große Problem von Rotationen ist zu wissen wann man sie einsetzen soll. Sie verbessern nämlich nicht immer das Gleichgewicht eines Baums wie folgendes Beispiel zeigt.

Es gibt verschiedene Strategien um hier vorzugehen. Keine ist allerdings wirklich trivial und verdienen alle ihren eigenen Artikel. Da alle aber Rotationen nutzen hab ich sie bereits jetzt eingeführt damit nicht jeder Artikel diese Operation neu beschreiben muss und direkt mit dem wirklich interesanten Teil beginnen kann. Ich werde in diesem Artikel nicht weiter auf ihre Verwendung eingehen.

3 Implementierung

Das erste was man bei einer Implementierung festlegen muss ist die Darstellung. Die Knoten werden durch eine Struktur dargestellt und dann mit Pointern verbunden. Dies sieht in etwa so aus:

template<class T>
struct Node{
	Node*parent, *left, *right;
	T value;

	explicit Node(const T&value):
		parent(0), left(0), right(0), value(value){}
};

parent zeigt auf den Elternknoten. Falls es sich um die Wurzel handelt ist dieser NULL. left und right zeigen jeweils auf die Wurzel des linken oder rechten Unterbaums oder NULL falls es diesen nicht gibt.

Um zu verhindern, dass Unbefugte an unserem Baum rumbasteln wird dieser durch eine Klasse gekapselt. Dies sieht dann in etwa folgendermaßen aus:

template<class T>
class Tree{
private:
	struct Node{
		Node*parent, *left, *right;
		T value;

		explicit Node(const T&value):
			parent(0), left(0), right(0), value(value){}
	};

	Node*root;
public:
	Tree():root(0){}

	bool is_empty()const{
		return !root;
	}
};

root zeigt dabei auf die Wurzel des Baumes oder NULL falls der Baum leer ist. Ob der Baum leer ist kann mittels is_empty überprüft werden.

Es gibt Variationen in denen die Knoten keinen Zeiger auf den Elternknoten besitzen. Dies spart Speicher und erleichtert die Verwaltung der zusätzlichen Zeiger jedoch macht es auch die Implemenierung mancher Operationen wie zum Beispiel des Durchwandern komplizierter. Oft sind diese nur noch durch den Einsatz eines Stacks oder von Rekurivität überhaupt möglich. Welche Option nun die beste ist hängt von Einsatzfall ab.

Manche Leser werden vielleicht auch auf den Gedanken gekommen sein die Elemente in einem Array abzulegen und das Navigieren durch Multiplizieren der Indexe mit 2 abzuwickeln. Für manche Bäume ist dies sicherlich ein sinnvoll Ansatz wie zum Beispiel Heaps wie man in Jesters Artikel dazu nachlesen kann. Für Suchbäume ist dieser Ansatz aber unbrauchbar da Rotationen sich nur sehr schwer implementieren lassen und unausbalancierte Bäume in dieser Darstellung echte Speicherfresser sind.

3.1 Navigation

Um uns beim navigieren im Baum zu helfen schreiben wir uns Funktionen die prüfen ob es sich um ein linkes oder rechtes Kind handelt.

private:
static bool is_left_child(const Node*node){
	if(node->parent == 0)
		return false; // Die Wurzel ist kein Kind
	else
		return node->parent->left == node;
}

static bool is_right_child(const Node*node){
	if(node->parent == 0)
		return false; // Die Wurzel ist kein Kind
	else
		return node->parent->right == node;
}

Um die Position eines Knoten ändern zu können muss man auch einen einfachen Zugriff auf den Zeiger im Elternknoten haben. Dies bietet folgende Funktion:

private:
Node**get_parent_ptr(Node*node){
	if(node->parent == 0)
		return &root;
	else if(is_left_child(node))
		return &node->parent->left;
	else
		return &node->parent->right;
}

3.2 Debuggen

Da es sehr schwer ist einen Baum fehlerfrei zu implementieren müssen wir uns auch Gedanken machen wie wir ihn debuggen. Wer sich nur für den eigentlichen Code interessiert kann diesen Teil des Artikels getrost überspringen.

3.2.1 Konsolenausgabe

Eine Funktion die den Baum einfach komplett auf die Konsole ausgibt wäre sehr nützlich da die meisten Debugger nicht sonderlich gut sind um solche Datenstrukturen zu inspizieren und nur Zeigersalat anzeigen.

Ziel ist es den Baum ähnlich wie auf den Grafiken oben auszugeben. Dazu müssen wir als erstes festlegen welche Informationen über einen Knoten ausgegeben werden. Dies macht folgende Funktion:

private:
static std::string format_label(const Node*node){
	if(node){
		std::ostringstream out;
		out<<node->value;
		return out.str();
	}else
		return "";
}

Wir müssen auch wissen wie breit und hoch der Baum wird damit wir wissen wie viel Platz frei gelassen werden muss. Folgende Funktionen berechnen diese Informationen für den Baum und jeden Unterbaum.

private:
static unsigned get_height(const Node*node){
	if(!node)
		return 0;
	unsigned left_height = 0, right_height = 0;

	if(node->left)
		left_height = get_height(node->left);
	if(node->right)
		right_height = get_height(node->right);

	// Der höchste Unterbaum bestimmt die Gesamthöhe
	return std::max(left_height, right_height) + 1;
}

static unsigned get_width(const Node*node){
	if(!node)
		return 0;
	unsigned left_width = 0, right_width = 0;

	if(node->left)
		left_width = get_width(node->left);
	if(node->right)
		right_width = get_width(node->right);

	return left_width + format_label(node).length() + right_width;
}

Da wir nur zeilenweise auf die Konsole schreiben können müssen wir den Baum auch Zeile für Zeile ausgeben.

private:
static void dump_spaces(std::ostream&out, unsigned count){
	for(unsigned i=0; i<count; ++i)
		out.put(' ');
}

static void dump_line(std::ostream&out, const Node*node, unsigned line){
	if(!node)
		return;
	if(line == 1){
		// Die Wurzel des Unterbaums soll ausgegeben werden
		dump_spaces(out, get_width(node->left));
		out<<format_label(node);
		dump_spaces(out, get_width(node->right));
	}else{
		// In beiden Unterbäumen sind die Wurzeln um eins niedriger und darum verändert
		// sich die Zeilennumerirung.
		dump_line(out, node->left, line-1);
		dump_spaces(out, format_label(node).length());
		dump_line(out, node->right, line-1);
	}
}

Nun benötigen wir noch eine Möglichkeit den gesamten Baum auszugeben und nicht nur eine Zeile.

private:
static void dump_node(std::ostream&out, const Node*node){
	for(unsigned line=1, height = get_height(node); line <= height; ++line){
		dump_line(out, node, line);
		out.put('\n');
	}
	out.flush();
}

public:
void dump(std::ostream&out)const{
	dump_node(out, root);
}

Mit der Hilfe der dump Funktion können wir nun den Baum für den Menschen lesbar anzeigen. Eine mögliche Ausgabe wäre:

6     
 3   10  
1 5 7  12

Man könnte den Ausgabealgorithmus sicher noch sehr viel verbessern was die Geschwindigkeit betrifft. Ich glaube jedoch kaum, dass er bei großen Bäumen überhaupt zum Einsatz kommen wird und deshalb werde ich dies sein lassen.

3.2.2 Tod dem Zeigersalat

Bei dem Implementieren von Bäumen wird man oft Zeigern die nicht dahin zeigen wo sie eigentlich sollten. Eine Funktion die testet ob der Baum so überhaupt richtig sein kann hilft viele Fehler zu finden. Man testet zum Beispiel ob der Elternknoten des Kindes eines Knoten dieser selbst ist.

private:
bool is_wellformed(Node*node){
	if(node == 0)
		return true;
	if(*get_parent_ptr(node) != node)
		return false;
	if(!is_wellformed(node->left))
		return false;
	if(!is_wellformed(node->right))
		return false;
	return true;
}

Mit Hilfe eines assert(is_wellformed(root)) können sehr viele Fehler vorzeitig abgefangen werden. Durch ein Paar geschickte gesetzte Breakpoints innerhalb dieser Funktion kann man auch sehr genau erfahren welcher Zeiger falsch ist.

3.3 Kopiekonstruktor, Destruktor und Zuweisung

Da ein Baum keine triviale Datenstruktur ist muss man auch den Kopiekonstruktor, den Destruktor und den Zuweisungsoperator implementieren.

Als erstes implementiere ich den Destruktor. Dieser ist leicht rekursive zu realisieren.

private:
static void destroy_node(Node*node){
	if(node){
		destroy_node(node->left);
		destroy_node(node->right);
		delete node;
	}
}

public:
~Tree(){
	destroy_node(root);
}

Bei sehr großen Bäumen kann es bei diesem Destruktor zu einem Stapelüberlauf kommen. In diesem Fall muss man ihn iterative formulieren. Die Idee ist immer das Blatt zu löschen das den kleinsten Wert aller Blätter darstellt also sich auf der linken Seite des Baums befindet. Durch das Abschneiden der ersten Blätter entstehen neue und der Baum schrumpft zusammen, bis dass er schlussendlich nicht mehr existiert.

~Tree(){
	Node*now = root;
	while(now){	
		if(now->left)
			now = now->left;
		else if(now->right)
			now = now->right;
		else{
			Node*next = now->parent;
			*get_parent_ptr(now) = 0;
			delete now;
			now = next;
		}
	}
}

Der Kopiekonstruktor kann auch rekursive implementiert werden man muss jedoch aufpassen ob eine Ausnahme fliegt oder nicht. Dies wird schnell unübersichtlich und fehleranfällig. Darum bevorzuge ich die iterative Version. Die Idee ist den alten und neuen Baum so zu durchlaufen wie wir es im Destruktor tun und dabei alle Knoten klonen welche im alten Baum vorhanden sind jedoch nicht im neuen.

Mit dieser Methode ist der Baum immer in einem gesunden Zustand und kann vom Destruktor auch im unvollendeten Zustand gelöscht werden. Falls eine Ausnahme fliegt brauchen wir nur den Destruktor mit der Arbeit zu beauftragen den halbfertigen Baum zu löschen.

Tree(const Tree&other){
	if(other.is_empty())
		root = 0;
	else{
		root = new Node(other.root->value);
		try{
			Node
				*now = root,
				*other_now = other.root;
			while(other_now){
				if(other_now->left && !now->left){
					now->left = new Node(other_now->left->value);
					now->left->parent = now;
					now = now->left;
					other_now = other_now->left;
				}else if(other_now->right && !now->right){
					now->right = new Node(other_now->right->value);
					now->right->parent = now;
					now = now->right;
					other_now = other_now->right;
				}else{
					now = now->parent;
					other_now = other_now->parent;
				}
				is_wellformed(root);
			}
		}catch(...){
			this->~Tree();
			throw;
		}
	}
}

Der Zuweisungs-Operator kann leicht mit Hilfe des Copy&Swap-Idioms implementiert werden.

public:
void swap(Tree&other){
	std::swap(root, other.root);
}

Tree&operator=(const Tree&other){
	Tree temp(other);
	swap(temp);
	return *this;
}

3.4 Suchen

Implementieren wir nun die Suchfunktion. Da wir die innere Struktur der Klasse verstecken wollen stellen wir dem Außenstehenden nur eine Funktion zur Verfügung die testet ob ein Wert im Baum enthalten ist.

Man sollte bemerken, dass man es dem Benutzer nicht erlauben sollte den Wert des Knoten zu verändert, da dies die Position im Baum durcheinander bringen kann. Falls er dies beabsichtig, dann soll er den alten Wert rauslöschen und den neuen einfügen damit sich das Element an der richtigen Stelle befindet.

Durch den Einsatz von Templates spare ich mir eine const und eine nicht-const Version zu schreiben.

private:
template<class NodeT>
static NodeT*search(NodeT*root, const T&value){
	NodeT*now = root;
	while(now){
		if(value < now->value)
			now = now->left;
		else if(now->value < value)
			now = now->right;
		else
			return now;
	}
	return 0;
}

public:
bool contains(const T&t)const{
	return search(root, t);
}

3.5 Einfügen

Um ein Element einzufügen verfahren wir ähnlich jedoch behalten wir uns wo sich der Elternknoten befindet.

public:
bool insert(const T&value){
	Node
		*parent = 0,
		*now = root;
	bool is_left_child = false;
	while(now){
		parent = now;
		if(value < now->value){
			is_left_child = true;
			now = now->left;
		}else if(now->value < value){
			is_left_child = false;
			now = now->right;
		}else
			return false; // Das Element ist bereits im Baum
	}
	Node*new_node = new Node(value);
	new_node->parent = parent;

	if(parent == 0)
		root = new_node;
	else if(is_left_child)
		parent->left = new_node;
	else
		parent->right = new_node;

	// Wenn etwas mit den Zeigern falsch ist
	// dann knallt es wahrscheinlich hier.
	assert(is_wellformed(root));
	return true;
}

3.6 Austauschen

Knoten können durch austauschen der Werte getauscht werden. Dies ist sicherlich der beste Weg falls man Ganzzahlen speichern will. Es gibt jedoch auch Klassen welche sehr teuer zu tauschen sind oder die gar nicht getauscht werden können. Es ist auch möglich, dass es Zeiger auf das Element gibt die außerhalb des Baums liegen und verändert werden müssten, oder dass beim Tauschen eine Ausnahme fliegen kann. Diese Probleme kann man dadurch umgehen, dass man die Zeiger der Knoten neuverbindet. Hierbei ist der allgemeine Fall vom Fall wo einer der beiden Knoten das Kind des anderen ist zu unterscheiden.

Man sollte beachten, dass das Tauschen von Knoten wahrscheinlich die Ordnung im Baum durcheinander bringt. Es sollte also sicher gestellt sein, dass diese nachdem diese Funktion ihre Arbeit getan hat wiederhergestellt wird.

private:
void swap_near_nodes(Node*child, Node*parent){
	// Als erstes passen wir den unbeteiligten Großelternknoten an.
	*get_parent_ptr(parent) = child;

	// Anschließend werden die Kind- und Elternzeiger ausgetauscht.
	std::swap(parent->left, child->left);
	std::swap(parent->right, child->right);
	std::swap(parent->parent, child->parent);

	// Da eines der Kinder getauscht wird benötigt es eine
	// sonder Behandlung.
	if(child->left == child)
		child->left = parent;
	else
		child->right = parent;

	// Nun sind alle Kindzeiger richtig und die Elternzeiger können
	// dem angepasst werden.
	if(child->left)
		child->left->parent = child;
	if(child->right)
		child->right->parent = child;
	if(parent->left)
		parent->left->parent = parent;
	if(parent->right)
		parent->right->parent = parent;

	// Na wer ist sich noch sicher ob wir nicht
	// bereits Zeigersalat haben? Besser testen!
	assert(is_wellformed(root));
}

void swap_far_nodes(Node*a, Node*b){
	// Zuerst updaten wir die Zeiger der Eltern
	*get_parent_ptr(a) = b;
	*get_parent_ptr(b) = a;

	// Danach der Kinder
	if(a->left)
		a->left->parent = b;
	if(a->right)
		a->right->parent = b;
	if(b->left)
		b->left->parent = a;
	if(b->right)
		b->right->parent = a;

	// Und als letztes die der beiden Knoten
	std::swap(a->left, b->left);
	std::swap(a->right, b->right);
	std::swap(a->parent, b->parent);

	assert(is_wellformed(root));
}

void swap_nodes(Node*a, Node*b){
	if(a->parent == b)
		swap_near_nodes(a, b);
	else if(b->parent == a)
		swap_near_nodes(b, a);
	else
		swap_far_nodes(a, b);
}

3.7 Minimum und Maximum

Das Minimum eines Unterbaums findet man indem man einfach den links Zeigern folgt bis man an einem Knoten ohne linken Unterbaum angelangt ist. Ähnlich geht man beim Maximum vor.

private:
template<class NodeT>
static NodeT*get_min(NodeT*node){
	NodeT*now = node;
	while(now->left)
		now = now->left;
	return now;
}

template<class NodeT>
static NodeT*get_max(NodeT*node){
	NodeT*now = node;
	while(now->right)
		now = now->right;
	return now;
}

public:
const T&min()const{
	return get_min(root)->value;
}

const T&max()const{
	return get_max(root)->value;
}

3.8 Durchwandern

Um dem Benutzer die Möglichkeit zu geben den Baum zu durchwandern bietet sich der Einsatz von Iteratoren förmlich an. Da ich mich in diesem Artikel allerdings auf die Implementierung des Baum beschränken möchte und nicht eine Schnelleinführung zum Thema Iteratoren geben möchte werde ich nur eine Funktion implementieren die den nächst größeren Wert sucht. next nimmt einen Wert als Parameter und gibt einen Zeiger auf das nächste Element zurück oder ein NULL Zeiger falls der Parameter das Maximum war oder ein Wert der sich gar nicht im Baum befindet. prev ist eine ähnliche Funktion die jedoch das nächst kleinere Element sucht.

private:
template<class NodeT>
static NodeT*get_next_node(NodeT*now){
	if(now->right)
		return get_min(now->right);
	else{
		while(now){
			if(is_left_child(now))
				return now->parent;
			else
				now = now->parent;
		}
		return 0; // Wir sind am Ende angekommen
	}
}

template<class NodeT>
static NodeT*get_prev_node(NodeT*now){
	if(now->left)
		return get_max(now->left);
	else{
		while(now){
			if(is_right_child(now))
				return now->parent;
			else
				now = now->parent;
		}
		return 0; // Wir sind am Anfang angekommen
	}
}

public:
const T*next(const T&value)const{
	const Node*now = search(root, value);
	if(!now)
		return 0;
	now = get_next_node(now);
	if(now)
		return &now->value;
	else
		return 0;
}

const T*prev(const T&value)const{
	const Node*now = search(root, value);
	if(!now)
		return 0;
	now = get_prev_node(now);
	if(now)
		return &now->value;
	else
		return 0;
}

3.9 Löschen

Das Löschverfahren von Knoten wurde tiefgehend in der Theorie behandelt und darum gibt es nicht viel zur Implementirung zu sagen.

private:
void remove(Node*node){
	// Ein Blatt
	if(!node->left && !node->right){
		*get_parent_ptr(node) = 0;
		delete node;
	}
	// Nur ein Kind
	else if(node->left && !node->right){
		*get_parent_ptr(node) = node->left;
		node->left->parent = node->parent;
		delete node;
	}else if(!node->left && node->right){
		*get_parent_ptr(node) = node->right;
		node->right->parent = node->parent;
		delete node;
	}
	// Zwei Kinder
	else{
		Node*other = get_prev_node(node);
		swap_nodes(node, other);
		// Löschen des Knoten durch benutzen von einer 
		// der beiden anderen Methoden 
		remove(node);
	}
	assert(is_wellformed(root));
}
public:
bool remove(const T&value){
	Node*node = search(root, value);
	if(node){
		remove(node);
		return true;
	}else
		return false;
}

3.10 Rotationen

Rotationen können sehr viel Stress verursachen bevor sämtliche Zeiger richtig gestellt werden. Darum ist es sehr nützlich den Baum zuerst zu zeichnen : wie er vorher aussieht und danach.

Die Rotationsfunktionen geben einen Zeiger auf die neue Wurzel zurück.

private:
Node*rotate_left(Node*A){
	Node
		**root_ptr = get_parent_ptr(A),
		*parent = A->parent,
		*B = A->right,
		*X = A->left,
		*Y = B->left,
		*Z = B->right;

	*root_ptr = B;
	B->left = A;
	B->right = Z;
	A->left = X;
	A->right = Y;

	B->parent = parent;
	A->parent = B;
	if(Z)
		Z->parent = B;
	if(X)
		X->parent = A;
	if(Y)
		Y->parent = A;

	return B;
}

private:
Node*rotate_right(Node*A){
	Node
		**root_ptr = get_parent_ptr(A),
		*parent = A->parent,
		*B = A->left,
		*X = B->left,
		*Y = B->right,
		*Z = A->right;

	*root_ptr = B;
	B->left = X;
	B->right = A;
	A->left = Y;
	A->right = Z;

	B->parent = parent;
	A->parent = B;
	if(Z)
		Z->parent = A;
	if(X)
		X->parent = B;
	if(Y)
		Y->parent = A;

	return B;
}

3.11 Tunen von new und delete

Bäume spielen ihren Vorteil gegenüber alternativen Datenstrukturen vor allem aus wenn es viele Elemente gibt doch auch bei kleinen Listen sind sie nicht hoffnungslos Unterlegen. Wenn es nur sehr wenige Elemente gibt dann wird nichts in der Liga einfacher Arrays spielen können jedoch gilt es so nahe wie möglich ran zu kommen. Bei kleinen Bäumen fällte die Zeit die durch die Speicherverwaltung, das heißt direkt in new und delete, verbracht wird, viel mehr ins Gewicht und darum bietet es sich an hier was zu tun. Da sämtliche Knoten die gleiche Größe haben kann der Einsatz von Memory Pools Wunder wirken. Bei großen Bäumen ist ihr Einsatz sicherlich nicht verkehrt auch wenn der Gewinn proportional gesehen kleiner ausfallen wird. Zum Nachteil wird der Einsatz von Pools eigentlich so gut wie nie.

3.12 Download und Experimentierkonsole

Die Implementierung gibt es auch fertig in einer Datei verpackt um das Herumexperimentieren zu erleichtern. Neben dem eigentlichen Baum ist auch eine Konsole enthalten mit deren Hilfe man die einzelnen Funktionen in Aktion sehen kann. Alles was zum Übersetzen benötigt wird ist ein Standard konformer Compiler.

Download Link

4 Bäume in der STL

Die Spezifikation der STL gibt wie immer keine Implementierung vor, allerdings ist es sehr wahrscheinlich, dass hinter std::set und std::map Bäume am Werk sind.

Wie der Baum eingesetzt wird um std::set umzusetzen sollte eigentlich nach dem Lesen dieses Artikels klar sein da es doch gewaltige Ähnlichkeiten mit der hier entwickelten Baumklasse und std::set gibt. Bei std::map könnte es weniger deutlich sein. Hier weist man jedem Knoten einen Schlüssel und den entsprechenden Wert zu und sortiert den Baum dem Schlüssel entsprechend. Ein Suchen nach dem Schlüssel liefert also auch den Knoten in dem der entsprechende Wert gespeichert ist.

5 Ausblick

In diesem Artikel habe ich gezeigt wie Suchbäume aufgebaut sind und wie sie funktionieren jedoch auch ihre Schwächen. Der Suchbaum so wie er in diesem Artikel beschrieben wird ist recht nutzlos weil er sehr einfach aus dem Gleichgewicht kommt. Um dagegen vorzugehen gibt es verschiedene Ansätze: AVL-Baum, Rot-Schwarz Baum oder Splay-Baum um nur einige zu nennen. Alle haben ihre Stärken und Schwächen. In den nächsten Artikeln wird der hier vorgestellten Baum zu diesen Spezialbäumen umbauen und die Rotationsfunktionen die jetzt noch etwas in der Luft hängen werden ihren Teil dazu beitragen.

Ben04

Ich hab den Artikel jetzt auf [R] gesetzt. Ich hoffe jemand findet die Zeit das ganze auf Rechtschreibfehler zu prüfen. Im Download gibt es auch noch ein paar Kommentare drin. Danke in voraus.