New answers tagged binary-search-trees
1
According to Lemma 7.1 in these notes, if you construct a random BST on $\{0,\ldots,n-1\}$, then the expected depth of $x \in \{0,\ldots,n-1\}$ is $H_{x+1} + H_{n-x} - 2$, where $H_m$ is the $m$'th harmonic number. Summing over all $x$, the expected sum of depths is
$$
\sum_{x=0}^{n-1} (H_{x+1} + H_{n-x} - 2) =
2 \sum_{i=1}^n (H_i - 1) = 2 \sum_{i=1}^n \sum_{...
0
You can update the ancestors. The Wikipedia article explains the running time to do so.
If you've done a rotation, you might need to update all nodes that participated in the rotation and all of their ancestors.
Top 50 recent answers are included