|
|
|
|
|
|
|
Ein AVL-Baum ist eine Datenstruktur aus der Informatik. Es handelt sich um einen Binärbaum, bei dem in jedem Knoten folgende Bedingung – die AVL-Bedingung – gilt:
Die Höhe des linken Teilbaums unterscheidet sich von der Höhe des rechten Teilbaums maximal um 1. |
|
|
|
|
|
AVL-Baum (Beispiel)
Die Höhe eines (Teil-)Baumes ist dabei definiert als das Maximum aller Abstände der im (Teil-)Baum enthaltenen Knoten von der Wurzel.
Diese Bedingung ist schwächer als die Forderung nach vollständiger Balanciertheit, stellt aber trotzdem sicher, dass der Baum nicht zu einer linearen Liste ausarten kann. Alle Operationen (Suchen, Einfügen und Löschen) sind immer mit Aufwand O(log N) durchführbar.
Nach jedem Einfügen oder Löschen eines Knotens wird in all seinen Vorgängern bis zur Wurzel überprüft, ob nun die AVL-Bedingung verletzt ist. Dies geschieht auf dem "Rückweg" der rekursiven Aufruffolge, es ist also nicht notwendig, einen separaten Prüf- und Korrekturlauf zu implementieren.
Ist an einem Knoten die Bedingung nicht mehr erfüllt, kann sie durch wenige Umordnungen von Kanten am betreffenden Knoten, seinem Vorgänger und den beiden Nachfolgern wieder hergestellt werden. Dazu ist es allerdings notwendig, in jedem Knoten die Zusatzinformation zu speichern, welcher seiner beiden Teilbäume höher ist. Sämtliche auftretenden Fälle (z.B. linker Teilbaum war vorher schon höher und ist nun noch höher geworden) lassen sich vorweg erfassen und programmieren.
Nachdem die AVL-Bedingung an einem Knoten verletzt und wieder hergestellt wurde, sind keine weiteren Korrekturen mehr notwendig.
Der Name AVL leitet sich von den Erfindern Adelson-Velskii und Landis ab. |
 |
|
|
|
|
Person(en):
Zeitraum:
Firma:
Verwandte Kategorien: |
kein Eintrag vorhanden
- -
kein Eintrag vorhanden
EDV-Fachbegriffe |
|
Es gibt 29 weiterführende Erklärungen oder Definitionen:
Aufruf, Bedingung,  Binär, Binärbaum, Daten, EIDE, Erfassen, Finder, Format, Inform, Informatik, Information, Kant, kursiv, Line, Linear, Link, Linker, Liste, löschen, NDIS, Opera, Operation, Programm, Ratio, Satz, Speicher, WAND, Word
|
|
Veröffentlicht am:
Zuletzt bearbeitet am:
Referenz:
|
12.07.2004 von Wilhelm Janssen (7094) Beiträge
12.07.2004 von Wilhelm Janssen
Wikipedia
|
| ..... Dieser Artikel aus Wikipedia wird durch die GNU FDL lizenziert. ..... |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Bei WinTotal finden Sie Programme und Tools für Microsoft Windows
|
|
| Werbung |
|
| | | | |
|
Bei Validome können Sie Ihre Website auf barrierefreies HTML testen |
|
|
