Einführung

Ein binärer Suchbaum hält Werte geordnet: Der linke Teilbaum jedes Knotens enthält kleinere Werte und sein rechter Teilbaum enthält größere Werte. Diese Ordnung macht die Suche schnell, aber nur, wenn der Baum annähernd ausbalanciert bleibt. Fügt man Werte in sortierter Reihenfolge in einen einfachen binären Suchbaum ein, degeneriert er zu einer geraden Linie, wodurch jede Suche zu einem langsamen, linearen Scan wird.

Ein AVL-Baum behebt dies, indem er sich automatisch ausbalanciert hält. Nach jedem Einfügen oder Löschen prüft er, ob ein Knoten einseitig geworden ist, und führt gegebenenfalls eine kleine lokale Korrektur durch, die als Rotation bezeichnet wird, um das Gleichgewicht wiederherzustellen. Egal wie man ihn aufbaut, ein AVL-Baum degeneriert niemals zu einer Linie.

In diesem Kurs werden Sie einen AVL-Baum von Grund auf in Ihrer bevorzugten Sprache erstellen: Knoten mit verfolgter Höhe, Balance-Prüfungen, die vier Rotationsfälle sowie ein selbstbalancierendes Einfügen und Löschen. Anschließend werden Sie Ihre fertige Klasse verwenden, um eine Reihe von Übungsaufgaben zu lösen.