Jeder kennt den Gemüsegarten des Informatikers. In der einen oder anderen Form sind uns die verschiedenen Sorten des „Lieblingsgemüses“ Baum schon über den Weg gelaufen. Meistens verursachten sie Kopfschmerzen der Art „wie war das noch gleich, wie ging das? nein nein, so war das nicht...“. Hier möchte ich Sie mit der neuesten, vielleicht besseren Züchtung bekanntmachen: den sogenannten „Skip Lists“.

Keine Angst. Nicht allzu viel Theorie, jedoch einen einfachen Algorithmus werde ich vorstellen, der zudem noch universell einsetzbar ist. Ein paar Sätze über die Flora muß ich jedoch vorausschicken.

Bäume

... sind im Informatikergarten auf den Kopf gestellt. Die Wurzel hängt in der Luft, und die Äste und Blätter baumeln normalerweise nach unten. Einen regelrechten Stamm gibt es nicht. (Viel treffender wäre es, wenn man Bäume besser als Wurzelwerk bezeichnen würde, aber wir übernehmen ja alles aus dem Englischen.) Man unterscheidet häufig zwischen Bäumen und Graphen (letztere interessieren uns im folgenden nicht), wobei die Bäume eigentlich eine Spezialisierung des Gewächses Graph sind. In Bäumen steckt schon ein wenig mehr Semantik. Man assoziiert mit ihnen ein gewisses Aussehen und diverse Behandlungsmethoden. Doch dazu später mehr.

Die Stammsorte der Bäume besitzt 2 Äste (Bild 1b), von denen wir den einen „der Ordnung halber“ als seinen linken und den anderen als seinen rechten Sohn (schon wieder diese unzutreffenden Benennungen) bezeichnen.

Eine andere Sorte hat mehrere Äste, respektive Söhne oder Nachfahren. Wollen wir also die beiden Typen unterscheiden, spricht man von binären und n-ären Bäumen (Bild lb).

Jede Verzweigung (Knoten) im Baum enthält einen Identifikationswert. Häufig wird er auch Schlüssel (key) genannt. Bei manchen Baumsorten ist dieser Schlüssel Teil der Information, die dann in jedem Knoten gespeichert wird. Teilweise besteht die Information nur aus diesem Schlüssel. Andere Sorten enthalten nur in den Blättern (Endknoten, Knoten, die keine Söhne mehr haben) Informationen. Aber alle Sorten besitzen in jedem Knoten Schlüssel.

Über diese Informationen ist durch die Baumstruktur eine Ordnung definiert, und man legt im allgemeinen fest, daß alle Informationen in dem linken Sohn und all dessen Söhne kleiner als die Information des Knotens sind. Die der rechten Seite (alle weiter „rechts“ liegenden Geschwister) sind alle größer. Das Wort „kleiner“ hat es so in sich. Was bedeutet es, daß eine Information „kleiner“ als eine andere ist? Bei Zeichenketten bedeutet es wohl, daß eine Zeichenkette lexikalisch kleiner als eine andere ist. Bei Zahlen bedeutet es offensichtlich mathematisch kleiner, also „links“ auf dem Zahlenstrahl.

Kennt man die Definition von „kleiner“, kann man in einem Baum sehr schnell nach Informationen suchen, indem man den Schlüssel der zu suchenden Information mit demjenigen des gerade aktuellen Knotens vergleicht und es abhängig von dem Ergebnis mit einem der Söhne weiterversucht.

Wo wachsen die Bäume?

Häufig werden sie in arrays gepflanzt (Bild 2a). So z.B. die GEM-Resourcen von Programmen, die mit dem Resource-Construction-Set erstellt wurden. (Anmerkung: Ein Objekt in der Resource ist kleiner als das andere, wenn es sich grafisch gesehen innerhalb des anderen befindet.) Solche Bäume wachsen in einem festen Beet und können somit eine bestimmte Größe, respektive die Anzahl der Verzweigungen nicht überschreiten. Viel schöner, aber auch aufwendiger zu pflegen, sind die dynamischen Bäume (Bild 2b), deren Größe von vornherein nicht feststeht, und die zur Laufzeit aufgebaut werden. Und mit diesen werden wir uns hier näher beschäftigen.

