AVL-Bäume sind eine spezielle Art von selbstbalancierenden binären Suchbäumen, die von den Mathematikern Georgy Adelson-Velsky und Evgenii Landis im Jahr 1962 eingeführt wurden. Sie garantieren, dass die Höhe des linken und rechten Teilbaums eines Knotens sich um höchstens 1 unterscheidet, um eine effiziente Suchzeit zu gewährleisten. Diese Eigenschaft wird als AVL-Bedingung bezeichnet und sorgt dafür, dass die maximale Höhe eines AVL-Baums mit Knoten durch die Formel begrenzt ist.
Um die Balance nach Einfüge- oder Löschoperationen aufrechtzuerhalten, können Rotationen (einzeln oder doppelt) durchgeführt werden. AVL-Bäume sind besonders nützlich in Anwendungen, bei denen häufige Suchoperationen erforderlich sind, da sie im Durchschnitt eine Zeitkomplexität von für Suche, Einfügen und Löschen bieten.
Starte dein personalisiertes Lernelebnis mit acemate. Melde dich kostenlos an und finde Zusammenfassungen und Altklausuren für deine Universität.