Balancierte Binärbäume

Um Extremfälle, in denen Suchbäume zu einer linearen Liste degenerieren, zu verhindern, wendet man Balancierungskriterien an, die garantieren, dass selbst im schlimmsten Fall die Höhe des Suchbaumes in $O(\log n)$ liegt. Wir betrachten höhenbalancierte Suchbäume, kurz AVL-Bäume.