patternMinor
Average depth of a Binary Search Tree and AVL Tree
Viewed 0 times
depthsearchaverageavlbinaryandtree
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#47292, answer score: 3
Revisions (0)
No revisions yet.