166
правок
Изменения
→Высота декартового дерева
|about=о математическом ожидании глубины узла
|statement=Математическое ожидание глубины <tex>k</tex>-го узла равно <tex>H_k + H_{n-k+1} - 1</tex>, где <tex>H_j = \sum\limits_{i=1}^j\frac{1}{i} \approx \ln j</tex>.
|proof=Глубина <tex>k</tex>-го узла - это количество узлов, которые являются прародителями этого узла. Введем случайную величину <tex>A_i</tex>, равную единице, если <tex>i</tex>-й узел является прародителем <tex>k</tex>-го узла, и нулю в противном случае. Легко проверить, что <tex>A_i</tex> и <tex>A_j</tex> независимы при <tex>i \ne j</tex>. Из того, что <tex>y_i</tex> выбраны случайно и независимо с одинаковым распределением и предыдущей леммы следует, что <tex>M(A_i) = \frac{1}{|i - k| + 1}</tex> при <tex>i \ne k</tex>:.
:<tex>M(depth_k)=M(\sum\limits_{i=1}^nA_i)=\sum\limits_{i=1}^nM(A_i)=\sum\limits_{i=1}^n\frac{1}{|i-k|+1}=</tex>
:<tex>=\sum\limits_{i=1}^k\frac{1}{k-i+1}+\sum\limits_{i=k}^n\frac{1}{i-k+1}-1=H_k+H_{n-k+1}-1</tex>.}}
