Analysis of data structures and tree-like structures

The aims of this project are twofold: First we want to give mathematically well-founded average-case analyses for certain data structures that are of interest and relevance in computer science, but whose behaviours are up to now not very well studied. In contrast to the worst-case analysis, where one considers the unfavourablest case, one wants to examine the average behaviour of relevant parameters (running time, space requirements, etc.), which is often of more interest in practice. Second we want to study important parameters of tree-like structures, which cannot be considered as data structures, but that are used as models in different fields of application (e. g. for describing the spread of epidemics, for modelling the growth of the internet, for pyramide schemes, etc.). In particular the following topics will be considered: Priority queues: are important for many scheduling problems for jobs, events etc. Typical applications are given in operation systems (scheduling the execution of different jobs, resource management, etc.) and in discrete event simulation models. Skip lists: are a very flexible data structure and a probabilistic alternative to search trees. Monotonically labelled trees: are a natural generalization of tree models that appear in several applications in computer science (traversal algorithms, syntax trees, evaluation of locic expressions). Increasing tree families: are a quite general model that contain a wide range of important tree structures, which are used as models for the spread of epidemics, for pyramid schemes, for the growth of the internet and as a basis for sorting methods. Tree traversal algorithms, ascendants and descendants of nodes: problems like the analysis of space requirements during a tree traversal and of search costs in data structures are treated here. Generalized Plya-Eggenberger-urn models: have many applications, e. g. they are used for modelling the space requirements of certain data structures, for contagious diseases and for the stemma construction in philology. Further stree statistics: in the literature are appearing various interesting tree parameters for different tree models, where a more detailed analysis might be of relevance.