SU Chun, MIAO Baiqi, FENG Qunqiang. On the Subtrees of Random Binary Search Trees[J]. Chinese Journal of Applied Probability and Statistics, 2006, 22(3): 304-310.
Citation:
SU Chun, MIAO Baiqi, FENG Qunqiang. On the Subtrees of Random Binary Search Trees[J]. Chinese Journal of Applied Probability and Statistics, 2006, 22(3): 304-310.
SU Chun, MIAO Baiqi, FENG Qunqiang. On the Subtrees of Random Binary Search Trees[J]. Chinese Journal of Applied Probability and Statistics, 2006, 22(3): 304-310.
Citation:
SU Chun, MIAO Baiqi, FENG Qunqiang. On the Subtrees of Random Binary Search Trees[J]. Chinese Journal of Applied Probability and Statistics, 2006, 22(3): 304-310.
The subtrees of various sizes and patterns in random binary search trees are investigated in this paper. The expectations and variances of their numbers are first derived from an essential recursive distributional equation. Applying the contraction method, we show both of their asymptotic distributions are normal.
DownLoad: