Majumdar Satya N, Krapivsky P L
Laboratoire de Physique Quantique, UMR C5626 du CNRS, Université Paul Sabatier, 31062 Toulouse Cedex, France.
Phys Rev E Stat Nonlin Soft Matter Phys. 2002 Mar;65(3 Pt 2A):036127. doi: 10.1103/PhysRevE.65.036127. Epub 2002 Feb 27.
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 that 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 again derive the already known results for random binary trees but to obtain 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.
我们研究计算机科学中二叉搜索树问题里高度和平衡高度的统计特性。搜索树问题首先被映射为一个碎片化问题，接着该碎片化问题又进一步被映射到凯莱树上的一个修正有向聚合物问题。我们运用行波前沿技术来求解聚合物问题，并通过反向转换来推导原始搜索树问题中的精确渐近性质。第二次映射不仅能让我们再次推导出随机二叉树的已知结果，还能得到条目依据任意分布（不一定是随机分布）到达的搜索树的精确结果。此外，它使我们能够推导出高度的全概率分布的渐近形状，而不仅仅是其矩。然后我们将结果推广到具有任意分布的m叉搜索树。
