Average depth of a Binary Search Tree and AVL Tree

Question

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.

Answer 1

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.

Answer 2

Your question refers to average depth of the nodes in a BST, but it's easiest answer this by thinking about the overall height of the tree first. In the worst case, the depth of the tree can be $n$, assuming it's not a balanced tree and the inputs are sorted, so the resultant tree ends up being a very deep linked list. In that case, the average depth of nodes in the tree can be $\frac{n}{2}$. But assuming the tree is balanced, or the input is randomized, the expected depth will be $O(\log n)$ because the number of nodes present at each depth in the tree grows exponentially with the depth of the tree. ($2^0$ nodes at depth 0, and $2^1$ nodes at depth 1, etc). This is of course, subject to the constraint that the count of all nodes is equal to $n$, so the height of the tree will be $O(\log n)$.

The average depth of all the nodes in the tree will of course grow as the depth of the tree increases, and since the number of nodes present at a particular depth increases exponentially with the depth, the larger the tree is, the denser the deeper layers of the tree will be, and the more the deeper layers will dominate the average. So the average depth of nodes in the tree will approach the height of the tree, which we know to be $O(\log n)$. So the average depth of nodes in the tree is also $O(\log n)$.

Your professor mentioned that AVL trees will always have an average depth of $O(\log n)$. This is because AVL trees are balanced, so everything mentioned above always applies to AVL trees. They cannot end up being linear.

This is just an intuitive argument, not a proof. If you need a proof, see CLRS (Cormen Leiserson Rivest Stein) Introduction to Algorithms Third Edition pg 300. They have 3 pages of algebra as a proof.

Answer 3

These are balanced trees. That means, the algorithm for adding / removing elements from it provides that the difference of the depth of the subtrees remains below a (low) limit.

These trees are also recursive structures: the left and right child is of an AVL tree is also an AVL tree for which this property also consists. And so on.

This $O(log(n))$ is an asymptotic value, which means, while $n$ grows to infinity, the depth of an AVL tree will grow with $log(n)$. (More exactly, for AVL trees a $depth < 1.44log(n)$ is guaranteed, it has a very beautiful proof, I suggest, don't miss it). For small $n$s it is possible some relatively larger deviation.

The BSTs aren't balanced for every inputs, it is easy to construct such an insertion ordering which degenerates them (the most simple if you add numbers linearly - essentially, you will get a list). But they will be nearly balanced if your insertions are quasi-randomly.

In the practical IT it is not a problem, because the explicit goal of these balanced trees is to handle big data structures (i.e. large $n$) fast. This is why is $O()$ used so many times in the Computer Science.