Anhang A: Performance von AVL-Bäumen
In diesem Anhang gehe ich näher auf die Performance von AVL-Bäumen ein. Ich habe diese Bäume in Kapitel 5 vorgestellt. Ich rate dir dringend, dieses Kapitel zu lesen, bevor du hier weiterliest.
![[Bild]](/api/v2/epubs/9783747509104/files/Images/image_a-1.jpg)
AVL-Bäume weisen eine Laufzeit von O(log n) für die Suche auf. Aber etwas sorgt für Verwirrung. Sieh dir diese beiden Bäume an. Bei beiden beträgt die Laufzeit für die Suche O(log n), obwohl ihre Höhe unterschiedlich ist! Wie kann das sein?
![[Bild]](/api/v2/epubs/9783747509104/files/Images/image_a-2.jpg)
(Gestrichelte Knoten stehen für Lücken im Baum.)
Bei einem AVL-Baum dürfen ...
Get Algorithmen kapieren - Visuell lernen und verstehen mit Illustrationen, Alltagsbeispielen und Python-Code now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
