Effizientes Programmieren - Kurs 3

Diesmal wollen wir eine sehr mächtige und universell einsetzbare Datenstruktur besprechen: den Baum (tree). Im speziellen wollen wir dann auf die besondere Eignung von Bäumen zum Suchen eingehen.

In der ersten Folge dieses Kurses haben wir uns mit linearen Listen beschäftigt und haben bemerkt, daß die Suchoperation bei Verwendung der verketteten Speicherung nicht in zufriedenstellender Geschwindigkeit abläuft. Um nun die Vorteile einer schnellen Suche, wie wir sie bei der Implementierung durch ein Array hatten, mit den schnellen Einfüge- und Entferne-Operationen und dem flexibeln dynamischen Aufbau der verketteten Speicherung kombinieren zu können, benötigen wir eine neue Datenstruktur: den Suchbaum. Zum besseren Verständnis müssen Sie erst einmal wissen, was ein Baum ist. Bäume sind im Prinzip eine Erweiterung von einfachen linearen Listen. Anders wie bei Listen, bei denen jedes Element einen Vorgänger und einen Nachfolger besitzt, hat bei einem Baum jeder Knoten einen Vater und eine bestimmte Anzahl von Söhnen. Wir wollen hier nur Bäume mit maximal zwei Söhnen betrachten, die Binärbäume (binary tree). Ein Knoten im Baum ist als Wurzel ausgezeichnet, er hat als einziger keinen Vater und stellt somit quasi den "Anfang" des Baumes dar. Bäume veranschaulicht man sich grafisch wie in Abbildung 1. Dabei zeichnet man die Wurzel ganz oben und hängt die entsprechenden Söhne links und rechts an die Wurzel. An diese Söhne hängt man dann wieder neue Knoten und so weiter. Das Ende dieses Pfades ist erreicht, wenn ein Knoten keine Söhne mehr hat. Einen solchen Knoten nennt man dann auch Blatt, alle anderen bezeichnet man als innere Knoten.

Abbildung 1: Ein sortierter Binärbaum

Zum Suchen benötigen wir einen sortierten Baum. Ein Binärbaum ist dann sortiert, wenn für jeden Knoten gilt, daß der Schlüssel des linken Sohnes immer kleiner oder gleich dem Schlüssel des Knotens selbst und dieser kleiner oder gleich dem Schlüssel des rechten Sohnes ist. Der kleinste Knoten steht in einem Binärbaum also immer ganz links, der größte ist immer ganz rechts zu finden. Wenn wir nun einen bestimmten Knoten auffinden wollen, beginnen wir bei der Wurzel und vergleichen deren Schlüsseln mit dem gesuchten. Sind die beiden Schlüsseln identisch, dann haben wir den gesuchten Knoten gefunden. Ist der Schlüssel der Wurzel aber größer als der gesuchte, wissen wir nun, daß wir den rechten Teilbaum der Wurzel nicht mehr durchsuchen brauchen, da alle Knoten, die rechts von der Wurzel hängen, noch größere Schlüsseln haben, als die Wurzel selbst. Wir setzen also die Suche mit dem linken Sohn der Wurzel fort. Hier verfahren wir gleich wie mit der Wurzel. Ist der gesuchte Schlüssel aber größer als der eben betrachtete, steigen wir natürlich zum rechten Sohn hinunter. Diese als binäres Suchen bezeichnete Methode haben wir schon bei den Listen in ähnlicher Form kennengelernt. Wir setzen sie solange fort, bis wir den gesuchten Knoten gefunden haben oder an das Ende des Baumes gestoßen sind. In diesem Fall ist der gesuchte Schlüssel im Suchbaum nicht vorhanden. Wie der enorme Zeitgewinn zustande kommt, ist leicht zu verstehen. Wie Sie sich leicht vorstellen können, fallen bei jedem Vergleich gleich eine Menge von Knoten unter den Tisch. Während wir beim sequentiellen Suchen in konventionellen Listen bei jedem Vergleich immer nur sagen können, ob der eben betrachtete Knoten der gesuchte ist oder nicht, kann man beim binären Suchen gleich entweder den gesamten linken oder den gesamten rechten Teilbaum vergessen. Wir ersparen uns somit viele unnötige Vergleiche. Der Nachteil dabei ist, daß wir den Baum sortiert halten müssen, um den Erfolg eines solchen Suchvorgangs gewährleisten zu können. Somit dauert das Einfügen eines solchen Knotens länger als bei unsortierten Listen, bei denen wir ein neues Element einfach am Ende der Liste anhängen. Trotzdem sind solche Suchverfahren sehr beliebt, da dieser kleine Nachteil durch den Geschwindigkeitsgewinn beim Suchen mehr als wettgemacht wird. Wagen wir uns nun einmal an die programmtechnische Realisierung des Suchens in Binärbäumen. Wir wählen dazu eine Datenstruktur, die aus zwei Zeigern - auf den linken und den rechten Sohn - besteht.

