Understanding search trees via statistical physics |
| |
Authors: | Satya N Majumdar David S Dean P L Krapivsky |
| |
Institution: | (1) Laboratoire de Physique Théorique et Modéles Statistiques, Université Paris-Sud, Bat 100, 91405 Orsay Cedex, France;(2) Laboratoire de Physique Theorique (UMR C5152 du CNRS), Université Paul Sabatier, 31062 Toulouse Cedex, France;(3) Center for Polymer Studies and Department of Physics, Boston University, 02215 Boston, Massachusetts, USA |
| |
Abstract: | We study the randomm-ary search tree model (wherem stands for the number of branches of the search tree), an important problem for data storage in computer science, using a
variety of statistical physics techniques that allow us to obtain exact asymptotic results. In particular, we show that the
probability distributions of extreme observables associated with a random search tree such as the height and the balanced
height of a tree have a travelling front structure. In addition, the variance of the number of nodes needed to store a data
string of a given sizeN is shown to undergo a striking phase transition at a critical value of the branching ratiom
c
= 26. We identified the mechanism of this phase transition and showed that it is generic and occurs in various other problems
as well. New results are obtained when each element of the data string is a D-dimensional vector. We show that this problem
also has a phase transition at a critical dimension,D
c
= π/ sin-1 (l/√8) = 8.69363 … |
| |
Keywords: | Search trees fragmentation travelling fronts phase transition |
本文献已被 SpringerLink 等数据库收录! |
|