Das Profil zufälliger Binärsuchbäume

The profile of binary search trees

Binärsuchbäume sind eine wichtige Datenstruktur, die in der Informatik vielfach Anwendung finden. Ihre Konstruktion ist deterministisch, zur Analyse ihrer Eigenschaften wird aber eine rein zufällige Eingabe zugrundegeleg
Binärsuchbäume sind eine wichtige Datenstruktur, die in der Informatik vielfach Anwendung finden. Ihre Konstruktion ist deterministisch, zur Analyse ihrer Eigenschaften wird aber eine rein zufällige Eingabe zugrundegelegt. Viele Größe, wie z.B. Tiefe, Höhe und Pfadlänge werden seit Jahren viel untersucht. Als besonders interessant hat sich die Analyse des Profils, der Anzahl Knoten einer bestimmten Tiefe herausgestellt. In dieser Arbeit wird ein funktionaler Grenzwertsatz für das am Erwartungswert normierte Profil vorgestellt. Dazu werden unterschiedliche Zugänge gewählt, die hauptsächlich auf dem sogenannten Profil-Polynom beruhen. Zunächst wird ein klassischer Zugang mit Hilfe von Martingalen besprochen. Der diskrete Prozess wird dazu auf kanonische Weise in ein zeitstetiges Modell (Yule-Prozess) eingebettet. Ergebnisse im kontinuierlichen Prozess werden dann durch Stoppen auf den diskreten übertragen. Zudem wird ein neuerer Zugang vorgestellt, der auf der Kontraktionsmethode in Banachräumen unter Verwendung der Zolotarev-Metrik beruht.
show moreshow less
Binary search trees are an important data structure in Computer Science. Their construction is deterministic, for analyzing their typical behavior a random input is assumed. Many quantities like depth, height and path le
Binary search trees are an important data structure in Computer Science. Their construction is deterministic, for analyzing their typical behavior a random input is assumed. Many quantities like depth, height and path length have been studied for years. The analysis of the profile, the number of nodes on a certain level has turned out to be quite interesting. In this work a functional limit theorem for the profile, normalized by its expectation, is presented. Two different approaches, both based upon the so-called profile-polynomial, are presented. A classical approach based upon martingales is discussed. The discrete process is embedded in a time-continuous model (Yule-process) in a canonical way. Results for the continuous process are transferred to the discrete one by making use of stopping times. Secondly, a new approach based on to the contraction method in Banach spaces using the Zolotarev metric is presented.
show moreshow less

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Author:Henning Sulzbach
URN:urn:nbn:de:hebis:30-38988
Advisor:Ralph Neininger
Document Type:Diplom Thesis
Language:German
Year of Completion:2006
Year of first Publication:2006
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Granting Institution:Johann Wolfgang Goethe-Universität
Release Date:2007/03/28
Tag:Analyse von Algorithmen; Binärsuchbaum ; Kontraktionsmethode ; Zolotarev-Metrik
SWD-Keyword:Martingal
HeBIS PPN:18531628X
Institutes:Mathematik
Dewey Decimal Classification:510 Mathematik
MSC-Classification:60F17 Functional limit theorems; invariance principles
60G42 Martingales with discrete parameter
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
68W40 Analysis of algorithms [See also 68Q25]
Sammlungen:Universitätspublikationen
Licence (German):License Logo Veröffentlichungsvertrag für Publikationen

$Rev: 11761 $