Für mathematisch Interessierte: Der Aufwand zum Suchen einer Information in einem n-ären Baum (ein Baum mit maximal n Söhnen) - und damit ist auch die Unterscheidung, ob es diese Information gibt oder nicht, gemeint - ist 0(log(m)) (Logarithmus zur Basis n. Es befinden sich maximal m Informationen in dem Baum). Zum Vergleich: Lineares Suchen, d.h. alle Informationen der Reihe nach untersuchen, dauert im ungünstigsten Fall, also, wenn alle Informationen zu untersuchen sind (z.B. die Information ist nicht vorhanden), m-Zeiteinheiten. Der Aufwand ist damit O(n). Bei einer großen Anzahl von Informationen macht sich das erheblich bemerkbar.

Kranke und mißratene Bäume

Aber Bäume sind beim Wachsen und während ihrer Lebenszeit (in der sie manchmal auch gestutzt werden müssen) ständigen Gefahren ausgesetzt. Beide Phasen eines Baumlebens münden in dasselbe Krankheitsbild: degenerierte Bäume. Beim Wachsen eines Baumes bilden sich immer neue Blätter, und es besteht die Möglichkeit, daß immer nur der rechte Ast Söhne bekommt und die anderen Söhne unfruchtbar bleiben. Resultat: der Baum „hängt schief“ (Bild 3b).

Dies wirkt sich fatal für Suchalgorithmen aus. Einige Informationen werden erheblich schneller gefunden als andere. Die durchschnittliche Suchdauer ist größer als bei einem optimal ausbalancierten Baum. Hoppla: optimal ausbalanciert ist ein Begriff, der erst mal erklärt werden muß.

Bildlich gesprochen bedeutet es. daß das Astwerk schön buschig ist, daß, um technischer zu werden, die maximale Astlänge sich von der minimalen Astlänge nur um ein Mindestmaß unterscheidet. Im Normalfall bedeutet dies eine maximale Differenz von einer Astlänge. Die oben erwähnte mathematische Formel ist nur für ausgeglichene Bäume gültig (Bild 3a).

Insofern ist man bestrebt, diesen Fall nicht eintreten zu lassen. Manchmal läßt er sich aber nicht vermeiden. Auch wenn Blätter absterben, kann es passieren, daß davon immer nur ein Ast betroffen ist.

Medizin für Bäume

Die Informatik hat [Adelson, Velskii und Landis sei Dank] Abhilfe durch sogenannte AVL-Bäume geschaffen. Die benötigten Algorithmen garantieren, daß in der Wachstums- und Lebensphase keine Krankheitssymptome auftreten, d.h. die Differenz der Länge der Äste zwischen zwei verschiedenen Söhnen eines jeden Vaterknotens maximal eine Einheit ist. Trifft diese Bedingung auch für den Urvater, die Wurzel des Baumes, zu, spricht man von einem ausgeglichenen Baum.

Die Medizin ist jedoch nicht ohne Nebenwirkungen. Die entsprechenden Algorithmen benötigen Speicherplatz für die Routinen und zur Laufzeit evtl, einen ausreichend großen Stack (wie groß ist das?) wegen des rekursiven Layouts der Funktion (Ok, heutzutage vemachlässigbar und für Besserwisser: Ich weiß auch, es gibt nichtrekursive Verfahren, aber siehe den nächsten Absatz). Weiterhin wird die Laufzeit (dito) oder um im Jargon zu bleiben, die Durchflußgeschwindigkeit der Informationen durch den Baum durch die zusätzlichen Testfunktionen gehemmt.

