|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
18 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Extreme Value Statistics and Traveling Fronts: An Application to Computer Science | | Satya N. Majumdar
; P.L. Krapivsky
; | | Date: |
18 Sep 2001 | | Journal: | Phys. Rev. E 65, 036127 (2002) | | Subject: | Statistical Mechanics; Disordered Systems and Neural Networks; Data Structures and Algorithms | cond-mat.stat-mech cond-mat.dis-nn cs.DS | | Abstract: | 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. | | Source: | arXiv, cond-mat/0109313 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER