What is the average asymptotic depth of a simple unbalanced search tree?

3
votes

For a balanced search tree, it is O(log(N)) for all cases. For unbalanced search trees, the worst case is O(N), e.g., insert 1, 2, 3, 4,.. and best case complexity is when it is balanced, e.g., insert 6, 4, 8, 3, 5 7. How do we define the average case complexity for unbalanced search tree?

1
mathbinary-treedepth
I'd expect about O(n^.5) due to similarity to random walks, but I'm not posting an answer as I can't quite prove this. BTW, if this is homework, could you tag it as such? – pavpanchekha
this is not homework. this is out of curiosity as most search trees in standard libraries in C++, Java are implemented as unbalanced. – user236215
This is too tough to be homework. – Aryabhatta
It is not true that search trees in C++ and Java's libraries are unbalanced. Both use red-black trees. – jkff
"Unbalanced search tree" is a large category. Some math appears to be solving avg/max depth for "a random tree picked from the set of all possible trees with N nodes", and some solve for "a tree generated by inserting N nodes in random locations", and the two appear to have vastly different results :( – Mooing Duck

1 Answers

4
votes

The average height of Binary Trees is Theta(sqrt(n)). This has been shown (or referenced, not very sure) in the following paper: http://www.dtc.umn.edu/~odlyzko/doc/arch/extreme.heights.pdf.

But perhaps you are more interested in the average depth of a random node and this is Theta(log n), as can be seen here: http://www.toves.org/books/data/ch05-trees/index.html (Section 5.2.4).