Mathematik
Refine
Year of publication
- 2008 (1)
Document Type
- diplomthesis (1) (remove)
Language
- German (1)
Has Fulltext
- yes (1)
Is part of the Bibliography
- no (1)
Keywords
- Knotenabstand (1) (remove)
Institute
- Mathematik (1)
Ein universeller zentraler Grenzwertsatz für den Abstand zweier Kugeln in zufälligen Splitbäumen
(2008)
In der vorliegenden Arbeit wird ein Modell des zufälligen Splitbaumes untersucht. Dies ist ein verallgemeinertes Modell, das bei passender Wahl der zugehörigenParameter viele konkrete Suchbäume umfasst. Das Modell ist in der Arbeit von L. Devroye beschrieben: Nach einem zufallsbasierten Algorithmus werden den Knoten des Baumes Daten in Form von Kugeln hinzugefügt. Tiefe und Höhe sind dabei grundlegende Größen, die die Komplexität von Suchoperationen beschreiben, wenn das Suchbaummodell als Datenstruktur verwendet wird. Das Augenmerk der Arbeit richtet sich auf eine weitere entscheidende Größe: Den Abstand zweier rein zufällig gewählter Kugeln im Baum. Aufbauend auf Devroyes Erkenntnissen zum asymptotischen Verhalten der Tiefe der zuletzt eingefügten Kugel im Splitbaum, wird ein neues Resultat erzielt: Ein universeller Zentraler Grenzwertsatz für den Abstand der Kugeln. Als Anwendungsbeispiel werden zwei vom allgemeinen Modell abgedeckte Suchbäume betrachtet und der jeweilige Grenzwertsatz für die Abstände aus dem universellen Satz abgeleitet.