Baeume in Balance Schnelle Datenverwaltung mit dem AVL-Baum ----------------------------------------- c't 1/92 S.174 (ad) AVL\AVLPRCT2.C MAIN.C REK.EXE ITER.EXE Anbei finden Sie eine Implementierung der Datenstruktur AVL-Baum in der Programmiersprache C. Im wesentlichen besteht das Programm aus drei Teilen, naemlich Routinen fuer das Einfuegen, das Loeschen und das Suchen. Das Suchen bildet dabei den einfachsten und kuerzesten Teil (er unterscheidet sich nicht von Routinen zum Suchen in zufaelligen Binaerbaeumen). Interessanter wird es allerdings dann bei den Routinen fuer das Einfuegen und Loeschen. Die Funktion Einfuegen_in_Pfad_AVL ist die Funktion, die fuer das Einfuegen von Elementen in den Baum aufzurufen ist. Als Uebergabeparameter verlangt diese Funktion die Angabe der Wurzel des Baums, den einzufuegenden Wert und bei der rekursiven Implementierung noch eine beliebige Variable vom Typ short *. Weiter benutzt die Funktion Einfuegen_in_Pfad_AVL die Funktionen Links_Rotation und Rechts_Rotation. Hierbei sollte man sich einmal vor Augen fuehren, wie kurz und praegnant die doch so kompliziert erscheinenden Rotationen zu implementieren sind. Die Realisierung des Loeschens ist der Teil, der wie so oft am kompliziertesten zu handhaben ist. Die eigentliche Loeschfunktion ist die Funktion Loeschen_in_Pfad_AVL. Diese Funktion benoetigt die gleichen Uebergabeparameter wie die Funktion Einfuegen_in_Pfad_AVL. Zusaetzlich benoetigt man fuer das Loeschen die beiden Funktion Links_geloescht und Rechts_geloescht. Diese greifen wiederum auf die Funktionen Links_Rotation und Rechts_Rotation zu, und dienen dazu, die Balance des Baums zu erhalten. Die Funktion Links_loeschen wird nur bei der rekursiven Implementierung benoetigt, und dient dazu, das Loeschen von Knoten mit zwei Soehnen zu realisieren. Das Listing enthaelt sowohl eine rekursive als auch eine iterative Implementierung. Fr die rekursive Implementierung spricht die un- mittelbare Entsprechung der Definition der Datenstruktur und ihrer Implementierung. Doch wurde auch groer Wert auf eine iterative Implementierung gelegt, da sie erheblich schneller (ca. 25 Prozent) und in der Literatur kaum zu finden ist. Zwischen den einzelnen Varianten kann man leicht ber die bedingte Compilierung auswaehlen.