<p>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.</p>

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

<p>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!</p>

<p>Thanks</p>

CC BY-SA 3.0
2014-01-10T23:02:36.747Z
What kind of stats are you looking for? They aren't that hard to enumerate for n < 13.
Chad Brewbaker
CC BY-SA 3.0
2014-01-11T12:01:27.953Z
@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?
Bapi Chatterjee
CC BY-SA 3.0
2014-01-13T16:30:21.103Z
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 http://oeis.org/A000680 , my code https://gist.github.com/chadbrewbaker/8403241
Chad Brewbaker
<ds.algorithms><ds.data-structures><randomized-algorithms><average-case-complexity>
Height of randomly built binary search tree by insert and delete?
Bapi Chatterjee
# Height of randomly built binary search tree by insert and delete?

(Asked by: username_0 on 2014-01-10)

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!

Thanks

**Tags:** ds.algorithms, ds.data-structures, randomized-algorithms, average-case-complexity

> **Comments:**
> **username_1**: What kind of stats are you looking for? They aren't that hard to enumerate for n < 13.  
> **username_0**: @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?  
> **username_1**: 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 http://oeis.org/A000680 , my code https://gist.github.com/chadbrewbaker/8403241  

---

## 0 answers

