Understanding Search Trees via Statistical Physics

Details Understanding Search Trees via Statistical Physics Understanding Search Trees via Statistical Physics

2004-10-20

arxiv.org/abs/cond-mat/0410498v1

Physics

Condensed Matter

Statistical Mechanics

11 pages, 8 .eps figures included. Invited contribution to STATPHYS-22 held at Bangalore (India) in July 2004. To appear in th

Scientific paper

10.1007/BF02704178

We study the random m-ary search tree model (where m stands for the number of branches of a 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 traveling front structure. In addition, the variance of the number of nodes needed to store a data string of a given size N is shown to undergo a striking phase transition at a critical value of the branching ratio m_c=26. We identify the mechanism of this phase transition, show 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= \pi/\sin^{-1}(1/\sqrt{8})=8.69363...

Affiliated with

Also associated with

No associations

Rating

Understanding Search Trees via Statistical Physics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Understanding Search Trees via Statistical Physics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Understanding Search Trees via Statistical Physics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-536601