Und, die Arznei muß sorgfältig hergestellt (programmiert) werden. Letzteres ist häufig der Grund, auf diese Medizin zu verzichten. (Hoffen und Bangen, daß die einzufügenden Informationen in zufälliger Reihenfolge auftreten, da nur dies ein zufriedenstellendes Wachstum ohne Krankheitssymptome ermöglicht.)

Genmanipulation

Da dem nun so ist, versuchte William Pugh [1] einen anderen Ansatz. Und über diesen möchte ich hier berichten. Das Problem läßt sich folgendermaßen charakterisieren:

• Wie läßt sich ein Baum möglichst gleichmäßig aufbauen, ohne daß man die Schlüsselreihenfolge kennt oder gar beeinflussen kann?
• Oder wie lassen sich die Informationen in eine zufällige Reihenfolge bringen, die beim Einsortieren der Informationen einen ausgeglichenen Baum realisieren?

Eine Antwort: Der Aufbau des Baumes muß unabhängig von den Informationen gestaltet werden, also unabhängig von der Ordnung, respektive den Schlüsseln der Informationen. Wie soll das gehen?

In einem Baum bisherigen Typs wird beim Einfügen mit Hilfe des Schlüssels die Stelle gesucht, an der die Information eingefügt werden soll. Und genau diese Stelle müssen wir uns auf andere Weise unabhängig von dem Schlüssel besorgen.

Dabei ist natürlich die Sortierung des Baumes, bestimmt durch unsere „kleiner“-Relation, zu beachten.

Wählen wir einen (nicht ganz passenden) Vergleich aus dem richtigen Leben: Wir suchen eine Telefonnummer in der dicken gelben Schwarte. Man greife also mit der rechten Hand unter das Buch, die Finger der linken Hand liegen auf dem Deckel, und mit dem Daumen hebt man eine „zufällige“ Anzahl Seiten hoch. Wir stellen fest, daß unser Suchbegriff sich entweder im führenden Teil oder im nachfolgenden Teil des Buches befindet. Die Hand greift zwischen die aufgeschlagenen Seiten, und der Vorgang wiederholt sich mit dem Rest des Buches. (Natürlich wird irgendwann sequentiell geblättert.) Probieren Sie’s mal bei diesem Heft mit dem Suchkriterium „Seitenzahl“, ist ja dick genug.

Zentrale Eigenschaft dieses Algorithmus’ ist die Zufälligkeit, mit der wir auf eine bestimmte Seitenzahl stoßen. Wir überspringen dabei eine zufällige Zahl von Blättern.

Pugh wählte eine andere Beschreibungsmethode:

Durch eine aufsteigend sortierte Liste wird sequentiell nach einem Begriff gesucht. Stellen Sie sich eine Straße mit Häusern vor. Die geraden Nummern auf der rechten, die anderen auf der linken Seite. Sie suchen, die Straße entlangradelnd (bei der Hausnummer 1 beginnend) Hausnummer „n“. Dabei werden Sie natürlich nicht den Blick immer pendelnd zwischen den Straßenseiten hin- und herbewegen, sondern immer nur eine Seite (in Deutschland bevorzugt die rechte) mit dem Blick schräg nach vorne betrachten, und im rechten Augenblick, nämlich dann, wenn man kurz vor der entsprechenden Nummer ist, den Kopf der richtigen Seite zuwenden. Dabei werden Hausnummern, die unleserlich oder nicht vorhanden sind, einfach außer acht gelassen. Wir überspringen bei diesem Verfahren mindestens jede 2. Hausnummer.

Wie wäre es, wenn wir nicht jede 2. Hausnummer, sondern mehrere auf einmal überspringen (dabei könnten wir schneller fahren), und erst kurz vor dem Ziel langsamer werdend, weniger Hausnummern überspringend, genauer hinschauen würden.

