TREE BALANCING

TREE BALANCING

Trees are used to represent the hierarchical structure of a given set of data and to reduce the search time of a element than that of a linked list. This applies more to trees which are perfectly full or close to being perfectly balanced as given in figure 1.

Figure 1: (Right) Tree which is close to being perfectly balanced (Left) Perfectly balanced tree

When considering the trees given in figure 2 we cannot say that it preserves either of hierarchy or the ease of search factors. In the trees given below if we try to search for an element in the left subtree it will be closer to liner time which is O(n). If we remove the right child from the left tree in figure 2 we can reduce that tree into a linked list where the worst case search time is O(n). These trees are called unbalanced trees and the process of fixing these trees so it structure looks more like the trees in figure 1 is called tree balancing. A tree is balanced when the height difference of the subtrees in a binary tree is at most one (ex:- AVL trees). In some types of balancing techniques (ex:- Red-Black Trees) the height difference is relaxed up to being at most two.

Figure 2: Trees that are close to being linear

Tree balancing can be divided into two categories as known as global and local tree balancing. Figure 3 shows the categories of tree balancing and the algorithms and types of trees associated with each category. 

• Global Balancing:   This type of balancing happens after all the operations (inserts and deletes) on the tree is completed. The effects caused by these types of balancing techniques affects the whole tree. 

• Local Balancing:   This type of balancing occurs after each insertion or deletion provided that an imbalance has occurred due to the operation. The effects caused by these trees are constrained to a part of a tree.

Figure 3: Tree Balancing Taxonomy

The tree balancing algorithms or techniques makes extensive use of rotations (rotating a node about another node). Therefore it is important to discuss about rotations before we consider balancing algorithms.

Tree Rotations 

Tree rotations come in two flavors known as a left rotation and a right rotation which is symmetrical of each other. As illustrated in figure 4 these rotations can be transformed into each other because of their symmetry. In figure 4 the child (ch) is right rotated around the parent (par) which results in the tree on the right. Equally when the new child (parent (par))  in the left tree of figure 4 is left rotated around the new parent (child (ch)) will result in the tree on the left.

Figure 4: Right & Left Rotation

The values P, Q, R define other subtrees of figure 4. So if we consider the tree in figure 4 as a binary search tree then the values in subtree P is less than the value of Ch and the values in Q is greater. But every thing is less than Par. So when the right rotate takes place the binary search tree properties should also be preserved. Lets consider the tree given in figure 5.

Figure 5: Example Binary Search Tree

Lets try to right rotate 30 about its parent 35. (This can be simply said as right rotate 35. This way it is easier to remember) The following steps happen in the given order

• Since 35 is not the root we set 25 which was the grandparent of 30 as the parent of 30. Resulting tree after this step is given if figure 6. . If there is no grandparent this step is not performed.

Figure 6: Binary search tree after the initial step of the right rotation

• The the right subtree of 30 becomes the left subtree of 30's parent at the start which was 35. The resulting tree after this step is given in figure 7.

Figure 7: Binary search tree after the second step of the right rotation

• Finally the node 30 which was initially the left child of 35 becomes the parent of 35. The node containing the value 35 will be now take the place of the right subtree of the node containing the value 30. The final tree after the right rotation is given in figure 8.

Figure 8: Binary search tree after the right rotation is complete

The left rotation is performed using the exact same steps but this time all it should be the exact opposite of the right rotation. Pseudo code for the right rotation is given below. Note that the values of the child, parent and the grandparent is given as parameters to the operation. The main reason being that without having explicit references we cannot complete the rotation since the algorithm breaks the tree into two disjoint trees at a given point. 

Function rightRotate(Node child, Node GP, Node Par){

        if(Par != root)                //if it is the root it does not have a parent 

                     set GP as parent of child 

        set right subtree of child as the left child of Par 

        set Par as the right subtree of child

 }

In order to make the above pseudo code a left rotation one have to change the right and left values to be the exact opposite in the lines highlighted in blue.