Can this binary tree be balanced?

1
votes

I had tried to implement the codes to implement the way (brute force) to balance the binary search tree, and I found that there is a case (of the tree) and it seems that it cannot be balanced. The tree is

         6
          \
           10
          /
         8
        / \
       7   9

You can obviously find that the right height of this tree is much greater than its left height, so I rotate left the tree around '6', then the new tree will be

       10
      /
     6
      \
       8
      / \
     7   9

Then it becomes that the left height is much greater than its right height, so in the next step I have to rotate right (back to) the tree around node '10'.

It seems that there must be an infinite loop to rotate this tree around its root node (rotate left, right, left, right...and so on) while balancing this tree. Is there a solution to balancing this tree?

2
binary-tree
Check out the max heap or min heap. That might help you learn how to create a balanced binary tree. – Denis

2 Answers

2
votes

You should not rotate around the root first, you should instead rotate the right subtree first as it is also unbalanced.

This

       10
      /
     8
    / \
   7   9

should be rotated and converted to 

     8
    / \
   7   10
      /
     9

Then the tree will be

   6
    \
     8
    / \
   7   10
      /
     9

And then you rotate around root

    8
   / \
  6   10
   \   /
    7 9
1
votes

The simplest algorithm for doing this is:

  1. take 3 consecutive nodes in this tree (in your case 6, 8, 10)
  2. order those nodes
  3. attach the original sub-trees in order: empty, 7, 9, empty

That would yield:

     8
   /   \
  6     10
 / \   /  \
.   7 9    .

This tree is pretty well balanced.