Balancing the tree

How to balance this tree structure

                                 13
                                /  \
                               8    18
                                   /  \
                      开发者_开发知识库           14    19
                                   \
                                    15

You didn't specified what kind of balanced tree you want. For example you can use AVL tree

If you count node highs then you will get that node 13 is disbalanced with worth -2 and 18 with 1 so you have to do right rotation in node 18 and left rotation in node 13. After that node become balanced.

After right rotation:

                             13
                            /  \
                           8    14
                                  \
                                   18
                                  /  \
                                15    19

After left rotation:

                             14
                            /  \
                           13   18
                          /    /  \
                         8    15   19

Your values are 8 13 14 15 18 19, so a balanced tree with these values could be:

       15
    /      \
  13        19
 /  \      /
8    14  18

To get this tree, I counted the values to get the general shape of the tree (filling layers left-to-right, top-down) then sorted the values and placed them left-to-right in the tree.

This has good performance if balancing a tree once, but should not be used to balance the tree after every insert/delete.

i am also a student and studying the avl tree, in this question the balance of node 13 is -2 which is the violation of avl condition , now this violation occurs because of insertion of new node 15. now the node which is violating the avl condition lets call it alpha , now we need to identify the case of insertion the cases of insertion are: 1) insertion in the right subtree of right child of alpha(alpha is the node whose balance factor is violating the avl condition). in this case we need single left rotation. 2)insertion in the left subtree of right child of alpha. in this case we need to do double rotation that is right left rotation. 3) insertion in the right subtree of the left child of alpha. in this case we need to do double rotation that is left right rotation. 4)insertion in left subtree of left child of alpha . in this case we need to do single right rotation to rebalance the tree.

now in your question this is case 2 , we need to do right left rotation to rebalance the tree. we will do the right rotation between the right child of alpha and parent of its left subtree. then after this we need to do a left rotation between the alpha and the new right child of alpha(which was the parent of left subtree of right child of alpha) after this left rotation we have a tree whoes root is 14 left child of 14 is 13 left child of 13 is 8. Right child of 14 is 18 left child of 18 is 15 right child of 18 is 19. i don't know how to post figer of this tree, the person Gaim answered this question too. so see the figer that he posted. I hope this will help.

In practice AVL trees are balanced upon insert, check if the node needs balancing, and using tail-recursion to balance everything on the way back up from the insert. Wikipedia's AVL article actually has some decent illustrations too:

http://en.wikipedia.org/wiki/AVL_tree#Insertion