1

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?

Improve this question
1
  • Check out the max heap or min heap. That might help you learn how to create a balanced binary tree. Commented Jun 16, 2017 at 7:20

2 Answers 2

Reset to default
2

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
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Thank you so greatly!!! I found that I am so awkward!! It is a great explanation!
Sorry Jerry, I faced another binary search tree, 1 -> 3 -> 2, I tried to balance this tree (it is a subtree actually), but it was stuck at a loop. Is it possible to balance that binary search tree?
@DavidHsu, that is one case where you need to rotate 3->2 first and then put 2 to the root (double rotation). I suggest you read some textbook for some standard implementation of self balanced binary search tree. One common implementation is AVL tree and you may refer to the wikipage here en.wikipedia.org/wiki/AVL_tree. The double rotation case is exactly what you met here.
thank you so greatly, I will read more about the AVL tree from the books or websites.
1

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.

Improve this answer

1 Comment

Thank you so greatly!!! I found that I am so awkward!! It is a great explanation!

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.