Mathematik Informatik Philosophie Diverses Kontatkt FAQ
Benutzername:
Passwort:
 Home > News
Freitag, 26. Mai 2017 13:15 
AVL-Bäume: Ausgeglichene binäre Suchbäume
 
Geschrieben von Alexander am Samstag, 27. Mai 2006

Das Suchen, Einfügen und Entfernen eines Schlüssels in einem zufällig erzeugten binären Suchbaum mit N Schlüsseln ist zwar im Mittel O(log(N)) Schritten ausführbar. Im schlechtesten Fall kann jedoch ein Aufwand von der Ordnung Theta(N) zur Ausführung dieser Operation erforderlich sein, weil der gegebene Baum mit N Schlüsseln zu einer Liste degeneriert ist. Es ist daher natürlich, durch zusätzliche Bedingungen an die Struktur der Bäume ein Degenerieren zu verhindern. Die Operationen zum Einfügen und Entfernen werden dann allerdings komplizierter als für natürliche Bäume.

Im Einzelnen werden behandelt:
  • Kosten für das Einfügen (insert), Löschen (delete) und Suchen (member) in AVL-Bäumen
  • Definitionen: AVL-Baum als spezieller binärer Suchbaum, Balancefaktor, bal(v), linker Teilbaum, rechter Teilbaum, Algorithmus isbalanced, Beispiele
  • Operationen auf AVL-Bäumen, 4 elementaren Operationen auf AVL-Bäumen, Doppelrotation, einfache Rotation, wann welche Operation?, Schema für die Doppelroation und die einfache Rotation, Doppelrotation = zwei einfache Rotationen
  • Löschoperationen

AVL-BäumeAVL-Bäume
Alle Logos und Warenzeichen auf dieser Seite sind Eigentum der jeweiligen Besitzer und Lizenzhalter.
Im übrigen gilt Haftungsausschluss. Weitere Details finden Sie im Impressum.
Die Inhalte dieser Seite sind als RSS/RDF-Quelle verfügbar.
Die Artikel sind geistiges Eigentum des/der jeweiligen Autoren,
alles andere © 2004 - 2017 by mathematik-netz.de

Seitenerstellung in 0.0721 Sekunden, mit 54 Datenbank-Abfragen