1
$\begingroup$

Im learning about tree data structures, and had a question that i couldnt find answer to so I came here.

Usually when we balance a tree, we insert keys and keep checking balance factor, as soon as it exceeds the given limit of (-1,0,1) we immediately balance it and continue to insert keys, if any.

But lets say, I construct a tree, and I dont check balance factor after each key is inserted and I just completely construct the tree first and then I calculate balance factor for each node and attempt to balance the tree.

Q) Is it possible to balance tree using such approach ? If yes, then how?

Q) If no, then why not? What would be the flaws/problems that would arise using such approach ?

$\endgroup$
6
  • $\begingroup$ Hint to first questions, the answer is simple and easy. Do not be surprised if you think that is not a hint at all. More often than not, knowing there is an answer might be enough for you to figure out the correct answer. $\endgroup$
    – John L.
    Mar 28, 2019 at 22:55
  • $\begingroup$ @Apass.Jack I would appreciate it if you care to explain what you wrote. $\endgroup$ Mar 28, 2019 at 23:12
  • $\begingroup$ Hm, my hint was slightly misleading. I should have said, there are several simple and easy answers. Can you see one? I will elaborate shortly. $\endgroup$
    – John L.
    Mar 28, 2019 at 23:24
  • $\begingroup$ @Apass.Jack I tried, I dont get it. Kindly explain, i would appreciate it, please. $\endgroup$ Mar 28, 2019 at 23:28
  • $\begingroup$ "information of last insert" and "balance factor for each node" seems just red herring for this question. $\endgroup$
    – John L.
    Mar 29, 2019 at 1:10

1 Answer 1

1
$\begingroup$

What you are asking is simply how to balance a binary search tree (BST) $T$. By the way, the phrase "un-balanced AVL tree" is somewhat confusing since AVL tree is height balanced by definition.

If there is enough space for a whole new tree, then we can simply construct a new AVL tree from scratch, by removing one element from the $T$ and inserting it to the new tree repeatedly. You may call this cheating. While I would agree with you if I were on your side, I can also argue this is just an alternative simple way of balancing a BST, although slightly revolutionary and possibly heavy. Note that we can improve the performance of this approach by taking advantage of the fact that $T$ is a BST, as shown in the exercise 2 below.

Suppose we do not have that much space. Here is how we can balance $T$ in-place. Count the number of nodes in the left subtree of the root node and the number of nodes in the right subtree of the root. If their difference is greater than one, then let us find $m$, the median node of all nodes when the number of all nodes is odd or one of the two median nodes of all nodes when the number of all nodes is even.

  • Suppose $m$ is the left child of its parent node. Consider $R$, the right subtree of $m$ and $T'$, which is $T$ with the subtree with root $m$ removed. Note that all nodes of $R$ is smaller than all nodes of $T'$. So we can merge $R$ and $T'$ into a new BST $T''$ easily in $O(1)$ operations. Now set the right subtree of $m$ to $T''$ and set $m$ to be the root.
  • Otherwise $m$ is the right child of its parent node. This case is symmetric to the above case.

Now we have obtained a BST tree whose root is a median of all nodes. Repeat the process above on its left subtree and right subtree, as long as the subtree has more than 2 nodes. In the end, we will obtain a BST where the difference of the number of nodes in the left subtree and the number of nodes the right subtree of any node is at most 1. Let us call this kind of BST "optimally-balanced". Intuitively and apparently, you cannot make a BST more balanced than an optimally-balanced BST. It is not hard to prove that an optimally-balanced BST must be an AVL tree.

I might have skipped over a few boundary cases and a few finer points in the above explanation. Hopefully, the above is able to convince you that the answer to "is it possible to balance an already constructed 'un-balanced AVL tree'" is positive once you have taken some time to reflect.


Here are several related exercises that you can think about. $T$ is a given BST with $n$ nodes.

Exercise 1. Show that an optimally-balanced BST must be an AVL tree.

Exercise 2. If there is enough space, convert $T$ to an AVL tree in $O(n)$ time. (Hint, convert $T$ to a sorted array first.)

Exercise 3. With $O(1)$ working space, balance $T$ into an AVL tree in $O(n)$ time. (This might be a difficult exercise.)

$\endgroup$
1
  • $\begingroup$ Thank you for detailed answer.I will look at exercises too, interesting stuff! $\endgroup$ Mar 29, 2019 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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