Insert items into a Binary Search Tree in ascending order

[kwstriker299]

Today in class, my professor posed an interesting question for us to think about before our next class. If you insert items that are in ascending order into a binary search tree, then you will build the worst possible tree since it will have the largest possible height. The question is:

How would you change the tree building process so that the tree is nearly balanced ?

Just something to think about, if anyone has any ideas that would be great!! Thanks in advance!!!

[Ganon11]

What if you tried to keep the height of the subtrees of each node equal?

[kwstriker299]

What if you tried to keep the height of the subtrees of each node equal?

I'm not real sure what you are getting at.....wouldn't the height of each subtree already be 1, since every parent node would have 1 child node on the right side?

[Ganon11]

What is the height of a tree? Isn't it the number of levels (i.e. a perfectly balanced binary tree with 7 nodes has height 3 (level 1 has the root, level 2 has its 2 children, and level 3 has those children's 4 children))? So then, the height of a subtree is 1 + max(height(leftChild), height(rightChild)).

If the two heights were equal or close to equal, that means that subtree is balanced.

[kwstriker299]

yes i understand what you are saying, and that was the question that my professor posed to us.

How would you change the tree building process so that the tree is nearly balnaced?

The one thought that I am having is rotating the nodes after they are inserted, more like an AVL tree would do.

Does any one know of any pseudo-code to implement a rotation? After thinking about it more I think rotation would be the best option, but im not sure what the best way to perform the rotation would be.

[Ganon11]

In the following diagrams, X3 is the node where the tree is unbalanced, and X1 and X2 are other nodes we will be moving around. A, B, C, and D are all subtrees whose structure doesn't change.

             (Some tree...)
            /
           X1
          /  \
        X2    A
       /  \
     X3    B
    /  \
   D    C

would become...

             (Some tree...)
            /
          X2
         /  \
       X3     X1
      /  \   /  \
     D    C B    A

in one type of rotation.

There are 3 other types - try writing down diagrams and figuring out where each node/subtree would go.

[kwstriker299]

Yes I know how to make all of the necessary rotations on paper like you suggested. But lets say we wanted to implent it. How would we do that?

Would this work?

Insert item
Check height to see if the tree is balanced
If it is unbalanced, call function to perform necessary swaps

The only thing that I am unclear about would be how to know which type of rotation is to be used? How would you check to see if it is a right rotation, left rotation, or one of the other 2 types?

[Ganon11]

You would have to check the specific values of the heights where the tree was unbalanced.

Let's say that, in the above example, height(X3) = 6, height (B) = 4, height(X2) = 7, height(X1) = 8. So the tree is unbalanced at X2 (because height(X2->left) is significantly different than height(X2->right)). So you go to the parent of X2, namely X1, and check if X2 is a left child of X1 or a right child. A single rotation occurs when you have a bigger subtree in the left child of a left child, or the right child of a right child. In this case, X2 is the left child of X1, so you want to check if X3 is a left child of X2 - wait, we already determined this (from our comparison of the height() of each subtree).

If the heights had been reversed (height(X3) = 4, height(B) = 6), you would have needed to perform a double rotation, which you should know how to do.

The actual rotations are done with some simple manipulation of pointers - say, making X1 point to X3 instead of X2 or something.