2
$\begingroup$

I was studying AVL trees and was wondering if the only reason one propagates upwards to the node in an insert is to change the height. It seems to me that rebalancing does not recursively propagate back with only inserts but one might have to go back to change heights (since only nodes on the path from insertion point to root node have possibly changed in height, so we need to make sure we update them).

However, I was trying to form some type of proof that we don't actually recurse to the root and actually perform rebalancing. The proof I sort of had was the following:

The only way to recurse back to fix a unbalanced node is if we have two violations due to an insertion. One at some point down the tree and another one higher up the tree. When we do an insert the node increased height which caused these two unbalances. For us to have to recurse back we need to make sure even after the rebalancing of the lowest node, that the height doesn't decrease due to the rebalancing. This is unfortunately unavoidable because for that to happen, we'd need to be in one of the cases of rebalancing where the node's height doesn't change. Since the height of a node always decreases in an insert, then we don't actually need to rebalance.

Why don't we need to rebalance? That is because the only time we need to rebalance and the height doesn't change is when the right child of the lowest violating node $x$ has two subtrees that are balanced. That is not possible to happen because for that to happen, you need two inserts to cause that unbalance, but a single insert would cause the imbalance already, so the second insert won't make the right child of $x$ have two balanced subtrees.

$\endgroup$
  • $\begingroup$ Please cite the source you are referring to resp. learning from. $\endgroup$ – Raphael Feb 24 '16 at 9:38
2
$\begingroup$

You may have to rebalance during insertions, that much is clear: inserting a sorted sequence of values would otherwise lead to a degenerate tree.

By looking at the setup graphics of the four types of rotation, you can easily see that the height of the affected subtree after the insertion is the same as before. Thus, no node outside of this subtree can be imbalanced.

Thus, we never need more than one rotation when inserting. We can stop moving up the tree after we've rotated once, and efficient (non-recursive) implementations do exactly that.

$\endgroup$
  • $\begingroup$ So it takes O(logn) to insert due to the usual BST insertion AND also to update the heights as we go back? Im just confused if we need to recurse back and update the heights or if we only do that once after the insertion. $\endgroup$ – Charlie Parker Feb 24 '16 at 21:54
  • $\begingroup$ $\Theta(\log n)$ has nothing to do with this -- you need this much time to find the insertion position, anyway. You have to update balance values after every insertion, yes. (Why wouldn't you?) $\endgroup$ – Raphael Feb 25 '16 at 13:14
  • $\begingroup$ If after an insertion it causes the tree to break the AVL invariant at some lowest violating node x, then after fixing the height then the height decreases by one due to the fix (or returns to what it was before). Thus, it seems to me that one shouldn't actually increase the heights in the path along the insertion because the rebalancing would decrease the height of the lowest violating node anyway. So it seems to be that during insertion one doesn't have to propagate back and decrease the heights of the nodes in the path of the insertion, unless they were increased during the actual insertion $\endgroup$ – Charlie Parker Feb 25 '16 at 19:48
0
$\begingroup$

When you rebalance on an insert the resulting node height is equal to what it was before the insert so you don't need to propagate to the root to change node height after a single or double rotation, after the rotation rebalancing is complete and node heights are already correct further up because they didn't change.
Often recursive insert implementations just keep going to the root because they don't maintain a way to signal the rebalancing is complete. Non-recursive bottom-up AVL tree rebalancing will always break out of the loop and return after a single or double rotation.

$\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.