struct tree_node { struct tree_node *left,*right; };

Diese Struktur ist jedoch nur von theoretischem Wert, denn sie enthält noch keinen Schlüssel. Dazu muß erst eine weitere Struktur von tree_node abgeleitet werden. Unter ableiten verstehen wir dabei, daß diese Struktur die gleichen Eigenschaften hat wie tree_node, weshalb alle Operationen, die für tree_node definiert sind, auch für die abgeleitete Struktur gelten. In C++ würde eine solche Ableitung beispielsweise so aussehen:

class bsp_node : public tree_node { int key; ... };

In C stellt man hingegen die Basisklasse einfach an den Anfang der abgeleiteten Klasse; das hat dann aber den Nachteil, daß man bei Funktionsaufrufen immer entweder die Adresse der tree_node übergeben muß oder die ganze Struktur in eine tree_node umcastet.

struct bsp_node { struct tree_node node; int key; ... };

Unsere Suchprozedur schreiben wir, wie oben beschrieben. Zusätzlich benötigen wir aber noch Routinen zum Einfügen bzw. Entfernen von Knoten aus dem Binärbaum.

Beim Einfügen verfahren wir ähnlich wie beim Suchen. Wir durchlaufen den Baum, als ob wir den einzufügenden Knoten suchen würden. Wenn wir die Stelle gefunden haben, an der dieser Knoten stehen sollte, dann fügen wir ihn eben dort ein. Dazu brauchen wir nur den Zeiger des übergeordneten Knotens auf ihn zu richten und der Knoten ist eingefügt.

Das Entfernen eines Knotens aus einem Binärbaum gestaltet sich schon etwas schwieriger. Während ein neuer Knoten immer ein Blatt wird, kann es beim Entfernen auch passieren, daß wir einen inneren Knoten rauswerfen müssen. Unterscheiden wir also drei Fälle:

(1) Wir sollen ein Blatt entfernen. Dies ist der einfachste Fall. Hier setzen wir den Zeiger seines Vaters einfach auf NULL und der Knoten ist draußen. (2) Der zu entfernende Knoten k hat nur einen Sohn. Hier ersetzen wir den Knoten einfach durch seinen einzigen Sohn. Dadurch ist er aus dem Baum entfernt. (3) Der Knoten k hat zwei Söhne. Hier wird es schon etwas schwieriger. Wir können den Knoten nicht einfach hinauswerfen, weil dann die Zeiger auf die beiden Söhne verlorengehen. Wir gehen vielmehr folgendermaßen vor: Wir suchen uns im rechten Teilbaum unseres Knotens den Knoten mit dem kleinsten Schlüssel heraus. Da unser Baum sortiert ist, ist das immer der am weitesten links stehende Knoten im rechten Teilbaum. Er wird als der symmetrische Nachfolger von k bezeichnet. Wenn wir diesen Knoten gefunden haben, entfernen wir ihn von seiner alten Position und setzen ihn dort rein, wo bisher k gestanden hat.

