In Introduction to algorithm (CLRS), even in its third edition (published in 2009) it is noted in Sec 12.4 that little is known about height of randomly built binary search tree using insert and delete.

In a discussion (Oct 12. Can it be said old?) in stack ex here https://cs.stackexchange.com/questions/6342/proof-that-a-randomly-built-binary-search-tree-has-logarithmic-height as well the explanation of CLRS method has been discussed.

Is there some work in last one year or so? Much appreciate if a reference could be found of some recent publication noting the above i.e. there is no progress as yet!


  • $\begingroup$ What kind of stats are you looking for? They aren't that hard to enumerate for n < 13. $\endgroup$ – Chad Brewbaker Jan 10 '14 at 23:02
  • $\begingroup$ @ChadBrewbaker I can cite CLRS for - "The expected height of a randomly built binary search tree by inserts is O(logn)". Can I have some reference work which has some discussion about the height of randomly built binary search tree by inserts and delete? $\endgroup$ – Bapi Chatterjee Jan 11 '14 at 12:01
  • $\begingroup$ What is the expected delete distribution? 50% ? Inserts alone are easy to model with building trees from permutations of the numbers 1..n. Del(i) has to come after Insert(i) [Ins(1),Ins(3),Ins(5),Del(3),Del(4),Ins(2),Del(1)] is what it would look like. I would model it as $S$, shuffle/interleaving of two permutations $Ins$ and $Del$ (1..n), where the insert has to happen before the corresponding delete. Looks like the combinatorial object is oeis.org/A000680 , my code gist.github.com/chadbrewbaker/8403241 $\endgroup$ – Chad Brewbaker Jan 13 '14 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.