5
$\begingroup$

Given an AVL tree, I want to compute its height as efficiently as possible. $\newcommand{\bf}{\text{bf}}\newcommand{\height}{\text{height}}$

Each node of an AVL tree stores its balance factor ($\bf$), defined as

$$\bf(v)=\height(v.\text{left}) - \height(v.\text{right}).$$

We can recursively compute the height of an AVL tree in $O(\log n)$ time, using the following recursive procedure:

Height($v$):
1. If $v$ is a leaf node, return 0.
2. If $\bf(v)=+1$, return Height($v.\text{left}$).
3. If $\bf(v)=-1$, return Height($v.\text{right}$).
4. If $\bf(v)=0$, return Height($v.\text{left}$). (returning Height($v.\text{right}$) would work too)

This recursive algorithm works, because the balance factor tells us which is taller, the left subtree or the right subtree, and the algorithm always recurses into the taller subtree.

My question is: Is there a faster algorithm? Can we do better than $O(\log n)$ time? Assume we can't augment the tree to store extra information in it; we are restricted to only the information that is already normally stored in an AVL tree.

$\endgroup$
  • $\begingroup$ Without storing the height somewhere, I don't think $o(\log n)$ is possible. $\endgroup$ – Raphael Jan 8 '16 at 11:46
  • $\begingroup$ Effectively, inspecting the non-smaller subtree at each level allows to find the height. So does visiting each and every node, if with efficiency $\omega(log n)$: strictly larger/slower/less efficient than $log n$ for n tending to infinity. With no information in the nodes about the subtree as a whole (in addition to balance), here's another one thinking small-o(log $n$) impossible. (A descendant at half height would be fun such info.) This being the second comment to that effect, constructing a proof by contradiction seems to be less easy than with many questions triggering "of course not". $\endgroup$ – greybeard Feb 7 '16 at 13:25
3
$\begingroup$

There is a $\Omega(\lg \lg n)$ lower bound: you can't hope for an algorithm that is faster than $O(\lg \lg n)$ time.

Let the height of the tree be $H$. AVL trees are balanced, so as a result the height is $H=\Theta(\lg n)$.

Suppose we solve the height problem by visiting the nodes in a longest path, one by one. The longest path has length $H$, so this approach will take $\Theta(H) = \Theta(\lg n)$ time.

Alternatively, suppose (just suppose) that we actually stored the height on a node at all times. Then we could get the height in $O(1)$ time easily. Of course, AVL trees don't actually store the height in each node, so we can't actually do that in this case.

Nonethelesss, this suggests we can model the problem as a communication problem. During tree manipulation, each node has some information to communicate to the algorithm, but the channel is limited to just $1.6$ bits per node (and you cannot choose that bit, it has to be the balance factor). Why $1.6$ bits? Because there are only three possible values for the balance factor, $-1$, $0$, or $+1$, and $\lg 3 \approx 1.6$.

We'd like this channel to communicate the integer $H$. Obviously, this will require at least $\lg H$ bits. Since each node carries only $1.6$ bits of information, that means that we're going to need to visit at least $(\lg H)/1.6 = \Omega(\lg H) = \Omega(\lg \lg n)$ nodes. Therefore, the optimal algorithm cannot possibly be faster than $\Omega(\lg \lg n)$ time.

In particular, there is no hope for an $O(1)$-time algorithm, assuming you are using an unaugmented AVL tree.

$\endgroup$
3
$\begingroup$

No. There's a $\Omega(\lg n)$ lower bound. You can't do better than $O(\lg n)$ time. In fact, any algorithm has to visit at least $H-1$ nodes, where $H$ is the height of the tree.

Let $T_1$ be a tree of height $H$, where the balance factor at every node at all but the bottom two levels is 0. In other words, it is a perfect binary tree of height $H$, except that some subset of the leaves are missing; at the level above the leaves, all nodes have balance factor $+1$, $0$, or $-1$; and at all levels above that, the balance factor is $0$.

Let $T_2$ be an analogous tree of height $H+1$, i.e., it has height $H+1$ and the balance factor at all but the bottom two levels is 0.

Both $T_1$ and $T_2$ are AVL trees.

Now note that any algorithm has to visit at least $H-1$ nodes to distinguish $T_1$ from $T_2$. Their first $H-2$ levels look identical (every node has two children and has balance factor 0), so you can't tell them apart until you have visited at least $H-1$ nodes. To count as a correct algorithm for this problem, the algorithm has to produce the right answer on both $T_1$ and on $T_2$.

Consequently, any algorithm has to have worst-case running time at least $H-1$, i.e., $\Omega(H)$.

$\endgroup$
-1
$\begingroup$

For every node in the AVL, we keep the height of the node as well - so that the balance factor can be calculated in constant time. Can you expand the definition for your "height()" function?

$\endgroup$
  • $\begingroup$ we keep the height of the node as well - who we? What did A-V&L present? $\endgroup$ – greybeard Jan 8 '16 at 8:42
  • 1
    $\begingroup$ This answer is incorrect. Standard AVL trees don't store the height in each node; they store only the balance factor (-1, 0, or +1). Also, please don't use answers to request clarification in the question. Once you've participated enough on this site by posting useful answers and/or questions, you'll be able to post a comment requesting clarification; until then, we'd prefer you to focus on answering questions that you find clear enough to answer as is. $\endgroup$ – D.W. Jul 6 '16 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.