Der letzte Fall ist wohl der schwierigste. Deshalb wollen wir dazu ein kleines Beispiel machen. Nehmen wir an, wir wollen die 7 aus Abbildung 1 entfernen (in diesem Fall die Wurzel). Da die 7 zwei Söhne hat, nämlich die 4 und die 20, handelt es sich wohl eindeutig um Fall 3. Wir suchen also zunächst den symmetrischen Nachfolger der 7. Das ist - wie besprochen - der linkeste Knoten im rechten Teilbaum. Der rechte Teilbaum von 7 hat die Wurzel 20 und der linkeste Knoten dieses Teilbaumes ist die 17. Wir entfernen also diesen Knoten gemäß der Vorschrift. Beachten Sie bitte, daß es sich hier immer entweder um Fall 1 oder um Fall 2 handelt, nie aber um Fall 3. Das erscheint insofern logisch, daß der linkeste Knoten nie einen linken Sohn haben kann, weil dieser ja sonst noch weiter links liegen würde. In unserem Beispiel handelt es sich um den Fall 1, denn die 17 ist ein Blatt. Wir hängen also die 17 von ihrem Vater, der 20, ab und setzen Sie dorthin, wo bisher die 7 stand, nämlich an die Wurzel. Auf diese Weise ist die 7 aus unserem Baum verschwunden und der Vorgang des Entfernens beendet.

Die bisher besprochenen Routinen für das Suchen, Einfügen und Entfernen sind in Listing 1 als fertiges Programm zu sehen. Es handelt sich dabei um eine Unterprogrammbibliothek, die die Funktionen tree, tree_find, tree_insert und tree_remove zur Verfügung stellt. tree ist der Konstruktor für diesen Baum. Er muß immer vor der ersten Verwendung des Baumes aufgerufen werden. An ihn wird neben dem zu konstruierenden Baum ein Zeiger auf eine Funktion übergeben, mit der zwei Knoten (bzw. deren Schlüsseln) verglichen werden können. Sie erinnern sich, wir haben schon in der ersten Folge unseres Kurses besprochen, wie wir auf diese Weise eine Datenstruktur implementieren können, die unabhängig vom eigentlich verwendeten (Schlüssel-)Typ arbeitet.

An tree_find wird ein Zeiger auf den zu durchsuchenden Baum übergeben und ein weiterer auf den zu suchenden Beispielknoten. Mit diesem Beispielknoten hat es eine besondere Bewandtnis. Es ist kein Zeiger auf einen Knoten im Baum, sondern nur ein Knoten, der denselben Schlüssel hat, wie der gesuchte. Durch einen Vergleich der Knoten im Baum mit dem Beispielknoten kann tree_find dann den richtigen Knoten finden. tree_insert bekommt den obligaten Zeiger auf den Baum und den einzufügenden Knoten k übergeben. Da unsere Bäume in der Form nur für exklusive Schlüssel gedacht sind, können nie zwei Knoten in einem Baum denselben Schlüssel haben. Findet tree_insert also im Baum einen Knoten mit derselben Schlüsselinformation wie k, dann wird der Zeiger auf diesen Knoten zurückgegeben und k nicht eingefügt. Andernfalls gibt tree_insert NULL zurück und fügt k in den Baum ein.

