A note on growing binary trees |
| |
| Authors: | Alan G Konheim Donald J Newman |
| |
| Institution: | IBM, Thomas J. Watson Research Center, Yorktown Heights, N.Y. 10598, USA;Yeshiva University, New York, N.Y., USA |
| |
| Abstract: | The class ? of binary search trees is studied. A leaf is a vertex of degree 0; ?n is the subset of ? consisting of trees with n leaves. We grow trees in ?n from ?n ? 1 thereby inducing a probability measure on ?n. We will show that the expected value of the average leaf distance of t ∈ ?n is asymptotic to log2n as n → ∞. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