Begriffen? In dem Fall schauen Sie sich jetzt Bild 4a an. Dort ist eine sequentielle Liste mit dargestellt, mit jeweils verschiedener Anzahl von Verweisen auf weiter hinten liegende Elemente. Wenn wir in dieser Liste einen Schlüssel (hier eine Zahl) suchen, folgen wir, von vorne beginnend, zuerst den Pfeilen, die am weitesten nach hinten zeigen (den oberen). Ist der Schlüsselbegriff in der Information, auf die der Pfeil steht, kleiner oder gleich demjenigen, den wir suchen, setzen wir die Suche mit der Gruppe von Pfeilen fort, die PI mal Daumen nur noch halb so weit zeigen. Das setzen wir solange fort, bis wir entweder das Element gefunden haben, oder wir bei Level 0, d.h. der Pfeil zeigt auf das nächste Element in der sortierten Liste, angekommen sind. Alles klar? Das ist das Prinzip.

Was passiert, wenn wir einen neuen Schlüsselbegriff einfügen möchten? Wir müssen uns nicht überlegen, wo wir ihn einsortieren wollen (das legt ja unsere Ordnung „kleiner“ auf dem Schlüsselbegriff fest), sondern ob wir ihn als Sohn oder als Enkel usw. behandeln wollen. Am besten, wir überlassen dies dem Zufall. Und genau das ist die entscheidende Idee:

Instrumente

Wenn wir den Baum aufbauen, überlassen wir es dem Zufall, auf welcher Ebene des Baumes ein neuer Knoten angeordnet wird - also ob er als Sohn, Enkel, Urenkel usw. behandelt wird.

Da der Zufall halt „zufällig“ ist, verteilen sich die Schlüsselbegriffe auch zufällig auf die verschiedenen Ebenen der Nachfahren (Söhne, Enkel ...) unseres Baumes (wie Bild 4b zeigt). Setzen wir einen Zufallszahlengenerator voraus, der gleichverteilte Zahlen eines eingeschränkten Wertebereiches liefert, und ordnen wir jedem Level von Nachfahren eine dieser Zahlen des Wertebereichs fest zu, also z.B. der Wurzel eine 1, den Söhnen eine 3, den Enkeln eine 2 ..., so erfolgt dadurch der Aufbau des Baumes durch Einführung als entsprechender Nachfahre rein zufällig, und damit mit hoher Wahrscheinlichkeit gleichmäßig. Die Zuordnung muß so erfolgen, daß es prinzipiell mehr Enkel als Söhne, als Väter ... gibt. Das ist noch ein Problem!

Alle Ebenen sind damit mit der richtigen Häufigkeit vertreten, (eine genügend große Zahl von Informationen vorausgesetzt.) Um es noch einmal zu sagen: Die Struktur des Baumes ist von der Struktur und Reihenfolge der Information abgekoppelt. Auch das Löschen von Knoten innerhalb des Baumes löscht einen zufälligen Knotentyp (Enkel, Urenkel...), so daß insgesamt die gleichmäßige Struktur des Baumes erhalten bleibt. (Anmerkung: Natürlich lassen sich Arbeitsweisen finden, bei denen sich auch dieser Algorithmus nicht so gut verhält.)

Alles hängt von einem geeigneten Zufallszahlengenerator ab. Der Aufbau des Baumes ist also von der Reihenfolge der Schlüsselbegriffe unabhängig, die somit willkürlich, z.B. auch sortiert sein kann, er hängt von der Reihenfolge der Zufallszahlen ab. (Anmerkung: Gerade sortierte Schlüsselfolgen bereiten konventionellen Algorithmen große Probleme.)

random

Der Zufallszahlenalgorithmus ist nicht beliebig wählbar. Er muß bestimmte Zahlen bevorzugen. Wir wollen, wie oben schon erwähnt, mehr Väter als Söhne haben. Um genauer zu sein: es müssen doppelt soviele Söhne erzeugt werden wie Väter vorhanden sind, um ein optimales Ergebnis zu erzielen. (Verzwickt dabei ist, daß die Anzahl der Väter eigentlich nicht feststeht.) Je besser uns dieses gelingt, desto buschiger gestaltet sich unser Baum. Genau dieses versucht die Funktion randomLevel, und damit kommen wir zum Algorithmus.