Die letzte Funktion, tree_remove, benötigt wieder einen Zeiger auf den Baum und einen zweiten auf den Beispielknoten. Für diesen Knoten gilt das bei tree_find gesagte. tree_remove entfernt anschließend den zu diesem Beispielknoten äquivalenten Knoten und gibt einen Zeiger auf ihn zurück. Konnte kein passender Knoten gefunden werden, wird NULL zurückgegeben. Diese Implementation von Binärbäumen stellt schon eine recht akzeptable Lösung unseres Suchproblems dar. Jedoch hat die Sache einen Haken. Wenn Sie noch einmal einen Blick auf Abbildung 1 werfen, sehen Sie einen typischen Baum, wie wir ihn gerne haben möchten. Er besitzt sieben Knoten und hat die Höhe drei. Als Höhe bezeichnet man dabei den maximalen Abstand eines Knotens von der Wurzel. Um in einem solchen optimalen Baum einen beliebigen Knoten zu finden braucht man maximal drei Vergleiche. Leider kommt es in der Praxis oft vor, daß Bäume ausarten. Nehmen wir beispielsweise an, wir fügen in einen anfangs leeren Baum in dieser Reihenfolge folgende Schlüsseln ein: 3, 4, 6, 7, 17, 20 und 33. Probieren Sie selbst einmal, den daraus entstehenden Baum auf Papier aufzuzeichnen. Er müßte genau so wie in Abbildung 2 aussehen. Dies wäre ein extremes Beispiel eines entarteten Baumes. Hier ist er praktisch zu einer linearen Liste degeneriert. Um hier ein Element herauszusuchen kann man im Fall der 33 schon 7 Schritte benötigen, dieser Suchbaum ist also ebenso schlecht wie eine lineare Liste, mit dem zusätzlichen Handicap einer langsamereren Einfügeroutine.

Abbildung 2: Ein entarteter Baum

Obwohl solche zu Listen degenerierte Bäume eher selten vorkommen, möchte man manchmal gewährleisten, daß die Höhe eines Baumes stets minimal bleibt, der Baum also optimal zum Suchen ist. Aus diesem Grund hat man sogenannte höhenbalancierte Bäume erfunden, bei denen es in angemessener Zeit möglich ist, den Baum beim Einfügen oder Entfernen eines beliebigen Knotens immer optimal zu halten. Berühmteste Vertreter solcher höhenbalancierter Bäume sind die AVL-Bäume, benannt nach den beiden sowjetischen Erfindern Adelson-Velskii und Landis. Wie Sie sich sicherlich vorstellen können, ist das Einfügen und Entfernen von Schlüsseln in einem solchen Baum nicht mehr ganz so einfach.

Zunächst brauchen wir für jeden Knoten k einen Balancefakor ß(k). Hier speichern wir immer die Differenz der Höhe des rechten Teilbaumes von k und der Höhe des linken Teilbaumes von k ab. Weiters legen wir fest, daß die Balance für jeden inneren Knoten nur die Werte -1, 0 oder +1 annehmen darf. Damit gewährleisten wir, daß für jeden Knoten entweder der linke Teilbaum gleich groß wie der rechte ist, oder einer von beiden um nur einen Knoten höher ist. Beim Einfügen und Entfernen muß also stets beachtet werden, daß diese Bedingungen nicht verletzt werden. Das Suchen hingegen läuft ganz gleich ab wie bei den natürlichen Binärbäumen.

Betrachten wir zuerst das Einfügen eines Knotens k in einen AVL-Baum. Da ein neuer Knoten immer als Blatt an einen Baum angehängt wird, bekommt unser Knoten k den Balancefaktor 0. Anschließend wird er ganz normal in den Baum eingefügt. Nun erfolgt die Ausbalancierung. Dazu wird der Vater des eben eingefügten Knotens k überprüft. Nennen wir diesen Vater beispielsweise p. Wir machen nun eine Unterscheidung, ob k der linke oder rechte Sohn von p ist.

