在CLRS中要求混淆的是随机建立的二叉搜索树证明

Theorem 12.4
The expected height of a randomly built binary search tree on n distinct keys is O(lgn).

\'Xn\' is the height of a randomly built binary search on n keys.
\'Yn\' is the \"exponential height\", where Yn = 2^(Xn)
\'Rn\' is the position that the root key would occupy if the key\'s were sorted, its rank.

Zn,1 Zn,2 Zn,3 ... Zn,n

\'Zn,i = I{Rn = i}\'

We claim that the indicator random variable Zn,i = I{Rn = i} is independent of the
values of Yi-1 and Yn-i. Having chosen Rn = i, the left subtree (whose exponential
height is Yi-1) is randomly built on the i-1 keys whose ranks are less than i. This
subtree is just like any other randomly built binary search tree on i-1 keys.
Other than the number of keys it contains, this subtree\'s structure is not affected
at all by the choice of Rn = i, and hence the random variables Yi-1 and Zn,i are
independent.