title: analysis of binary search tree
body: <p>In binary search trees most of the operations' average computational complexity is given as O(NlogN). Below is a text snippet from Algo's book:</p>
  
  <blockquote>
    <p>Average of internal path length is D(n) = O(n log n).  Thus, the expected depth of
    any node is O(log n). As an example, the randomly generated 500-node
    tree  has nodes at expected depth 9.98.</p>
    
    <p>It is tempting to say immediately that this result implies that the
    average running time of all the operations  discussed i.e., insert,
    find min, find max, delete on binary search tree is O(log n), but this
    is not entirely true. The reason for this is that because of
    deletions, it is not clear that all binary search trees are equally
    likely. In particular, the deletion algorithm described above favors
    making the left subtrees deeper than the right, because we are always
    replacing a deleted node with a node from the right subtree. The exact
    effect of this strategy is still unknown, but it seems only to be a
    theoretical novelty. It has been shown that if we alternate insertions
    and deletions O(n2) (i.e., theta of n square) times, then the trees
    will have an expected depth of theta of square root N. </p>
    
    <p>After a quarter-million random insert/delete pairs, the tree that was
    somewhat right-heavy looks decidedly unbalanced  (average depth =
    12.51).</p>
  </blockquote>
  
  <p>My questions on above text snippet are:</p>
  
  <ol>
  <li>What does the author mean by "because of deletions, it is not clear that all binary search trees are equally likely"?</li>
  <li>How did the author achieved expected depth of 9.98 for 500 node tree, as log 500 is not 9.98?</li>
  <li>In last paragraph, how did he get average depth of 12.51?</li>
  </ol>
  
  <p>Thanks!</p>