(1) k ist linker Sohn von p: Nun untersuchen wir die Balance von p. (a) p hat die Balance +1. In diesem Fall war die Höhe des rechten Teilbaumes von p um einen Knoten höher als die des linken. Nachdem p aber einen linken Sohn dazubekommen hat, ist die Balance nun wieder ausgeglichen, wir brauchen also nur ß(p)=0 setzen und der Einfügevorgang ist beendet, da sich die Höhe des Teilbaumes ab dem Knoten p nicht verändert hat. (b) p hat die Balance 0. Das bedeutet, daß die Höhe des linken Teilbaumes von p gleich der Höhe des rechten Teilbaumes war. Da sich der linke Teilbaum aber erhöht hat, setzen wir ß(p)=-1. Beachten Sie bitte, daß sich in diesem Fall die Höhe des Teilbaumes mit der Wurzel p um eins erhöht haben muß! Aus diesem Grund muß auch ein eventueller Vater von p ausbalanciert werden, da sich auch für ihn eine Änderung der Balance ergeben wird. (c) p hat die Balance -1. Hier war die Höhe des linken Teilbaumes sowieso schon höher als die des rechten. Jetzt haben wir ihn aber noch um einen Knoten erhöht, das ist zuviel. Die Balance-Bedingung wurde verletzt und wir müssen eine Umstrukturierung des Baumes vornehmen. Man bezeichnet diese im allgemeinen als Rotationen und man unterscheidet zwischen einfachen und doppelten Rotationen. Wie diese Rotationen im Detail aussehen, zeigen die Abbildungen 3 und 4. Die Dreiecke stehen hierbei für einen beliebigen Baum und die darunter stehenden Ausdrücke geben die möglichen Höhen dieser Teilbäume an. Die Zahlen neben den Knoten geben deren Balance an. Je nach Balance von k, also des linken Sohnes von p, muß eine einfache Rotation nach rechts (s. Abbildung 3, bei ß(k)=-1), oder eine doppelte Rotation nach links-rechts (s. Abbildung 4, bei ß(k)=+1) durchgeführt werden. Eine Balance von ß(k)=0 ist nicht möglich, wenn k kein Blatt ist. In jedem Fall ist die Höhe des Teilbaumes ab p nach der Rotation wieder gleich wie vor dem Einfügen, sodaß eine Betrachtung des Vaters von p nicht mehr nötig ist. (2) k ist der rechte Sohn von p. Dieser Fall verläuft symmetrisch zum Fall 1. Für 2c sind hier entsprechend Linksrotationen und Doppelrotationen nach rechts-links notwendig.

Abbildung 3: Einfache Rotation nach rechts

Verpacken wir nun unser neues Wissen in ein Programm. Betrachten Sie dazu Listing 2. Auch für die AVL-Bäume benötigen wir einen Konstruktor (namens avl), dem die zu verwendende Vergleichsfunktion übergeben werden muß. Am Anfang stehen die Rotationsroutinen nach links, rechts, links-rechts und rechts-links. Die Einfachrotationen sind nicht schwer nachzuvollziehen. Nach der Rotation haben sowohl der Knoten k als auch p immer die Balance 0. Bei den Doppelrotationen ist es schon etwas schwieriger. Sie setzen sich, wie der Name schon sagt, aus zwei Einzelrotationen zusammen. Nehmen wir das Beispiel einer links-rechts-Rotation in Abbildung 4. Zuerst wird der Knoten k nach links rotiert. Danach erfolgt eine Rechtsrotation des Knotens p. Der dadurch an die Spitze kommende Knoten - in der Abbildung mit q bezeichnet - hat danach immer die Balance 0, da der Baum wieder vollständig ausbalanciert wurde. Schwieriger zu erkennen ist aber, welche Balancen die Knoten p und k erhalten. Dazu betrachten wir die unter dem Teilbäumen stehenden Höhen. Wie Sie am ursprünglichen Baum sehen, hat der Knoten q entweder links oder rechts einen kürzeren Teilbaum (sofern q nicht das eben eingefügte Blatt ist). Je nachdem, ob nun der linke Sohn von q kleiner ist oder der rechte, hat q vor der Rotation die Balance +1 bzw. -1. Aus der Abbildung entnehmen wir nun, wie die Teilbäume durch die Rotation neu verteilt wurden. Wie Sie sehen, bekommt k den Teilbaum 2 als rechten Sohn und p den Teilbaum 3 als linken Sohn. War nun der Teilbaum 3 der kürzere, dann bekommt k die Balance 0 und p die Balance +1. War hingegen der Teilbaum 2 kürzer, dann wird ß(k)=-1 und ß(p)=0. Der dritte Fall tritt auf, wenn q unser eben eingefügtes Blatt war, in diesem Fall setzen wir sowohl die Balance von p als auch die Balance von k auf 0.

