Average depth of a Binary Search Tree and AVL Tree

Problem Detail: 

My professor recently mentioned that the average depth of the nodes in a binary search tree will be $O(log(n))$ where $n$ is the amount of nodes in the tree. I ended up drawing out a bunch of binary search trees and I don't think I am understanding the concept correctly. For example, if $n=4$ the tree is either going to have a node with a maximum depth of $3$ or node(s) with a maximum depth of $2$. In the case of where the maximum is $3$, then we would have nodes of $0$, $1$, $2$, and $3$ depths. This would give us an average depth of $1.5$ and $log(4)$ is $2$.

My professor also said that an AVL tree's nodes will ALWAYS have an average depth of $O(log(n))$, which makes even less sense to me, since with the example above of $n=4$ the closest we got to $log(4)$ was $1.5$ with a tree that had nodes of depth $0$, $1$, $2$, $3$ but in an AVL tree we couldn't have that tree.

The $O(log(n))$ stuff would kind of make sense if the root started with a depth of $1$, but I specifically asked the professor if that was the case and he said no.

Asked By : Nickknack

Answered By : Hendrik Jan

True, the height any fixed tree can range from logaritmic to linear (in terms of the number of nodes). The avarage depth of the nodes ranges correspondingly. So, trees can range from good (logaritmic) to bad (linear). The statement your professor seems to make is that the avarage binary search tree (BST) is in fact good. Or alternatively that by far most trees are good. Note that AVL-trees are designed to be good by their balanced construction.

How can we make this precise? A "random" BST with $n$ nodes is generated by taking a permutation $a_1,a_2,\dots,a_n$ of $1,\dots,n$ and adding the numbers in that order to the bst. Of course $a_1$ will be in the root. A measure for the total depth of all nodes in the tree is called internal path length (counting steps from root to all nodes). Now there is a nice "recursive" way of looking at internal path length. All numbers smaller than $a_1$ will end up in the left subtree, those larger than $a_1$ in the right subtree. So we can look at the smaller and larger numbers separately and consider the subtrees.

This forms the basis for a computation of the average internal path length over the $n!$ different permutations. (Actually, there are less trees than that: some permutations will give the same tree. That is only natural, as it is the way BST's are built.) This computation then shows the average internal path length to be in the order of $n \lg n$, so the avarage depth of a node in the avarage BST is order $\lg n$.

At least two books on Data Structures and Algorithm Analysis that I know have that derivation, by Weiss and Drozdek respectively. It also is in the TAoCP books by Knuth.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47292