Physics – Condensed Matter – Statistical Mechanics
Scientific paper
2001-09-18
Phys. Rev. E 65, 036127 (2002)
Physics
Condensed Matter
Statistical Mechanics
16 pages, two-column revtex
Scientific paper
10.1103/PhysRevE.65.036127
We study the statistics of height and balanced height in the binary search tree problem in computer science. The search tree problem is first mapped to a fragmentation problem which is then further mapped to a modified directed polymer problem on a Cayley tree. We employ the techniques of traveling fronts to solve the polymer problem and translate back to derive exact asymptotic properties in the original search tree problem. The second mapping allows us not only to re-derive the already known results for random binary trees but to obtain new exact results for search trees where the entries arrive according to an arbitrary distribution, not necessarily randomly. Besides it allows us to derive the asymptotic shape of the full probability distribution of height and not just its moments. Our results are then generalized to $m$-ary search trees with arbitrary distribution. An attempt has been made to make the article accessible to both physicists and computer scientists.
Krapivsky Paul. L.
Majumdar Satya N.
No associations
LandOfFree
Extreme Value Statistics and Traveling Fronts: An Application to Computer Science 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 Extreme Value Statistics and Traveling Fronts: An Application to Computer Science, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extreme Value Statistics and Traveling Fronts: An Application to Computer Science will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-424793