The Height of Increasing Trees
The Height of Increasing Trees
复制标题
增加树木的高度
DOI：
10.1007/s00026-009-0009-x
复制
发表时间：
2009
影响因子：
0.5
通讯作者：
M. Drmota
中科院分区：
文献类型：
--
作者：
M. Drmota
Bergeron、Flajolet和Saly引进了越来越多的树[1]。这种概念涵盖了几类众所周知的随机树，如二叉树、递归树和面向平面(或堆排序)的树。考虑树的增长高度，证明了几类树(包括上述几类树)的树高满足ehn~γlogn(对于某个常数γ>；0)，且VarHn=(1)为n个树.使用的方法是基于生成函数的。
Increasing trees have been introduced by Bergeron, Flajolet, and Salvy [1]. This kind of notion covers several well-know classes of random trees like binary search trees, recursive trees, and plane oriented (or heap ordered) trees. We consider the height of increasing trees and prove for several classes of trees (including the above mentioned ones) that the height satisfies EHn ~ γlogn (for some constant γ > 0) and VarHn = O(1) as n → ∞. The methods used are based on generating functions.