Benutzer:Mikyra/ Gemeinfrei/ AVL-Baum
Der Inhalt des Dokuments ist zusätzlich freigegeben unter WTFPL.
Ein AVL Baum ist ein selbstbalancierender binärer Suchbaum.
Eine solide Kenntnis binärer Suchbäume ist für die weitere Lektüre dieses Kapitels erforderlich. Für dieses Kapitel relevante Informationen finden sich im Kapitel binärer Suchbaum.
Definition[Bearbeiten]
Ein AVL Baum T ist eine Datenstruktur mit den folgenden Eigenschaften:
- (T1) T ist ein binärer Suchbaum
- (T2) H erfüllt das folgende AVL-Kriterium:
Jeder Knoten n mit linkem Kind left und rechtem Kind right erfüllt die AVL-Bedinung: -1 ≤ height(right) - height(left) ≤ 1
- (T3) T untertsützt die folgenden Operationen:
- (a) insert(key) : Füge den Schlüssel key in T ein
- (b) delete(key) : Entferne den Schlüssel key aus T
- (c) lookup(key) : Finde den Knoten n mit Schlüssel key und liefere ihn zurück
Die Differenz height(right) - height(left) der Höhen von rechtem und linken Kind eines Knotens n wird auch als der Balance-Fakor des Knotens n bezeichnet.
Höhe eines AVL-Baums[Bearbeiten]
Die Höhe eines AVL-Baums mit n Knoten ist von der Größenordnung θ(log n).
Die untere Schranke für die Höhe eines AVL-Baums ist durch die Höhe eines vollständigen binären Baums gegeben.
- Sie beträgt Ω(log n) wie behauptet.
Für die Angabe der oberen Schranke in asymptotischer Notation begnügen wir uns mit einer groben Abschätzung. Eine genauere Abschätzung kann durch das Studium von Fibonacci-Bäumen erzielt werden.
- Ein AVL-Baum der Höhe h besteht aus einem Knoten an der Wurzel, sowie einem linken und einem rechten Teilbaum.
- Der Balance-Faktor der Wurzel kann schlimmstenfalls ± 1 betragen. Beide Teilbäume haben damit mindestens die Höhe h-2.
- Die Teilbäume bestehen ihrerseits je aus einer Wurzel, sowie einem linken und einem rechten Teilbaum. Die Balance-Faktoren ihrer Wurzeln können ebenfalls schlimmstenfalls ± 1 betragen. Die Höhen ihrer Teilbäume müssen somit mindestens h-4 betragen und so fort. In der Tiefe t haben alle Teilbäume somit mindestens die Höhe h-2t.
- Der früheste Punkt, an dem wir ein Blatt (d.h. einen Teilbaum der Höhe 0) erreichen können, liegt somit in der Tiefe h/2.
- Ein vollständiger binärer Baum der Höhe h/2 besitzt 2h/2-1 Knoten.
- In der Tiefe h/2 benötigen wir mindestens h/2 weitere Knoten, um die Höhe h des AVL-Baums zu erreichen. Die Zahl n der Knoten in einem AVL-Baum der Höhe h können wir daher mit n ≥ 2h/2 abschätzen.
- Durch Logarithmieren erhalten wir die Abschätzung h ≤ 2 log n für die Höhe h eines AVL-Baums mit n Knoten.
- Die Höhe ist somit von der Größenordnung O(log n) wie behauptet.
Konzept[Bearbeiten]
Operationen, die die Struktur des Baumes unverändert lassen, verändern die Höhen der Knoten des Baumes nicht und können daher genauso wie bei gewöhnlichen binären Suchbäumen implementiert werden.
Im Folgenden werden wir uns daher auf die Operationen insert() und delete() beschränken, die beide die Struktur des Baumes verändern.
Die Strategie, die wir bei ihrer Umsetzung verfolgen, wird darin bestehen den betreffenden Knoten zunächst genauso wie bei einem gewöhnlichen binären Suchbaum einzufügen bzw. zu löschen. In einer nachfolgenden Reparatur-Phase werden wir dann das AVL-Kriterium wiederherstellen. Hilfe bei der Reparatur werden uns die Hilfsoperationen des folgenden Abschnitts leisten.
Rotationen[Bearbeiten]
Hat die Wurzel a eines Baumes T den Balance-Faktor +2 oder -2 und erfüllen die restlichen Knoten von T die AVL-Bedinung, so kann das AVL-Kriterium durch Umhängen von Knoten für ganz T wiederhergestellt werden.
Der Fall, in dem der Balance-Faktor von a +2 beträgt ist dabei symmetrisch zu dem Fall, in dem der Balance-Faktor von a -2 beträgt. Aus diesem Grund werden wir im Folgenden ausschließlich den Fall betrachten, dass der Balance-Faktor von a +2 beträgt. Das Vorgehen in dem Fall, dass der Balance-Faktor von a -2 beträgt ergibt sich hieraus durch Spiegelung.
Beträgt der Balance-Faktor von a +2, so betrachten wir das rechte Kind b von a. Nach Voraussetzung erfüllt b die AVL-Bedinung. Der Balance-Faktor von b kann somit nur einen der Werte +1, 0 oder -1 haben.
Einfache Rotation[Bearbeiten]
Einfach zu beheben sind die Fälle, in denen b einen Balance-Faktor von +1 oder 0 aufweist. Hier genügt es die Knoten wie folgt umzuhängen:
- das linke Kind von b als rechtes Kind von a
- den Knoten a als linkes Kind von b
Dieses Umhängen wird auch als einfache Rotation bezeichnet
Doppelte Rotation[Bearbeiten]
Beträgt der Balance-Faktor von b -1, so können die Knoten wie folgt umgehängt werden:
- das linke Kind von c als rechtes rechtes Kind von a
- das rechte Kind von c als linkes Kind von b
- die Knoten a und b als linkes, bzw. rechtes Kind von c
Dieses Umhängen wird auch als doppelte Rotation bezeichnet.
Balance-Faktoren[Bearbeiten]
Die aus einer einfachen Rotation resultierenden neuen Balance-Faktoren der Knoten a und b hängen von dem Balance-Faktor ab, den der Knoten b vor der Rotation hatte.
Die aus einer doppelten Rotation resultierenden neuen Balance-Faktoren der Knoten a, b und c hängen von dem Balance-Faktor ab, den der Knoten c vor der Rotation hatte.
Auskunft darüber, wie die Balance-Faktoren der beteiligten Knoten anzupassen sind, erhalten wir, indem wir die möglichen Szenarien auf durchspielen. Die Ergebnisse sind in den folgenden Tabellen zusammengefasst.
TODO: Tabelle einfügen
Reparatur[Bearbeiten]
Auf der Suche nach einer Reparaturmöglichkeit hilft folgende Überlegung:
Die einzigen Knoten, deren Höhe sich durch das Einfügen bzw. Löschen eines Knotens x ändern kann, liegen auf dem Pfad von der Wurzel des Baumes zu x. Ihre Höhe kann sich dabei maximal um den Betrag 1 ändern. (1)
Der Balance-Faktor eines Knotens ändert sich genau dann, wenn sich die Höhe eines seiner beiden Kindknoten ändert. (2)
Die einzigen Knoten, deren Balance-Faktoren durch das Einfügen, bzw. Löschen von x beeinflusst werden können, liegen somit ebenfalls auf dem Pfad von der Wurzel des Baumes zu x.
Wir beginnen die Reparatur beim Elternknoten von x und arbeiten uns von dort bis zur Wurzel vor.
Der Balance-Faktor jedes besuchten Knotens n kann sich wegen (1) maximal um den Betrag 1 ändern.
Vor dem Einfügen, bzw. Löschen von x war das AVL-Kriterium erfüllt. Der Balance-Faktor jedes besuchten Knotens n kann somit schlimmstenfalls auf den Wert +2 ansteigen, bzw. auf den Wert -2 sinken.
In beiden Fällen kann die Balancierung des Teilbaums mit Wurzel n mit einer einfachen oder einer doppelten Rotation wiederhergestellt werden.
Die Höhe des rebalancierten Teilbaums kann bei einer einfachen oder doppelten Rotation maximal um den Wert 1 sinken. (3)
Hat sich die Höhe des Teilbaums seit dem Einfügen bzw. Löschen von x nicht geändert, so können wir die Reparatur wegen (2) erfolgreich abbrechen.
Andernfalls setzen wir die Reparatur fort. Der Balance-Faktor jedes besuchten Knotens n kann wegen (3) schlimmstenfalls auf den Wert +2 ansteigen, bzw. auf den Wert -2 sinken. Bei der Reparatur können wir wie gewohnt fortfahren.
Spätestens bei Erreichen der Wurzel ist das AVL-Kriterium wiederhergestellt.
Im schlimmsten Fall wird die Höhe des Baumes bei einer Reparatur genau einmal durchlaufen.
Die worst-case Laufzeit des Reparatur-Algorithmus beträgt somit O(log n).
Reparatur mit Balance-Faktor[Bearbeiten]
Stellen die bei einer Implementierung eingesetzten Datenstrukturen die Höhe eines Knotens direkt zur Verfügung, so kann der Reparatur-Algorithmus direkt in Quellcode umgesetzt werden.
Steht stattdessen nur der Balance-Faktor zur Verfügung, so muss der Reparatur-Algorithmus an zwei Stellen modifiziert werden.
Der neue Balance-Faktor eines Knotens n kann nun nicht mehr aus der Höhe seiner beiden Kindknoten berechnet werden. Stattdessen müssen wir sowohl darauf achten, von welchem der beiden Kindknoten wir zum Knoten n aufsteigen, als auch darauf, ob die Reparatur nach dem Einfügen oder nach dem Löschen eines Knotens durchgeführt wird.
- Nach dem Einfügen sinkt der Balance-Faktor von n um 1, wenn wir von einem linken Kind aufsteigen, und steigt um 1, wenn wir von einem rechten Kind aufsteigen.
- Nach dem Löschen steigt der Balance-Faktor von n um 1, wenn wir von einem linken Kind aufsteigen, und sinkt um 1, wenn wir von einem linken Kind aufsteigen.
Auch die Abbruchbedingung des Reparatur-Algorithmus können wir nun nicht mehr an der Höhe festmachen. Stattdessen müssen wir auch hier darauf achten, ob die Reparatur nach dem Einfügen oder nach dem Löschen eines Knotens ausgeführt wird.
- Nach dem Einfügen ist die ursprüngliche Höhe eines Teilbaums genau dann erreicht, wenn der Banlance-Faktor seines Wurzelknotens 0 beträgt.
- Nach dem Löschen hingegen ist die ursprüngliche Höhe genau dann erreicht, wenn der Balance-Faktor -1 oder +1 beträgt.
Top-Down Einfügen[Bearbeiten]
Beide Varianten des Reparatur-Algorithmus arbeiten sich von den Blättern zur Wurzel vor. Für die Reparatur nach dem Einfügen gibt es eine alternative Variante, die sich von der Wurzel zu den Blättern vorarbeitet.
Die einzige Rotation R2, bei der sich die Höhe des rebalancierten Teilbaums nicht um 1 reduziert, kann nur nach dem Löschen eines Knotens auftreten.
Nach dem Einfügen eines Knotens wird schlimmstenfalls eine einfache bzw. doppelte Rotation benötigt um die Balancierung des Baums wiederherzustellen.
Bereits während wir auf der Suche nach dem Punkt zum Einfügen den Baum hinabsteigen, können wir uns den tiefsten Knoten t merken, dessen Balance-Faktor nach dem Einfügen auf den Wert -2 absinken bzw. auf den Wert +2 ansteigen wird.
Wird nach erfolgter Suche tatsächlich ein neuer Knoten x eingefügt, so können wir in einem weiteren Abstieg die Balance-Faktoren der Knoten auf dem Pfad von t zu x anpassen und eine Rotation um den Knoten t ausführen, um die Balancierung des Baums wiederherzustellen.
Implementierung[Bearbeiten]
Es gibt zahlreiche Möglichkeiten einen AVL-Baum zu implementieren.
Insbesondere die folgenden Wahlmöglichkeiten haben Einfluss auf die Implementierung:
- sind Duplikate zugelassen oder nicht?
- stellt ein Knoten einen Verweis auf den Elternknoten zur Verfügung oder nicht?
- stellt ein Knoten Information über seine Höhe oder über seinen Balance-Faktor zur Verfügung?
Duplikate werden wir bei keiner der im Folgenden vorgestellten Implementierungen zulassen.
Implementierungs-Schema[Bearbeiten]
Für die Darstellung eines AVL-Baums werden wir die folgenden beiden Datenstrukturen verwenden.
- Die Knoten eines AVL-Baums werden wir mit einer Struktur
Noderepräsentieren.
- Den AVL-Baum selbst werden wir mit einer Struktur
Treerepräsentieren.
Um den Code kompakt zu halten, werden wir für beide Datenstrukturen eine Reihe von Hilfsfunktionen definieren. Auf diese Weise können wir bei der Implementierung den Blick auf das wesentliche konzentrieren ohne uns dabei in einer Abhandlung von Spezialfällen zu verlieren.
Implementierung mit Höhe[Bearbeiten]
Bei der ersten Implementierungs-Variante eines AVL Baums werden wir eine Darstellung verwenden, bei der jeder Knoten sowohl Information über seine Höhe height, als auch über seinen Elternknoten parent zur Verfügung stellt.
Knoten[Bearbeiten]
Wie bei der Implementierung eines gewöhnlichen binären Suchbaums, wird die Struktur Node sowohl einen Schlüssel key, als auch zwei Zeiger left und right enthalten, die auf den linken bzw. den rechten Kindknoten verweisen.
Darüber hinaus wird sie sowohl eine Komponente height enthalten, die Auskunft über die Höhe des Knotens gibt, als auch einen Zeiger parent, der auf den zugehörigen Elternknoten verweist.
Die Abwesenheit eines Knotens werden wir dabei in allen Fällen mit dem speziellen Zeigerwert NULL darstellen.
Die Struktur Node kann in C wie folgt definiert werden.
typedef struct node{
int key;
struct node* left;
struct node* right;
struct node* parent;
int height;
} Node;
Um einen neuen Knoten mit Schlüssel key anzulegen, werden wir die Funktion node_new() verwenden.
Sie übernimmt die Aufgabe neuen Speicherplatz anzufordern und ihn entsprechend zu initialisieren.
Node* node_new(int key) {
Node *node = malloc(sizeof(Node));
node->left = node->right = node->parent = NULL;
node->key = key;
node->height = 0;
return node;
}
Um die Zeiger left bzw. right eines Knotens node auf den Wert child zu setzen, werden wir die Funktionen set_left() und set_right() verwenden.
Sie überprüfen den Parameter child auf den speziellen Zeigerwert NULL und passen gegebenenfalls den Zeiger parent des eingehängten Kindknotens an.
void set_left(Node* node, Node* child) {
node->left = child;
if (child != NULL)
child->parent = node;
}
void set_right(Node* node, Node* child) {
node->right = child;
if (child != NULL)
child->parent = node;
}
Um die Höhe und den Balance-Faktor eines Knotens aus der Höhe seiner beiden Kindknoten berechnen zu können, ist es nützlich, dem speziellen Zeigerwert NULL die Höhe -1 zuzuweisen.
Mit dieser Konvention können wir die Berechnung des Balance-Faktors BF() eines Knotens wie folgt in C Code umsetzen.
#define HEIGHT(node) ((node == NULL)? -1 : node->height)
#define BF(n) ( HEIGHT(n->right) - HEIGHT(n->left) )
Um die Höhe eines Knotens node neu zu berechnen, werden wir die Funktion update_height() verwenden.
#define MAX(a, b) ((a > b)? a : b)
void update_height(Node* node) {
node->height = 1 + MAX(HEIGHT(node->left), HEIGHT(node->right));
}
Baum[Bearbeiten]
Wie bei der Implementierung eines gewöhnlichen binären Suchbaums wird die Struktur Tree lediglich einen Zeiger root enthalten, der auf den Wurzelknoten des Baumes verweist.
Auch hier werden wir die Abwesenheit eines Knotens mit dem speziellen Zeigerwert NULL darstellen.
typedef struct {
Node* root;
} Tree;
Um die Struktur Tree zu initialisieren, werden wir die Funktion tree_init() verwenden.
Ihre einzige Aufgabe ist es, den Zeiger root auf den Wert NULL zu setzen.
void tree_init(Tree* tree) {
tree->root = NULL;
}
Um einen Knoten child als Kind des Knotens parent in den Baum tree einzuhängen, werden wir die Funktion attach() verwenden.
Sie überprüft den Parameter parent auf den speziellen Zeigerwert NULL und hängt child entsprechend als neue Wurzel des Baumes bzw. als Kind des Knotens parent ein.
void attach(Tree* tree, Node* parent, Node* child) {
if (parent == NULL)
tree->root = child;
else if (child->key < parent->key)
parent->left = child;
else
parent->right = child;
child->parent = parent;
}
Um ein (Halb-)Blatt node mit Elternknoten parent aus dem Baum tree auszuhängen, werden wir die Funktion detach() verwenden.
Falls vorhanden, bestimmt sie das einzige echte Kind child des Knotens node und hängt es nach Überprüfung des Parameters parent auf den speziellen Zeigerwert NULL als neue Wurzel des Baumes bzw. als Kind des Knotens parent ein.
void detach(Tree* tree, Node* parent, Node* node) {
Node* child = (node->left != NULL)? node->left : node->right;
if (parent == NULL)
tree->root = child;
else if (node == parent->left)
parent->left = child;
else
parent->right = child;
if (child != NULL)
child->parent = parent;
}
Rotationen[Bearbeiten]
Um eine einfache Rotation um den Knoten a auszuführen, werden wir die Funktionen rotate_left() bzw. rotate_right() verwenden.
Sie übernehmen die Aufgabe, die an einer Rotation beteiligten Knoten umzuhängen und ihre Höhe neu zu berechnen.
Um ihn später als neues Kind des ehemaligen Elternknotens von a einhängen zu können, liefern sie zudem den Wurzelknoten b des modifizierten Teilbaums zurück.
Node* rotate_left(Node* a) {
Node* b = a->right; /* A B */
/* \ / */
set_right(a, b->left); /* B A */
set_left(b, a); /* / \ */
/* t t */
update_height(a);
update_height(b);
return b;
}
Node* rotate_right(Node* a) {
Node* b = a->left; /* A B */
/* / \ */
set_left(a, b->right); /* B A */
set_right(b, a); /* \ / */
/* t t */
update_height(a);
update_height(b);
return b;
}
Reparatur[Bearbeiten]
Um die Höhe eines Teilbaum mit der Wurzel node neu zu berechnen und ihn gegebenenfalls zu rebalancieren, werden wir die Funktion fix_node() verwenden.
Auch sie liefert den Wurzelknoten des gegebenenfalls rebalancierten Teilbaums zurück, um ihn später als neues Kind des ehemaligen Elternknotens von node einhängen zu können.
Node* fix_node(Node *node) {
int bf = BF(node);
if (bf == +2) {
if (BF(node->right) == -1)
set_right(node, rotate_right(node->right));
node = rotate_left(node);
}
else if (bf == -2) {
if (BF(node->left) == +1)
set_left(node, rotate_left(node->left));
node = rotate_right(node);
}
else
update_height(node);
return node;
}
Die Reparatur können wir mit der Funktion fix_up() umsetzen.
void fix_up(Tree *tree, Node *node) {
while (node != NULL) {
Node *parent = node->parent;
int height = node->height;
node = fix_node(node);
attach(tree, parent, node);
if (height == node->height)
break;
node = parent;
}
}
Einfügen[Bearbeiten]
Die Implementierung der Operation insert() unterscheidet sich nur im abschliessenden Aufruf der Funktion fix_up() von der eines gewöhnlichen binären Suchbaums.
int insert(Tree* tree, int key) {
Node* parent = NULL;
Node* node = tree->root;
while (node != NULL && node->key != key) {
parent = node;
node = (key < node->key)? node->left : node->right;
}
if (node != NULL)
return -1;
attach(tree, parent, node_new(key));
fix_up(tree, parent);
return 0;
}
Löschen[Bearbeiten]
Die Implementierung der Operation delete() unterscheidet sich nur im abschliessenden Aufruf der Funktion fix_up() von der eines gewöhnlichen binären Suchbaums.
int delete(Tree* tree, int key) {
Node *parent, *node;
for( parent = NULL, node = tree->root;
node != NULL && node->key != key;
node = (key < node->key)? node->left : node->right )
parent = node;
if (node == NULL)
return -1;
if (node->left != NULL && node->right != NULL) {
Node* save = node;
for( parent = node, node = node->right;
node->left != NULL;
node = node->left)
parent = node;
save->key = node->key;
}
detach(tree, parent, node);
free(node);
fix_up(tree, parent);
return 0;
}
Quellcode[Bearbeiten]
Abschliessend hier der vollständige Quelltext der erstellten Implementierung zusammen mit einer Testroutine.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
/************************************************************/
/* Node */
/************************************************************/
typedef struct node{
int key;
struct node* left;
struct node* right;
struct node* parent;
int height;
} Node;
Node* node_new(int key) {
Node *node = malloc(sizeof(Node));
node->left = node->right = node->parent = NULL;
node->key = key;
node->height = 0;
return node;
}
void set_left(Node* node, Node* child) {
node->left = child;
if (child != NULL)
child->parent = node;
}
void set_right(Node* node, Node* child) {
node->right = child;
if (child != NULL)
node->parent = node;
}
#define HEIGHT(node) ((node == NULL)? -1 : node->height)
#define BF(n) ( HEIGHT(n->right) - HEIGHT(n->left) )
#define MAX(a, b) ((a > b)? a : b)
void update_height(Node* node) {
node->height = 1 + MAX(HEIGHT(node->left), HEIGHT(node->right));
}
/************************************************************/
/* Tree */
/************************************************************/
typedef struct {
Node* root;
} Tree;
void tree_init(Tree* tree) {
tree->root = NULL;
}
void attach(Tree* tree, Node* parent, Node* child) {
if (parent == NULL)
tree->root = child;
else if (child->key < parent->key)
parent->left = child;
else
parent->right = child;
child->parent = parent;
}
void detach(Tree* tree, Node* parent, Node* node) {
Node* child = (node->left != NULL)? node->left : node->right;
if (parent == NULL)
tree->root = child;
else if (node == parent->left)
parent->left = child;
else
parent->right = child;
if (child != NULL)
child->parent = parent;
}
/************************************************************/
/* Rotations */
/************************************************************/
Node* rotate_left(Node* a) {
Node* b = a->right; /* A B */
/* \ / */
set_right(a, b->left); /* B A */
set_left(b, a); /* / \ */
/* t t */
update_height(a);
update_height(b);
return b;
}
Node* rotate_right(Node* a) {
Node* b = a->left; /* A B */
/* / \ */
set_left(a, b->right); /* B A */
set_right(b, a); /* \ / */
/* t t */
update_height(a);
update_height(b);
return b;
}
/************************************************************/
/* Fix */
/************************************************************/
Node* fix_node(Node *node) {
int bf = BF(node);
if (bf == +2) {
if (BF(node->right) == -1)
set_right(node, rotate_right(node->right));
node = rotate_left(node);
}
else if (bf == -2) {
if (BF(node->left) == +1)
set_left(node, rotate_left(node->left));
node = rotate_right(node);
}
else
update_height(node);
return node;
}
void fix_up(Tree *tree, Node *node) {
while (node != NULL) {
Node *parent = node->parent;
int height = node->height;
node = fix_node(node);
attach(tree, parent, node);
if (height == node->height)
break;
node = parent;
}
}
/************************************************************/
/* Insert */
/************************************************************/
int insert(Tree* tree, int key) {
Node* parent = NULL;
Node* node = tree->root;
while (node != NULL && node->key != key) {
parent = node;
node = (key < node->key)? node->left : node->right;
}
if (node != NULL)
return -1;
attach(tree, parent, node_new(key));
fix_up(tree, parent);
return 0;
}
int delete(Tree* tree, int key) {
Node* parent = NULL;
Node* node = tree->root;
while (node != NULL && node->key != key) {
parent = node;
node = (key < node->key)? node->left : node->right;
}
if (node == NULL)
return -1;
if (node->left != NULL && node->right != NULL) {
Node* save = node;
for( parent = node, node = node->right;
node->left != NULL;
node = node->left)
parent = node;
save->key = node->key;
}
detach(tree, parent, node);
free(node);
fix_up(tree, parent);
return 0;
}
/************************************************************/
/* Tree Dump */
/************************************************************/
int tree_dump_r(Node* node, int is_left, int x, int y, char lines[][80]) {
if (node == NULL)
return 0;
char buffer[80];
int width = sprintf(buffer, "%d(%d)%d", node->height, node->key, BF(node));
int w_left = tree_dump_r(node->left, 1, x , y+1, lines);
int w_right = tree_dump_r(node->right, 0, x + w_left + width, y+1, lines);
x += w_left;
/* draw arc */
char* line = lines[2*y - 1];
if (y != 0) {
int line_left, line_right;
char marker_left = '+';
char marker_right = '+';
if (is_left) {
line_left = x + width/2;
line_right = line_left + width + w_right;
marker_left = '.';
}
else {
line_right = x + width/2;
line_left = line_right - width - w_left - 1;
marker_right = '.';
}
for (int i=line_left; i<=line_right; ++i)
line[i] = '-';
line[line_left] = marker_left;
line[line_right] = marker_right;
}
/* draw label */
line += 80;
for (int i=0; i<width; ++i)
line[x + i] = buffer[i];
return w_left + width + w_right;
}
void tree_dump(Tree* tree) {
int n_lines = (HEIGHT(tree->root) + 1) * 2;
char (*lines)[80] = malloc(n_lines * 80);
memset(lines, ' ', n_lines * 80);
tree_dump_r(tree->root, 0, 0, 0, lines);
for (int i=0; i<n_lines; ++i) {
lines[i][79] = '\0';
printf("%s\n", lines[i]);
}
free(lines);
}
/************************************************************/
/* main() */
/************************************************************/
int main(int argc, char* argv[]) {
//int numbers[] = { 3, 2, 8, 1, 6, 9, 5, 7, 10, 17, 23, 44, 4};
int numbers[] = { 1, 2, 3, 5, 6, 8, 9, 7, 10, 17, 23, 44, 4};
int n_numbers = sizeof(numbers) / sizeof(int);
int remove[] = { 8, 6, 3, 4 };
int n_remove = sizeof(remove) / sizeof(int);
Tree tree;
tree.root = NULL;
for (int i=0; i<n_numbers; ++i) {
printf("insert(%d)\n", numbers[i]);
insert(&tree, numbers[i]);
tree_dump(&tree);
}
for (int i=0; i<n_remove; ++i) {
printf("delete(%d)\n", remove[i]);
delete(&tree, remove[i]);
tree_dump(&tree);
}
return 0;
}
Nach dem Übersetzen erhalten wir eine Ausgabe der Form:
insert(1)
...
insert(7)
3(5)1
.--------+----------------.
1(2)0 2(8)-1
.---+-----. .---------+-----.
0(1)0 0(3)0 1(6)1 0(9)0
+-----.
0(7)0
...
delete(3)
3(9)1
.-------+-------------------.
1(5)0 2(23)-1
.---+-----. .-----------+------.
0(4)0 0(7)0 1(10)1 0(44)0
+------.
0(17)0
Knoten werden in der Form "«Höhe»(«Schlüssel»)<Balance-Faktor»" ausgegeben.
Implementierung mit Balance-Faktor[Bearbeiten]
Für die zweite Implementierungs-Variante eines AVL Baums verwenden wir eine Darstellung, bei der die Knoten des Baumes lediglich Information über ihren Balance-Faktor bf zur Verfügung stellen.
Knoten[Bearbeiten]
Wie bei der Implementierung eines gewöhnlichen binären Suchbaums, wird die Struktur Node sowohl einen Schlüssel key, als auch zwei Zeiger left und right enthalten, die auf den linken, bzw. den rechten Kindknoten verweisen.
Darüber hinaus wird sie eine Komponente bf enthalten, die Auskunft über den Balance-Faktor des Knotens gibt.
Die Abwesenheit eines Knotens werden wir mit dem speziellen Zeigerwert NULL darstellen.
Die Struktur Node kann in C wie folgt definiert werden.
typedef struct node{
int key;
struct node* left;
struct node* right;
int bf;
} Node;
Um einen neuen Knoten mit Schlüssel key anzulegen, werden wir die Funktion node_new() verwenden.
Sie übernimmt die Aufgabe neuen Speicherplatz anzufordern und ihn entsprechend zu initialisieren.
Node* node_new(int key) {
Node *n = (Node*) malloc(sizeof(Node));
n->left = n->right = NULL;
n->key = key;
n->bf = 0;
return n;
}
Baum[Bearbeiten]
Wie bei der Implementierung eines gewöhnlichen binären Suchbaums, wird die Struktur Tree lediglich einen Zeiger root enthalten, der auf den Wurzelknoten des Baumes verweist.
Auch hier werden wir die Abwesenheit eines Knotens mit dem speziellen Zeigerwert NULL darstellen.
typedef struct {
Node* root;
} Tree;
void tree_init(Tree* tree) {
tree->root = NULL;
}
Um einen Knoten child als Kind des Knotens parent in den Baum tree einzuhängen, werden wir die Funktion `attach()` verwenden.
Sie überprüft den Parameter parent auf den speziellen Zeigerwert NULL und hängt child entsprechend als neue Wurzel des Baumes bzw. als Kind des Knotens parent ein.
void attach(Tree* tree, Node* parent, Node* child) {
if (parent == NULL)
tree->root = child;
else if (child->key < parent->key)
parent->left = child;
else
parent->right = child;
}
Um ein (Halb-)Blatt node mit Elternknoten parent aus dem Baum tree auszuhängen, werden wir die Funktion detach() verwenden.
Falls vorhanden, bestimmt sie das einzige echte Kind child des Knotens node und hängt es nach Überprüfung des Parameters parent auf den speziellen Zeigerwert NULL als neue Wurzel des Baumes bzw. als Kind des Knotens parent ein.
void detach(Tree* tree, Node* parent, Node* node) {
Node* child = (node->left != NULL)? node->left : node->right;
if (parent == NULL)
tree->root = child;
else if (node == parent->left)
parent->left = child;
else
parent->right = child;
}
Einfache Rotationen[Bearbeiten]
Um eine einfache Rotation um den Knoten a auszuführen, werden wir die Funktionen rotate_left() bzw. rotate_right() verwenden.
Sie übernehmen die Aufgabe die an einer Rotation beteiligten Knoten um zu hängen und ihre Balance-Faktoren entsprechend anzupassen.
Um ihn später als neues Kind des ehemaligen Elternknotens von a einhängen zu können, liefern sie zudem den Wurzelknoten b des rebalancierten Teilbaums zurück.
Node* rotate_left(Node* a) {
/* A B */
Node* b = a->right; /* \ / */
/* B A */
a->right = b->left; /* / \ */
b->left = a; /* t t */
/* B | +1 0 */
/* --+------- */
a->bf = (b->bf == +1)? 0 : +1; /* A | 0 +1 */
b->bf = (b->bf == +1)? 0 : -1; /* B | 0 -1 */
return b;
}
Node* rotate_right(Node* a) {
/* A B */
Node* b = a->left; /* / \ */
/* B A */
a->left = b->right; /* \ / */
b->right = a; /* t t */
/* B | -1 0 */
/* --+------- */
a->bf = (b->bf == -1)? 0 : -1; /* A | 0 -1 */
b->bf = (b->bf == -1)? 0 : +1; /* B | 0 +1 */
return b;
}
Doppelte Rotationen[Bearbeiten]
Um eine doppelte Rotation um den Knoten a auszuführen, werden wir die Funktionen rotate_right_left() bzw. rotate_left_right() verwenden.
Sie übernehmen die Aufgabe die an einer Rotation beteiligten Knoten um zu hängen und ihre Balance-Faktoren entsprechend anzupassen.
Um ihn später als neues Kind des ehemaligen Elternknotens von a einhängen zu können, liefern sie zudem den Wurzelknoten c des rebalancierten Teilbaums zurück.
Node* rotate_right_left(Node* a) {
/* A C */
Node* b = a->right; /* \ / \ */
Node* c = b->left; /* B A B */
/* / \ / */
a->right = c->left; /* C t1 t2 */
b->left = c->right; /* / \ */
c->left = a; /* t1 t2 */
c->right = b;
/* C | +1 0 -1 */
/* --+----------- */
a->bf = (c->bf == +1)? -1 : 0; /* A | -1 0 0 */
b->bf = (c->bf == -1)? +1 : 0; /* B | 0 0 1 */
c->bf = 0; /* C | 0 0 0 */
return c;
}
Node* rotate_left_right(Node* a) {
/* A C */
Node* b = a->left; /* / / \ */
Node* c = b->right; /* B B A */
/* \ \ / */
b->right = c->left; /* C t1 t2 */
a->left = c->right; /* / \ */
c->left = b; /* t1 t2 */
c->right = a;
/* C | +1 0 -1 */
/* --+----------- */
a->bf = (c->bf == -1)? +1 : 0; /* A | 0 0 1 */
b->bf = (c->bf == 1)? -1 : 0; /* B | -1 0 0 */
c->bf = 0; /* C | 0 0 0 */
return c;
}
Rebalancierung[Bearbeiten]
Um den Balance-Faktor eines Teilbaum mit der Wurzel node zu überprüfen, und ihn gegebenenfalls zu rebalancieren, werden wir die Funktion fix_node() verwenden.
Auch sie liefert den Wurzelknoten des gegebenenfalls rebalancierten Teilbaums zurück, um ihn später als neues Kind des ehemaligen Elternknotens von node einhängen zu können.
Node* fix_node(Node* node) {
if (node->bf == +2) {
if (node->right->bf == -1)
node = rotate_right_left(node);
else
node = rotate_left(node);
}
else if (node->bf == -2) {
if (node->left->bf == +1)
node = rotate_left_right(node);
else
node = rotate_right(node);
}
return node;
}
Reparatur[Bearbeiten]
Bei der Reparatur müssen wir uns von den Blättern zur Wurzel des Baumes vor arbeiten.
Anders als bei der Implementierungs-Variante zuvor stellen die Knoten des Baumes in dieser Variante keinen Verweis auf den Elternknoten mehr zur Verfügung. Um uns dennoch von den Blättern zur Wurzel vor arbeiten zu können, müssen wir uns die Knoten, die auf auf dem Pfad von der Wurzel des Baumes zum betreffenden Blatt liegen, bereits beim Abstieg "merken". Je nach gewählter Form der Implementierung stehen uns dabei die folgenden Möglichkeiten offen.
- In einer iterativen Implementierung können die beim Abstieg besuchten Knoten auf einen explizit angelegten Stack legen
- In einer rekursiven Implementierung können wir den bei jedem Funktionsaufruf implizit angelegten Stack verwenden
Wir beginnen zunächst mit einer iterativen Implementierung. Eine rekursive Implementierung werden wir uns erst im Anschluss daran ansehen.
iterativ[Bearbeiten]
Bei der iterative Implementierung, werden wir für die Reparatur die Funktionen fix_insert() und fix_delete() verwenden.
Die Knoten, die auf dem Pfad von der Wurzel zum betreffenden Blatt liegen, werden wir dabei als Array im Parameter path übergeben.
Ein weiterer Parameter top wird dabei Auskunft über den Index des tiefsten Knotens geben.
void fix_insert(Tree *tree, Node* path[], int top, int is_left) {
Node* node = path[top--];
while (node != NULL) {
Node* parent = path[top--];
node->bf += is_left? -1 : +1;
node = fix_node(node);
attach(tree, parent, node);
if (node->bf == 0)
break;
is_left = (parent == NULL || node == parent->left);
node = parent;
}
}
/************************************************************/
void fix_delete(Tree *tree, Node* path[], int top, int is_left) {
Node* node = path[top--];
while (node != NULL) {
Node* parent = path[top--];
node->bf += is_left? +1 : -1;
node = fix_node(node);
attach(tree, parent, node);
if (node->bf == -1 || node->bf == +1)
break;
is_left = (parent == NULL || node == parent->left);
node = parent;
}
}
Einfügen[Bearbeiten]
Das Einfügen eines Schlüssels key können wir in einer Funktion insert_iter() umsetzen.
Ihre Implementierung unterscheidet sich nur darin von der eines gewöhnlichen binären Suchbaums, dass während des Abstiegs im Array path Buch über die besuchten Knoten geführt und abschließend die Funktion fix_insert() aufgerufen wird.
int insert_iter(Tree* tree, int key) {
Node* path[STACK_SIZE];
int top = 0;
path[0] = NULL;
Node* node = tree->root;
while (node != NULL && node->key != key) {
path[++top] = node;
node = (key < node->key)? node->left : node->right;
}
if (node != NULL)
return -1;
attach(tree, path[top], node_new(key));
fix_insert(tree, path, top, key);
return 0;
}
Entfernen[Bearbeiten]
Das Entfernen eines Schlüssels key können wir in einer Funktion delete_iter() umsetzen.
Auch Implementierung unterscheidet sich nur darin von der eines gewöhnlichen binären Suchbaums, dass während des Abstiegs im Array path Buch über die besuchten Knoten geführt und abschließend die Funktion fix_delete() aufgerufen wird.
int delete_iter(Tree* tree, int key) {
Node* path[STACK_SIZE];
int top = 0;
path[0] = NULL;
Node* node = tree->root;
while (node != NULL && node->key != key) {
path[++top] = node;
node = (key < node->key)? node->left : node->right;
}
if (node == NULL)
return -1;
if (node->left != NULL && node->right != NULL) {
Node* save = node;
path[++top] = node;
node = node->right;
while (node->left != NULL) {
path[++top] = node;
node = node->left;
}
save->key = node->key;
key = node->key;
}
detach(tree, path[top], node);
free(node);
fix_delete(tree, path, top, key);
return 0;
}
rekursiv[Bearbeiten]
Für die rekursive Version müssen wir wissen, wann die Reparatur abgeschlossen ist. Und ob überhaupt eingefügt / gelöscht werden konnte. Für das Flag werden wir die folgenden Werte verwenden:
typedef enum {
STATE_UNCHANGED,
STATE_FIX,
STATE_DONE
} State;
Einfügen[Bearbeiten]
Node* insert_r(Node* node, int key, State* state) {
if (node == NULL) {
*state = STATE_FIX;
return node_new(key);
}
if (key == node->key)
return node;
if (key < node->key)
node->left = insert_r(node->left, key, state);
else
node->right = insert_r(node->right, key, state);
if (*state == STATE_FIX) {
node->bf += (key < node->key)? -1 : +1;
node = fix_node(node);
if (node->bf == 0)
*state = STATE_DONE;
}
return node;
}
int insert_rec(Tree* tree, int key) {
State state = STATE_UNCHANGED;
tree->root = insert_r(tree->root, key, &state);
return (state == STATE_UNCHANGED)? -1 : 0;
}
Entfernen[Bearbeiten]
Node* delete_r(Node* node, int key, State* state) {
if (node == NULL)
return NULL;
if (key == node->key) {
if (node->left != NULL && node->right != NULL) {
Node* min = node->right;
while (min->left != NULL)
min = min->left;
node->key = min->key;
key = min->key;
}
else {
Node* child = (node->left !=NULL)? node->left : node->right;
free(node);
*state = STATE_FIX;
return child;
}
}
if (key < node->key)
node->left = delete_r(node->left, key, state);
else
node->right = delete_r(node->right, key, state);
if (*state == STATE_FIX) {
node->bf += (key < node->key)? +1 : -1;
node = fix_node(node);
if (node->bf == -1 || node->bf == +1)
*state = STATE_DONE;
}
return node;
}
int delete_rec(Tree* tree, int key) {
State state = STATE_UNCHANGED;
tree->root = delete_r(tree->root, key, &state);
return (state == STATE_UNCHANGED)? -1 : 0;
}
top down[Bearbeiten]
int insert_td(Tree* tree, int key) {
Node *top_parent, *top_node;
Node* parent = top_parent = NULL;
Node* node = top_node = tree->root;
while (node != NULL && node->key != key) {
if (node->bf != 0) { /* i.e. node->bf == -1 || node->bf == +1 */
top_node = node;
top_parent = parent;
}
parent = node;
node = (key < node->key)? node->left : node->right;
}
if (node != NULL)
return -1;
/* adjust bf */
node = top_node;
while (node != NULL) {
if (key < node->key) {
node->bf += -1;
node = node->left;
}
else {
node->bf += +1;
node = node->right;
}
}
/* insert node */
attach(tree, parent, node_new(key));
/* (maybe) fix top */
if (top_node != NULL)
attach(tree, top_parent, fix_node(top_node));
return 0;
}
Quellcode[Bearbeiten]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
/************************************************************/
/* Node */
/************************************************************/
typedef struct node{
int key;
struct node* left;
struct node* right;
int bf;
} Node;
Node* node_new(int key) {
Node *n = (Node*) malloc(sizeof(Node));
n->left = n->right = NULL;
n->key = key;
n->bf = 0;
return n;
}
/************************************************************/
int _node_height_rec(Node* node, int depth) {
if (node == NULL)
return depth-1;
int l_max = _node_height_rec(node->left, depth +1);
int r_max = _node_height_rec(node->right, depth +1);
return (l_max > r_max)? l_max : r_max;
}
int node_height(Node* node) {
return _node_height_rec(node, 0);
}
#define HEIGHT(node) node_height(node)
/************************************************************/
/* Tree */
/************************************************************/
typedef struct {
Node* root;
} Tree;
void tree_init(Tree* tree) {
tree->root = NULL;
}
/************************************************************/
void attach(Tree* tree, Node* parent, Node* child) {
if (parent == NULL)
tree->root = child;
else if (child->key < parent->key)
parent->left = child;
else
parent->right = child;
}
/************************************************************/
void detach(Tree* tree, Node* parent, Node* node) {
Node* child = (node->left != NULL)? node->left : node->right;
if (parent == NULL)
tree->root = child;
else if (node == parent->left)
parent->left = child;
else
parent->right = child;
}
/************************************************************/
/* Rotations */
/************************************************************/
Node* rotate_left(Node* a) {
/* A B */
Node* b = a->right; /* \ / */
/* B A */
a->right = b->left; /* / \ */
b->left = a; /* t t */
/* B | +1 0 */
/* --+------- */
a->bf = (b->bf == +1)? 0 : +1; /* A | 0 +1 */
b->bf = (b->bf == +1)? 0 : -1; /* B | 0 -1 */
return b;
}
/************************************************************/
Node* rotate_right(Node* a) {
/* A B */
Node* b = a->left; /* / \ */
/* B A */
a->left = b->right; /* \ / */
b->right = a; /* t t */
/* B | -1 0 */
/* --+------- */
a->bf = (b->bf == -1)? 0 : -1; /* A | 0 -1 */
b->bf = (b->bf == -1)? 0 : +1; /* B | 0 +1 */
return b;
}
/************************************************************/
Node* rotate_right_left(Node* a) {
/* A C */
Node* b = a->right; /* \ / \ */
Node* c = b->left; /* B A B */
/* / \ / */
a->right = c->left; /* C t1 t2 */
b->left = c->right; /* / \ */
c->left = a; /* t1 t2 */
c->right = b;
/* C | +1 0 -1 */
/* --+----------- */
a->bf = (c->bf == +1)? -1 : 0; /* A | -1 0 0 */
b->bf = (c->bf == -1)? +1 : 0; /* B | 0 0 1 */
c->bf = 0; /* C | 0 0 0 */
return c;
}
/************************************************************/
Node* rotate_left_right(Node* a) {
/* A C */
Node* b = a->left; /* / / \ */
Node* c = b->right; /* B B A */
/* \ \ / */
b->right = c->left; /* C t1 t2 */
a->left = c->right; /* / \ */
c->left = b; /* t1 t2 */
c->right = a;
/* C | +1 0 -1 */
/* --+----------- */
a->bf = (c->bf == -1)? +1 : 0; /* A | 0 0 1 */
b->bf = (c->bf == 1)? -1 : 0; /* B | -1 0 0 */
c->bf = 0; /* C | 0 0 0 */
return c;
}
/************************************************************/
/* Fix */
/************************************************************/
Node* fix_node(Node* node) {
if (node->bf == +2) {
if (node->right->bf == -1)
node = rotate_right_left(node);
else
node = rotate_left(node);
}
else if (node->bf == -2) {
if (node->left->bf == +1)
node = rotate_left_right(node);
else
node = rotate_right(node);
}
return node;
}
/************************************************************/
/* ITERATIVE */
/************************************************************/
#define STACK_SIZE 100
/************************************************************/
void fix_insert(Tree *tree, Node* path[], int top, int key) {
Node* node = path[top--];
while (node != NULL) {
Node* parent = path[top--];
node->bf += (key < node->key)? -1 : +1;
node = fix_node(node);
attach(tree, parent, node);
if (node->bf == 0)
break;
node = parent;
}
}
/************************************************************/
void fix_delete(Tree *tree, Node* path[], int top, int key) {
Node* node = path[top--];
while (node != NULL) {
Node* parent = path[top--];
node->bf += (key < node->key)? +1 : -1;
node = fix_node(node);
attach(tree, parent, node);
if (node->bf == -1 || node->bf == +1)
break;
node = parent;
}
}
/************************************************************/
int insert_iter(Tree* tree, int key) {
Node* path[STACK_SIZE];
int top = 0;
path[0] = NULL;
Node* node = tree->root;
while (node != NULL && node->key != key) {
path[++top] = node;
node = (key < node->key)? node->left : node->right;
}
if (node != NULL)
return -1;
attach(tree, path[top], node_new(key));
fix_insert(tree, path, top, key);
return 0;
}
int delete_iter(Tree* tree, int key) {
Node* path[STACK_SIZE];
int top = 0;
path[0] = NULL;
Node* node = tree->root;
while (node != NULL && node->key != key) {
path[++top] = node;
node = (key < node->key)? node->left : node->right;
}
if (node == NULL)
return -1;
if (node->left != NULL && node->right != NULL) {
Node* save = node;
path[++top] = node;
node = node->right;
while (node->left != NULL) {
path[++top] = node;
node = node->left;
}
save->key = node->key;
key = node->key;
}
detach(tree, path[top], node);
free(node);
fix_delete(tree, path, top, key);
return 0;
}
/************************************************************/
/* TOP-DOWN */
/************************************************************/
int insert_td(Tree* tree, int key) {
Node *top_parent, *top_node;
Node* parent = top_parent = NULL;
Node* node = top_node = tree->root;
while (node != NULL && node->key != key) {
if (node->bf != 0) { /* i.e. node->bf == -1 || node->bf == +1 */
top_node = node;
top_parent = parent;
}
parent = node;
node = (key < node->key)? node->left : node->right;
}
if (node != NULL)
return -1;
/* adjust bf */
node = top_node;
while (node != NULL) {
if (key < node->key) {
node->bf += -1;
node = node->left;
}
else {
node->bf += +1;
node = node->right;
}
}
/* insert node */
attach(tree, parent, node_new(key));
/* (maybe) fix top */
if (top_node != NULL)
attach(tree, top_parent, fix_node(top_node));
return 0;
}
/************************************************************/
/* RECURSIVE */
/************************************************************/
typedef enum {
STATE_UNCHANGED,
STATE_FIX,
STATE_DONE
} State;
/************************************************************/
/* Insert */
/************************************************************/
Node* insert_r(Node* node, int key, State* state) {
if (node == NULL) {
*state = STATE_FIX;
return node_new(key);
}
if (key == node->key)
return node;
if (key < node->key)
node->left = insert_r(node->left, key, state);
else
node->right = insert_r(node->right, key, state);
if (*state == STATE_FIX) {
node->bf += (key < node->key)? -1 : +1;
node = fix_node(node);
if (node->bf == 0)
*state = STATE_DONE;
}
return node;
}
int insert_rec(Tree* tree, int key) {
State state = STATE_UNCHANGED;
tree->root = insert_r(tree->root, key, &state);
return (state == STATE_UNCHANGED)? -1 : 0;
}
/************************************************************/
/* Delete */
/************************************************************/
Node* delete_r(Node* node, int key, State* state) {
if (node == NULL)
return NULL;
if (key == node->key) {
if (node->left != NULL && node->right != NULL) {
Node* min = node->right;
while (min->left != NULL)
min = min->left;
node->key = min->key;
key = min->key;
}
else {
Node* child = (node->left !=NULL)? node->left : node->right;
free(node);
*state = STATE_FIX;
return child;
}
}
if (key < node->key)
node->left = delete_r(node->left, key, state);
else
node->right = delete_r(node->right, key, state);
if (*state == STATE_FIX) {
node->bf += (key < node->key)? +1 : -1;
node = fix_node(node);
if (node->bf == -1 || node->bf == +1)
*state = STATE_DONE;
}
return node;
}
int delete_rec(Tree* tree, int key) {
State state = STATE_UNCHANGED;
tree->root = delete_r(tree->root, key, &state);
return (state == STATE_UNCHANGED)? -1 : 0;
}
/************************************************************/
/* Tree Dump */
/************************************************************/
int _tree_dump(Node* node, int is_left, int x, int y, char lines[][80]) {
if (node == NULL)
return 0;
char buffer[80];
int width = sprintf(buffer, "(%d)%d", node->key, node->bf);
int w_left = _tree_dump(node->left, 1, x , y+1, lines);
int w_right = _tree_dump(node->right, 0, x + w_left + width, y+1, lines);
x += w_left;
/* draw arc */
char* line = lines[2*y - 1];
if (y != 0) {
int line_left, line_right;
char marker_left = '+';
char marker_right = '+';
if (is_left) {
line_left = x + width/2;
line_right = line_left + width + w_right;
marker_left = '.';
}
else {
line_right = x + width/2;
line_left = line_right - width - w_left - 1;
marker_right = '.';
}
for (int i=line_left; i<=line_right; ++i)
line[i] = '-';
line[line_left] = marker_left;
line[line_right] = marker_right;
}
/* draw label */
line += 80;
for (int i=0; i<width; ++i)
line[x + i] = buffer[i];
return w_left + width + w_right;
}
void tree_dump(Tree* tree) {
int n_lines = (HEIGHT(tree->root) + 1) * 2;
char (*lines)[80] = malloc(n_lines * 80);
memset(lines, ' ', n_lines * 80);
_tree_dump(tree->root, 0, 0, 0, lines);
for (int i=0; i<n_lines; ++i) {
lines[i][79] = '\0';
printf("%s\n", lines[i]);
}
free(lines);
}
/************************************************************/
/* main() */
/************************************************************/
int main(int argc, char* argv[]) {
int numbers[] = { 1, 2, 3, 5, 6, 8, 9, 7, 10, 17, 23, 44, 4 };
int n_numbers = sizeof(numbers) / sizeof(int);
int remove[] = { 8, 6, 3, 4, 42 };
int n_remove = sizeof(remove) / sizeof(int);
Tree tree;
tree.root = NULL;
for (int i=0; i<n_numbers; ++i) {
int ret = insert_iter(&tree, numbers[i]);
printf("insert(%d) : %d\n", numbers[i], ret);
tree_dump(&tree);
}
for (int i=0; i<n_remove; ++i) {
int ret = delete_iter(&tree, remove[i]);
printf("delete(%d) : %d\n", remove[i], ret);
tree_dump(&tree);
}
return 0;
}