Abbildung 4: Doppelrotation nach links-rechts

Nach den Rotationsfunktionen ist die Suchroutine zu finden. avl_find sieht tree_find aus Listing 1 sehr ähnlich, es gibt aber einen entscheidenden Unterschied. Da die Einfüge- und Entferne-Operationen für AVL-Bäume im Extremfall eine Rückverfolgung vom eben eingefügten Knoten beginnend hinauf bis zur Wurzel erfordern, wird der beim Suchen zurückgelegte Pfad auf einem Stapel abgelegt. Auf diese Weise konnte vermieden werden, daß jeder Knoten eines AVL-Baumes auch einen Zeiger auf seinen Vater benötigt.

Die Prozedur avl_insert übernimmt das Einfügen eines Knotens in einen bestehenden AVL-Baum. An sie wird ein Zeiger auf den Baum und ein Zeiger auf den einzufügenden Knoten übergeben. Als Rückgabewert erhält man NULL für den Fall, daß alles gutgegangen ist. Ist jedoch im Baum schon ein Knoten vorhanden, der denselben Schlüssel hat, wie der einzufügenden Knoten, wird ein Zeiger auf diesen Knoten zurückgegeben und nichts eingefügt.

Die zweite, ebenfalls etwas schwer zu verstehende Operation ist das Entfernen eines Knotens aus einem AVL-Baum, im Listing 2 als avl_remove bezeichnet. Wir wollen nun die Funktionsweise dieses Algorithmusses besprechen. Ähnlich wie beim Entfernen aus einem natürlichen Binärbaum unterscheiden wir hier drei Fälle:

(1) Der zu entfernende Knoten k ist ein Blatt. In diesem Fall hängen wir es einfach von seinem Vater p ab und balancieren p neu aus. (2) k hat nur einen einzigen Sohn q. Wir setzen also - wie bei den natürlichen Bäumen - q an die Stelle von k und balancieren den Vater von k neu aus. (3) k hat zwei Söhne. Auch hier ersetzen wir k durch seinen symmetrischen Nachfolger, wie bei den natürlichen Bäumen besprochen. Jetzt interessiert es uns natürlich noch, wie die Ausbalancierung des Knotens p auszusehen hat. Wir werden auch hier nur den Fall untersuchen, daß p der linke Sohn seines Vaters v ist, da der umgekehrte Fall wieder symmetrisch verläuft. Wir untersuchen dazu die Balance des Vaters v. (3.a) v hat die Balance -1. In diesem Fall war die Höhe des linken Teilbaumes von v um einen Knoten höher als die Höhe des rechten Teilbaumes von v. Da wir nun den linken Teilbaum um eins reduziert haben, ist der Baum wieder ausgeglichen. Wir setzen somit ß(v)=0. Da sich nun aber die Höhe des Teilbaumes ab v um eins erniedrigt hat, müssen wir auch noch den Vater von v ausbalancieren. (3.b) v hat die Balance 0. Hier war der Knoten v höhenbalanciert, wir haben aber links einen Knoten entfernt. Deshalb muß die Balance auf +1 gesetzt werden. Beachten Sie aber bitte, daß sich die Höhe des Teilbaumes ab v nicht geändert hat, da der rechte Teilbaum von v immer noch gleich hoch ist wie vorher (und somit höher als der linke). Eine Betrachtung des Vaters von v ist in diesem Fall also nicht nötig. Da dies anfangs oft etwas schwer zu verstehen ist, zeigt Abbildung 5 ein Beispiel zu diesem Punkt. Wie Sie sehen, hat der linke Teilbaum vor der Rotation die Höhe 2, der gesamte Baum ab v die Höhe 3. Nach dem Entfernen von p erniedrigt sich der linke Teilbaum um eins. Da der rechte Teilbaum aber immer noch die Höhe 2 hat, bleibt die Höhe des gesamten Baumes ab v unverändert auf 3. (3.c) v hat die Balance +1. Hier ist eine weitere Fallunterscheidung nötig. Wir untersuchen nun den rechten Sohn von v, nennen wir ihn q. (3.c.1) ß(q)=0. In diesem Fall ist eine Rotation von v nach links erforderlich. Die Höhe des Baumes bleibt dabei unverändert, was ein Zurückverfolgen des Vaters von v unnötig macht. Die Balance von v wird dadurch auf +1 gesetzt und q erhält die Balance -1. (3.c.2) ß(q)=+1. Auch hier rotieren wir v nach links. Der Unterschied zum vorigen Fall besteht aber darin, daß sowohl die Balance von v als auch jene von q 0 wird, und auch die Höhe des Baumes um eins vermindert wird. Das erfordert die Ausbalancierung des Vaters von v. (3.c.3) ß(q)=-1. Hier sorgt eine Doppelrotation von v nach rechts-links für die Balancierung des Baumes. Da auch hier die Höhe des Baumes um eins gefallen ist, muß auch der Vater von v betrachtet werden.

