Tree balancing

In the previous chapter, we saw how binary search trees (BST) are used to manage data. With basic logic, an algorithm can easily traverse a model, searching data in O(log n) time. However, there are occasions when navigating a tree becomes inefficient - in some cases working at O(n) time. In this essay, we will review those scenarios and introduce the concept of tree balancing.


NEW MODELS

To start, let’s revisit our original example. Array values from numberList were used to build a tree. As shown, all nodes had either one or two children - otherwise called leaf nodes. This is known as a balanced binary search tree.

A balanced BST with 7 nodes - O (log n).

Our model achieved balance not only through usage of the addWord algorithm, but also by the way keys were inserted. In reality, there could be numerous ways to populate a tree. Without considering other factors, this can produce unexpected results:

An unbalanced "left-heavy" BST with 3 nodes - O(n).

An unbalanced "right-heavy" BST with 3 nodes - O(n)

A 6-node BST with left and right imbalances - O(n)


NEW HEIGHTS

To compensate for these imbalances, we need to expand the scope of our algorithm. In addition to left / right logic, we’ll add a new property called height. Coupled with specific rules, we can use height to detect tree imbalances. To see how this works, let’s create a new BST:

//a simple array of unsorted integers
let balanceList : Array<Int> = [29, 26, 23]

height_root.png

Step one: "29" is added to the BST.

To start, we add the root node. As the first item, left / right leaves don’t yet exist so they are initialized to nil. Arrows point from the leaf nodes to the root because they are used to calculate its height. For math purposes, the height of non-existent leaves are set to -1.

With a model in place, we can calculate the node’s height. This is done by comparing the height of each leaf, finding the largest value, then increasing that value by +1. For the root node this equates to 0. In Swift, these rules can be represented as follows:

    //retrieve the height of a node
    
    func getNodeHeight(aNode: AVLTree!) -> Int {
        
        if (aNode == nil) {
            return -1
        }
        else {
           return aNode.height
        }
        
    }


    //calculate the height of a node
    func setNodeHeight() -> Bool {
          
        //check for a nil condition
        if (self.key == nil) {
            println("no key provided..")
            return false
        }    

        //set height variable
        var nodeHeight: Int = 0
        
       //compare and calculate node height
        nodeHeight = max(getNodeHeight(self.left), getNodeHeight(self.right)) + 1
        
        self.height = nodeHeight
        
        return true        
    }


MEASURING BALANCE

With the root node established, we can proceed to add the next value. Upon implementing standard BST logic, item 26 is positioned as the left leaf node. As a new item, its height is also calculated (i.e., 0). However, since our model is a hierarchy, we traverse upwards to recalculate its parent height value.

height_26.png

Step two: "26" is added to the BST.

With multiple nodes present, we run an additional check to see if the BST is balanced. In computer science, a tree is considered balanced if the height difference between its leaf nodes is less than 2. As shown below, even though no right-side items exist, our model is still valid.

//example math for tree balance check

var rootVal: Int!
var leafVal: Int!

leafVal = abs((-1) - (-1)) //equals 0 (balanced)
rootVal = abs((0) - (-1)) //equals 1 (balanced)

In Swift, these nodes can be checked with the isTreeBalanced method.

//determine if the tree is balanced 

func isTreeBalanced() -> Bool {

   //check for a nil condition
   if (self.key == nil) {
       print("no key provided..")
       return false
   }
                
  //use absolute value to calculate right / left imbalances
  if (abs(getNodeHeight(self.left) - getNodeHeight(self.right)) < = 1) {
       return true
  }
      else {
         return false
  }
                
}


ADJUSTING THE MODEL

With 29 and 26 added we can proceed to insert the final value (i.e., 23). Like before, we continue to traverse the left side of the tree. However, upon insertion, the math reveals node 29 violates the BST property. In other words, its subtree is no longer balanced.

Step three: "23" is added to the BST.

//example math for tree balance check

var rootVal: Int!
rootVal = abs((1) - (-1)) //equals 2 (unbalanced)

For the tree to maintain its BST property, we need to change its performance from O(n) to O(log n). This can be achieved through a process called rotation. Since the model has more nodes to the left, we’ll balance it by performing a right rotation sequence. Once complete, the new model will appear as follows:

final_rotate.png

Step four: Right rotaion on node "29".

As shown, we've been able to rebalance the BST by rotating the model to the right. Originally set as the root, node 29 is now positioned as the right leaf. In addition, node 26 has been moved to the root. In Swift, these changes can be achieved with the following:

    //right rotation sequence

     var childToUse: AVLTree = AVLTree()
     childToUse.height = 0
     childToUse.key = self.key
                  
      if (getNodeHeight(self.left) - getNodeHeight(self.right) > 1) {             

            //reset the root node
            self.key = self.left?.key
            self.height = getNodeHeight(self.left)
                
            //assign the new right node
            self.right = childToUse
                
            //adjust the left node
            self.left = self.left?.left
            self.left?.height = 0

       } 

Even though we undergo a series of steps, the process occurs in O(1) time. Meaning, its performance is unaffected by other factors such as number of leaf nodes, descendants or tree height. In addition, even though we’ve completed a right rotation, similar steps could be implemented to resolve both left and right imbalances.


THE RESULTS

With tree balancing, it is important to note that techniques like rotations improve performance, but do not change tree output. For example, even though a right rotation changes the connections between nodes, the overall BST sort order is preserved. As a test, one can traverse a balanced and unbalanced BST (comparing the same values) and receive the same results. In our case, a simple depth-first search will produce the following:

//sorted values from a traversal
23, 26, 29

Like this series? Subscribe to the newsletter and receive a free guide on iOS interview tips.