Dependencies between Shape Parameters in Random Log-Trees
Michael Fuchs 教授交大應數系 下午 3:00–4:00 鴻經館 107 室Abstract:
Random log-trees are trees with an average height of logarithmic order. They are of key importance, e.g., in computer science since many algorithms and data structures exhibit a log-tree behavior. Performance measures of these algorithms and data structures correspond to parameters of log-trees describing their shape. These so-called shape parameters have been extensively studied for many families of log-trees. One of them are $m$-ary search trees for which, e.g., the limit law of the size has been proved to exhibit a phase change from normal ($m\leq 26$) to non-existence ($m>26$).
On the other hand, the limit law of the total path length does not undergo a phase change. In this talk, we consider the correlation between, e.g., the size and total path length which exhibits some surprises and further phase changes. Correlation between other shape parameters and other random log-trees will be also discussed. This talk is based on recent joint work with H.-H. Chern (National Taiwan Ocean University), H.-K. Hwang (Academia Sinica) and R. Neininger (Goethe University).