随机二叉搜索树的子树

On the Subtrees of Random Binary Search Trees

摘要: 本文讨论随机二叉搜索树上不同大小的子树和与给定某个二叉树同构的子树. 利用递归分布等式,　我们得出了它们各自数目的期望和方差\bd 最后, 用压缩法得出了它们的中心极限定理.

Abstract: 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.