Wir benötigen eine Initialisierung des gesamten Systems mittels der Prozedur init_skip-lists. Hier wird nur der Zufallszahlengenerator initialisiert. Es lohnt sich nicht, diese Informationen lokal je „skip list“ zu halten, da wir dann für jede einen solchen benötigten.

Jede aktive „skip list“ benötigt die Verwaltungsstruktur listStructure, die den Startknoten, das zu jeder Zeit maximale Level (wieviele hierarchische Nachfahren-Ebenen existieren noch) und zwei Zeiger auf Funktionen erhält. Sie ermöglichen die unabhängige Gestaltung der „skip list“-Funktionen, so daß mit den gleichen Routinen mehrere unterschiedliche Bäume (z.B. zum Umsortieren) behandelt werden können.

Die Funktion *cmp_fun erhält zwei Informationen als Argumente und muß entscheiden, welches von beiden „kleiner“ als das andere ist, oder ob sie „gleich“ sind. Ihre Rückgabewerte entsprechen im ganzen gesehen denen der Funktion strcmp. Genaueres siehe die Header-Datei „skiplist.h“.

Die Funktion *free_fun erhält eine Information als Argument und entscheidet, was mit ihr nach dem Entfernen aus der „skip list“ geschehen soll.

Das Feld last enthält einen Verweis auf das letzte gesuchte Element. Diese Positionsinformation wird genutzt, um auf die nachfolgenden Informationen zuzugreifen.

Für jede zu speichernde Information benötigen wir einen Zeiger auf die Information und eine sich nach dem Level richtende Anzahl von Zeigern auf die nächsten Informationen. Diese Daten sind in der Struktur nodeStructure gespeichert.

Mittels der Prozedur new_skiplist erzeugen wir eine Verwaltungsstruktur für eine neue „skip list“. Wir benötigen einen Startknoten, l->header, in dem wir nur die Tabelle der Zeiger auf nachfolgende Elemente der verschiedenen Levels speichern. Das Feld l->header.inf bleibt leer. Alle anderen Felder werden mit NULL initialisiert. Dieser Wert indiziert das Ende der Informationsketten.

In die „skip list“ fügen wir Informationen durch die Funktion skip_insert ein. Als Parameter werden die „skip list“, die Information und der Boolsche Wert dp benötigt. Dieser entscheidet, ob doppelte Informationen in der Liste erlaubt sein sollen. Ist der Wert äquivalent zu Null, sind sie nicht erlaubt. Die Funktion sucht, beim maximalen Level beginnend, nach Informationen, deren Schlüssel kleiner als die mitgelieferte Information ist. Übrigens sind die Schlüssel immer Teil der Information. Die Tabelle update enthält in Stelle k die Adresse des letzten Knotens, der „kleiner“ als die neue Information ist. Falls die Information eingefügt werden soll, sind diese Werte an den entsprechenden Stellen zu modifizieren. Es wird „FALSE“ zurückgegeben, falls die Information schon vorhanden war, „TRUE“, falls sie eingefügt werden mußte.

skip_delete löscht eine Information und gibt „TRUE“ zurück, falls der Auftrag ausgeführt, „FALSE“, falls keine Information gefunden wurde. Auch hier wird als erstes nach der Information gesucht, indem man zuerst mit den am weitesten zeigenden Verweisen („k = l->level“) beginnt und schließlich bei den niedrigsten Verweisen endet („k = 0“).

Mit Hilfe von skip_search ist der Zeiger l->last auf einen Teil des Suchbaumes einstellbar, von dem man dann mit skip_next auf die nachfolgenden Elemente zugreifen kann. Wurde die Information nicht gefunden, oder ist das Ende der Informationskette erreicht, wird „NULL“ zurückgeliefert. Ein nachfolgender skip_next-Aufruf beginnt am Anfang der Informationen.

Restriktionen und mögliche Verbesserungen

Nun, es gibt sie doch. Das Verfahren des Zufallszahlengenerators erlaubt eine maximale Hierarchietiefe von 16. Das bedingt, daß der Algorithmus im vorliegenden Fall „optimal“ bis zu einer maximalen Anzahl von 2 hoch 16 unterschiedlichen Informationen funktioniert. Darüber hinausgehende erfolgreiche Einfügungen werden zwar verkraftet, reduzieren aber die Leistungsfähigkeit des Algorithmus’.

Ist die hohe Flexibilität nicht gefordert, lassen sich Vergleichs- und Speicherfreigabefunktionen direkt kodieren. Im vorgestellten Fall werden sie aber über ein Unterprogramm aufgerufen, das die Geschwindigkeit des Algorithmus’ etwas mindert.Die Information läßt sich anstelle einer Verzeigerung auch einfach direkt in node-Structure kodieren, um so einen Effizienzgewinn zu erreichen. Dann allerdings benötigt man für jeden aktiven Baum einen eigenen Algorithmus.

Eine weitere Optimierung besteht in der Definition eines Elements mit einem maximalen Wert, der im Falle von erlaubten Duplikaten oder nicht sicherem Auftreten niemals eingefügt werden darf. Dadurch kann die Abfrage auf „NULL“ ersatzlos gestrichen werden.

Das Programm

Das Beispielprogramm nimmt eine Textdatei als Eingabe und sortiert die darin enthaltenen Wörter (alles, was durch mindestens ein Leerzeichen getrennt ist, führende und abschließende Kontrollzeichen werden ignoriert) in eine „skip list“ ein. Die gesamte Datei wird in den Speicher geladen, um auf zusätzliche malloc-Aufrufe zu verzichten. Ein Aufruf der Funktion „strtok“ modifiziert destruktiv diesen Puffer und separiert so alle gefundenen Wörter.

Ein kleines Schmankerl am Rande: Das Programm schafft es, die deutschen Sonderzeichen ‘ä’, ‘ö’ ‘ü’ und ‘ß’ richtig zu sortieren.

Die gewonnenen Informationen werden, um alle Wörter die mit einem ‘m’ beginnen, vermindert, ausgegeben. Sie könnten jetzt korrekturgelesen werden. Ein paar statistische Informationen, wieviele Knoten sich auf welchen Levels befinden, werden zur Kontrolle ebenfalls geliefert. Level 0 sollte die größte Anzahl Knoten, das größte Level die kleinste Anzahl liefern. Ist dies im Ganzen gesehen nicht der Fall, haben Sie entweder eine der wenigen Ausnahmen gefunden (sehr unwahrscheinlich) oder beim Abtippen einen Fehler gemacht (sehr wahrscheinlich).

Was bringt’s

• Die Routinen sind klein und schnuckelig und portabel; unter Turbo C auf dem Atari belegen sie mit allem drum und dran weniger als 800 Bytes, (vielleicht kann sie ja ein Assembler-Programmierer effizienter gestalten).
• Sie sind universell einsetzbar, da konfigurierbar. Man braucht sie nur einmal im Programm zu haben.
• Sie liefern einen zufällig „ausgeglichenen“ Baum, dem auch intensive Operationen nichts anhaben können.
• Sie sind schnell. Sag’ ich ganz einfach einmal. Lediglich bei der Suchzeit müssen sie im Vergleich zu optimal programmierten, nicht-rekursiven AVL-Bäumen ganz leicht zurückstecken. Rekursive Verfahren schneiden schlechter ab. Einfüge- und Ausfügeoperationen sind jeweils wesentlich schneller. Nähere Informationen dazu kann man in dem unten angeführten Artikel nachlesen.

[1] William Pugh „skip list“s: A probabilistic alternative to balanced trees; Communications of the ACM; June 1990, Vol 33, Number 6