Abbildung 5: Die Höhe ab v bleibt nach dem Entfernen von p unverändert

Auch die Entferne-Funktion ist in Listing 2 zu finden. Die beiden Unterprogramme leftRemoved und rightRemoved enthalten den eben besprochenen Ausbalancierungsalgorithmus. avl_remove ist der Einsprungspunkt zum Entfernen von Schlüsseln aus einem AVL-Baum. Es erwartet als Parameter den Zeiger auf den Baum und einen Zeiger auf den (nicht im Baum enthaltenen) zu entfernenden Beispielknoten. avl_remove liefert als Rückgabe einen Zeiger auf den entfernten Knoten oder NULL, wenn der Knoten nicht gefunden werden konnte.

Mit diesen Funktionen kann relativ einfach mit AVL-Bäumen gearbeitet werden. Selbst wenn Sie die ihnen zugrundeliegende Theorie nicht vollständig verstanden haben, sollten Sie in der Lage sein, die sich ergebenden Vorteile auszunutzen. Solche Bäume sind beispielsweise bei der Programmierung von Dateiverwaltungen sehr wichtig, wenn Sie mit index-sequentiellen Datensätzen arbeiten. Der damit erreichte Geschwindigkeitsvorteil ist enorm und rechtfertigt den Mehraufwand beim Programmieren gegenüber einem einfachen sequentiellen Suchen in linearen Listen. Es lohnt sich also, sich näher damit auseinanderzusetzen, denn wie so oft ist die einfachste Lösung doch nicht die beste.

Kursübersicht: Teil 1 -- Einführung und lineare Listen. Teil 2 -- Der Stapel und seine Anwendung. Teil 3 -- Der Baum. Teil 4 -- Anwendung von Bäumen. Teil 5 -- Hashverfahren Teil 6 -- Sortieren

Markus Öllinger ...........

Listing 3-1.c (shift-click!)

Listing 3-2.c (shift-click!)

Abbildung 3-1 (GIF;1K)

Abbildung 3-2 (GIF;1K)

Workshop Teil 1

Abbildung 3-3 (GIF;2K)

Abbildung 3-4 (GIF;3K)

Abbildung 3-5 (GIF;3K)

Gepackte Listings (LHA;4K)

Workshop Teil 2

....