0
$\begingroup$

I was listening to Eric Demaine's video lecture on AVL trees and there was a claim that comes up that keeping a trit on each node (to indicate whether the node is left heavy, right heavy or balanced) should be sufficient for all AVL tree operations, so essentially we don't need to keep heights of the node for every node. Can anyone prove to me why that would be the case?

$\endgroup$
  • $\begingroup$ Most of us should be able to, and about every DS text introducing AVL-trees should give it (consult yours(?)). If I don't get it wrong, it is not a property of the node such attributed, any or both of its sub-trees or the tree rooted at the node in question: it is about the way balancing should be done. $\endgroup$ – greybeard Jul 9 '15 at 18:44
1
$\begingroup$

In an AVL tree we aim to make the binary tree height balanced. Say the left subtree of a node has a height of $m$ and the right subtree has a height of $n$. The node therefore has a balance of $b=m-n$. We rotate the tree to restore it's balance if the balance of any node, $|b|>1$.

So the value of $b$ is either $-1,0, or 1$. Hence storing the balance of each node in a trit becomes much easier than say storing the height of each node, because all we need to do is check the balance.

Also storing the height of the subtree of each node would be a problem. You could not understand if your node is either left-heavy or right-heavy or balanced because all you have is the height of the lowest level leaf. So storing the height of each node will not serve any purpose and seems to be counterproductive.

$\endgroup$
2
$\begingroup$

The core argument is that the balance can never change by more than one when inserting or deleting a single key; of course, since heights can only change by at most one.

That way, knowing the old balance (which is in $\{-1,0,1\}$) and if (and how) subtree heights changed is enough to know the new balance (which is in $\{-2,1,0,1,2\}$). If the balance is $-2$ or $2$ we rotate, of course, and restore balance (in that node).

In order to prove this, simply write out all possible cases of old balances and changes due to insertion or deletion.

$\endgroup$

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.