New answers tagged


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_{...


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