最广为人知的生成随机树的算法是对于每个节点随机选择其父亲。
形式地说：
- 一个点的随机树只有一个形态；
- 生成 \(n+1\) 个点的随机树时，先照此办法生成一个 \(n\) 个节点的随机树，然后从 \(n\) 个节点中均匀随机地选择一个节点作为第 \(n+1\) 个节点的父亲。
我们证明，这样生成的树的期望高度是 \(\Theta(\log n)\) 的。
设 \(f_i\) 表示第 \(i\) 个点的期望高度，显然有递推：
- \(f_1=0\)；
- \(f_{n+1}=\dfrac{\sum_{i=1}^nf_i}{n}+1\)
记 \(S_n=\sum_{i=1}^nf_i\)，考虑 \(S_n\) 的增长速度，显然有
\[S_{n+1}-S_n=\dfrac{S_n}{n}+1 \]即
\[S_{n+1}=\dfrac{n+1}{n}S_n+1 \]注意到
\[S_n=n\left(\sum_{i=2}^n\dfrac{1}{i}\right) \]归纳易证。
显然 \(S_n=\Theta(n\log n)\)，那么 \(f_n=\Theta(\log n)\)。
标签：log,dfrac,生成,随机,一棵,Theta,节点 From： https://www.cnblogs.com/weily09/p/18411615