Give an asymptotic upper bound on the height of an n-node binary search tree in which the average depth of a node is Θ(lg n)

Question

Recently, I'm trying to solve all the exercises in CLRS. but there are some of them i can't figure out. Here is one of them, from CLRS exercise 12.4-2:

Describe a binary search tree on n nodes such that the average depth of a node in the tree is Θ(lg n) but the height of the tree is ω(lg n). Give an asymptotic upper bound on the height of an n-node binary search tree in which the average depth of a node is Θ(lg n).

Can anyone share some ideas or references to solve this problem? Thanks.

Answer 1

So let's suppose that we build the tree this way: given n nodes, take f(n) nodes and set them aside. Then build a tree by building a perfect binary tree where the root has a left subtree that's a perfect binary tree of n - f(n) - 1 nodes and a right subtree that's a chain of length f(n). We'll pick f(n) later.

So what's the average depth in the tree? Since we just want an asymptotic bound, let's pick n such that n - f(n) - 1 is one less than a perfect power of two, say, 2^k - 1. In that case, the sum of the heights in this part of the tree is 1*2 + 2*3 + 4*4 + 8*5 + ... + 2^(k-1) * k, which is (IIRC) about k 2^k, which is just about (n - f(n)) log (n - f(n)) by our choice of k. In the other part of the tree, the total depth is about f(n)^2. This means that the average path length is about ((n - f(n))log (n - f(n)) + f(n)^2) / n. Also, the height of the tree is f(n). So we want to maximize f(n) while keeping the average depth O(log n).

To do this, we need to find f(n) such that

1. n - f(n) = Θ(n), or the log term in the numerator disappears and the height isn't logarithmic,
2. f(n)^2 / n = O(log n), or the second term in the numerator gets too big.

If you pick f(n) = Θ(sqrt(n log n)), I think that 1 and 2 are satisfied maximally. So I'd wager (though I could be totally wrong about this) that this is as good as you can get. You get a tree of height Θ(sqrt(n log n)) that has average depth Θ(Log n).

Hope this helps! If my math is way off, please let me know. It's late now and I haven't done my usual double-checking. :-)