摘要
We consider three random variables X_n, Y_n and Z_n, which represent the numbers of the nodes with 0, 1, and 2 children, in the binary search trees of size n. The expectation and variance of the three above random variables are got, and it is also shown that X_n, Y_n and Z_n are all asymptotically normal as n→∞by applying the contraction method.
We consider three random variables X n , Y n and Z n , which represent the numbers of the nodes with 0, 1, and 2 children, in the binary search trees of size n. The expectation and variance of the three above random variables are got, and it is also shown that X n , Y n and Z n are all asymptotically normal as n → ∞ by applying the contraction method.
基金
This work was supported by the National Natural Science Foundation of China (Grant No. 10671188)
the Knowledge Innovation Program of the Chinese Academy of Sciences (Grant No. KJCX3-SYW-S02)
the Special Foundation of University of Science and Technology of China
