All About Balanced Binary Tree
Balanced binary search trees like AVL tree, m-tree, and Red-Black Tree are way more efficient than unbalanced binary trees. Hence, these efficient trees result in more efficient time complexities and can be used for data organization in the memory.
In this article, we will discuss a balanced binary tree, the conditions for a balanced binary tree, a self-balancing binary tree, and how to check whether a binary tree is balanced or not.
Table of Contents
- What is a binary tree?
- What is a balanced binary tree?
- Examples
- How to check whether a binary tree is balanced or not?
- Implementation
What is a Binary Tree?
A binary tree is an important data structure in computer programming as it can organize data efficiently. Binary tree in data structure has numerous types, and one of its most important and widely used types is the balanced binary tree. A binary tree has either zero, one, or two child nodes but not more than two. Other types of binary trees include a Complete binary tree, full binary tree, skewed binary tree (left-skewed tree, right-skewed tree), and degenerate binary tree.
Check out free data structure and algorithm courses
What is a Balanced Binary Tree?
A balanced binary tree or height-balanced binary tree is such a tree whose left and right subtrees' heights differ by not more than 1, which means the height difference could be -1, 0, and 1. A balanced binary tree is also known as a height-balanced tree.
Necessary conditions for a balanced binary tree:
- The height difference should not be more than 1.
- The Left sub-tree should be balanced.
- The right sub-tree should be balanced.
The height difference of a tree is calculated as |Left subtree| – |Right subtree| or |Right subtree| – |Left subtree|. The difference should not be more than 1.
Example of Balanced Binary Tree
Best-suited Data Structures and Algorithms courses for you
Learn Data Structures and Algorithms with these high-rated online courses
Self-balancing Tree
In data structure and programming, we mainly discuss two self-balancing binary search trees, which are as follows:
- AVL tree
- Red-Black Tree
AVL Tree:
If any binary tree, which is balanced means whose height difference or balance factor is 1, then it is known as an AVL tree. AVL trees are self-balancing binary search trees. AVL trees left sub-tree and right sub-tree to have a height difference at most 1.
If there is any disturbance in the balancing factor or the height difference between the left sub-tree and the right sub-tree is more than one, then we must balance the binary tree. balancing of the binary tree can be done using:
- Left Rotation
- Right Rotation
- Left-Right rotation
- Right-Left rotation
Red-Black Tree:
A red-black tree is a binary search tree with the property of a self-balancing binary search tree. For balancing the height of the tree, it uses two colours, red and black, in order to ensure that the tree is balanced even after multiple insertions and deletion operations. Being a variant of a binary search tree Red Black tree also has at most two children, which means that a node either can have zero, one, or two children but not more than two.
Here are some properties of the Red Black Tree which must be considered whenever designing a Red-Black tree, so the properties are as follows:
- The red-black tree is a self-balancing binary search tree.
- The root node should be Black in color.
- Every node would have either red/black color.
- Every leaf node which is NIL would be in Black color.
- If the node is in Red color, then its children must be in Black color.
- Every path from a node to any of its descendant NIL nodes has the same number of black trees.
Explore Free Online Courses with Certificates
How to check whether a binary tree is balanced or not?
Here are a few conditions; by checking them, we can ensure whether the given tree is balanced or not.
- The height difference or balance factor should be at most one, not more than that.
- The left sub-tree should be balanced
- The right sub-tree should be balanced.
The pseudo-code for checking a balanced binary tree is as follows:
- If node == null, then return 0
- Check the left sub-tree. If not balanced → return -1
- Check the right sub-tree. If not balanced → return -1
- The absolute difference between heights of left and right subtrees. If it is greater than 1 → return -1.
- If the tree is balanced → return height.
Implementation
int main() { int height = 0;
struct node *root = newNode(A); root- > left = newNode(B); root- > right = newNode(C); root- > left- > left = newNode(D); root- > left- > right = newNode(E); if (checkHeBal(root, &height)) printf("The tree is balanced"); else printf("The tree is not balanced");}
#include < stdio.h > #include < stdlib.h > #define bool int
struct node { int item; struct node *left; struct node *right;};
struct node *newNode(int item) { struct node *node = (struct node *)malloc(sizeof(struct node)); node- > item = item; node- > left = NULL; node- > right = NULL;
return (node);}
bool checkHeBal(struct node *root, int *height) { int leftHe= 0, rightHe= 0; int l = 0, r = 0;
if (root == NULL) { *height = 0; return 1; }
l = checkHeBal(root- > left, &leftHe); r = checkHeBal(root- > right, &rightHe);
*height = (leftHe > rightHe ? leftHe: rightHe) + 1;
if ((leftHe - rightHe > = 2) || (rightHe - leftHe > = 2)) return 0;
else return l && r;}
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
