Balanced Trees & Introduction to Self Balancing Trees | Trees | Data Structures Simplified
logo
Manas Sinha
Developer | Designer
logo
Manas Sinha
Developer | Designer

By Manas | 28 September 2021 | 2 mins read

BALANCED TREES AND
iNTRODUCTION TO SELF BALANCING TREES

Balance Factor | Why do we need SBT?
To start this article I would like to remind you of the reason we introduced tree data structures in the first place? Along with the hierarchy, trees help us to do a certain operation like search, insert, etc on a set of values in O(log N) time which might otherwise take O(n) time if we were to use some linear data structure like arrays or linked list. With this in mind, look at the below three images:
  • The first one is a simple binary tree. Think of searching for a value in this tree. Since there is no order, we will have to visit all the nodes. Hence, it will take O(n) time. This doesn’t seem to be helping us. So, we came up with another structure, the Binary search tree.
  • The second one is a binary search tree. This tree has the property that the values in the left subtree are less than the root node, and the values of the right subtree are greater than the root node. And this property holds for all the subtrees of this tree. Using this tree we can search a value in O(log N) time. But now look at the third image. It is also a BST.
  • The third one is a skewed BST. This looks similar to the linked list. If we try to find a value in this tree, the complexity will again be O(n). This is the worst case of a BST. The skewed BST. The evil doesn’t seem to stay quiet, does it?. What do we do now? We are again at square one. Or are we? Try to think about how can you solve this problem? The answer is to balance this tree like this:
Now I think you must be getting an idea of why we are even bothering learning a new data structure which is the Self-balancing tree. If you are not, I suggest you read the above four paragraphs again. Because before learning anything, you must first know why? Well.. it’s true in most cases, sometimes you have to take a leap of faith. Let’s now see what the technical definition of ‘Balanced Tree’ is.

0. WHAT IS A BALANCED TREE?

A balanced binary tree or a height-balanced tree is a tree in which the height of the left and right subtree at any node does not differ by more than one. Not just the root node, at any node. Mathematically we define using a balanced factor.
  • balance factor = height(left subtree) – height(right subtree)
and for a tree to be balanced:
  • | balance factor | <= 1
Note: The node with zero children will have a height of 0. The tree in example 2 is a balanced binary tree. But as you can see in example 1, even if the balance factor is less than 1 at the root node the tree is not balanced as all its sub-tree is not balanced.

1. FIND IF A TREE IS BALANCED OR NOT.

Check if a tree is balanced or not programmatically:
/* Author: The Binary Realm */
/* CPP function to check if
a tree is height-balanced or not*/
bool treeIsBanaced(TreeNode* root, int* curr_height){

	/* If the root is null the height is -1*/
	if(root == NULL){
		*curr_height = -1;
		return true;
	}

	int left_height = -1, right_height = -1;

	/* check if the left and right subtrees
	 are balanced */

	bool left_balanced = treeIsBanaced(root->left, &left_height);
	bool right_balanced = treeIsBanaced(root->right, &right_height);

	/* height of the current node */
	*curr_height = max(left_height, right_height) + 1;

	int balance_factor = left_height - right_height;

	/* checking all the three conditions */
	return (abs(balance_factor) <= 1) && left_balanced && right_balanced;
}
AVL trees, red-black trees, scapegoat trees are some of the trees that implement the self-balancing feature. Whenever a new value is inserted into the tree or a value is deleted from the tree, the tree re-orients itself in such a way that the tree becomes balanced again, keeping the Binary Search Tree property intact as well. This solves our problem of trees becoming skewed. In our next article, we will see how one of these self-balancing trees, the AVL tree, and how does AVL tree implement the self-balancing feature as well as the code to do it.

LEAVE A COMMENT

If you like the post leave a comment and share it.

This Post Has One Comment

Leave a Reply