What is a Height-Balanced Tree in Data Structure

A height-balanced tree is a type of binary tree. If the absolute difference between the heights of the left and right subtree is less than or equal to 1, then the given binary tree is considered a height-balanced binary tree. This height-balanced tree includes the AVL tree (Adelson, Velskii, & Landis Tree) and the red-black tree.

Note:

HeightI

n a tree data structure, the level of a node is calculated starting from the root node, while its height is calculated starting from leaf nodes. The size of any leaf node in a tree data structure is equal to zero.

Height balanced tree conditions:

The conditions that make a binary tree a height-balanced tree is given below:

• The left and right subtree must have a height difference of less than or equal to one (1).
• The left subtree must be balanced.
• The subtree must also be balanced.

Note: We can also treat an empty tree as a height-balanced tree.

What is the Height Balance of a node?

To calculate the height balance of each node, we need to calculate the heights of both the subtrees of that node which leads to a recursive and non-practical approach. All the nodes of a given tree data structure store their respective data and maintain the information regarding the height balance values of its child nodes.

We calculate the height balance of a particular node in a given tree using the following formula:

height balance of node = height of right subtree – height of left subtree

The above formula can be explained below:

• The height of a balanced node is treated as positive if the right subtree is taller than the left one.
• The height of a balanced node is treated as negative if the left subtree is taller than the right one.

Height of a Height-Balanced Binary Tree:

In a tree data structure, the level of a node is calculated starting from the root node, while its height is calculated starting from leaf nodes. The height of any leaf node in a tree data structure is equal to zero. A height-balanced tree with an 'N' number of nodes has a height equal to O(logN). This can be proved as shown below:

PROOF:

A height-balanced tree has a minimum of 2 ^{((h / 2) – 1)} nodes, where h is the height of the height-balanced tree.

We mentioned 'minimum' in the earlier statement, which means that the number of nodes can be greater than 2 ^{((h / 2) – 1)}, where h is the height of the height-balanced tree. We can denote this as the function f(h), therefore

F(h) > 2 ^{((h / 2) – 1)}

Mathematical induction can prove the above points.

Note:

Mathematical induction Mathematical induction is a technique for a mathematical proof. When we need to prove a statement P(n) which holds all natural numbers where n = 1, 2, 3, 4, 5, . . . so on, which in laymen’s terms means that the provided statement is a sequence of infinitely many cases P(0), P(1), P(2), P(3), P(4), P(5), . . . etc., we use mathematical induction. This technique is explained with the help of informal metaphors like climbing a ladder or falling dominoes, etc.

The minimum number of nodes in a height-balanced tree with height 1 is N = 2. Therefore, F (1) = 2 >= 2 ^{((1 / 2) – 1)}.

The minimum number of nodes in a height-balanced tree with height 2 is N = 4. Therefore, F(1) = 4 >= 2 ^{((2 / 2) – 1}.

Now, let the height of the tree be ‘h’ where h – 1 > 2 and the statement 2 ^{( ( h / 2 ) – 1 )} is true for ‘h – 1’. According to mathematical induction, we need to prove that the statement 2 ^{( ( h / 2 ) – 1 )} is also true for ‘h’.

Generally, the tree of height h has a root node along with its two subtrees whose heights are equal to h -2 and h – 1 respectively as we are expecting the minimum number of nodes. Hence,

f(h) = 1 + f(h – 1 ) + f(h – 2)

f(h ) = 1 + 2 ^{f( h – 2 )} as f( h – 1 ) > f( h – 2 )

f(h ) > 2 * f( h – 2 ).

As the statement is true for the heights that are less than ‘h’,

f(h ) > 2 * 2 ^{( ( h – 2 ) / 2 – 1 )} i.e., f( h ) > 2 ^{( ( h / 2 ) – 1 )}.

We can observe that

Log(f(h)) > ((h / 2) – 1 or

h / 2 < log (f( h ) ) + 1

h < (2 * log(N ) ) + 2    { this represents that the minimum number of nodes of the height-balanced tree is N. Hence, f(h ) = N

Hence, it is proved that h = O(log( N ) ).

Why do we need a Height-Balanced Binary Tree?

The example below illustrates the need for a height-balanced binary tree.

Let us take a tree that is both a binary search tree and a height-balanced tree.

In the given height balanced tree, let us find the value 96. We can observe that the height of the given binary tree is 3. The search in a height-balanced binary tree starts at the root node. The root node's value is 35, which is smaller than the required value (96). Hence, we move to the right child node of the root node of the binary tree (whose value is 35). The value of the right child node of the root node of the binary tree (whose value is 35) is 49, which is less than the required value (96).

Hence, we again move to the right child node of this node (root node of the right subtree of the root node of the binary tree). The right child node of the root node of the right subtree of the root node of the binary tree (whose value is 49) has a value equal to 52, which is less than our required value (96). We repeat the above step, i.e., we move to the right child node of the root node of the right subtree of the root node of the binary tree, which has a value equal to 96. This node is precisely equal to the value we were searching for (96).

Our tree height was three, and we found our required value in three steps. Therefore, this proves that we can find any key in at most h steps when the tree's height is equal to 'h’.

A value from a height-balanced binary tree can be searched in O( logN ) time. A value from a regular binary tree can be searched in O(N) time.

Applications of Height-Balanced Binary Tree:

1. Height-balanced trees are mainly used in computations that involve massive data and databases. They help search for data rather than insertion or deletion.
2. Dictionaries and memory slots require balanced trees for their application.
3. Rather than databases, applications that require improved searching use height-balanced trees.
4. Storyline games apply height-balanced tree searching as well.
5. If a corporate company has employees, who work under shifts, then height-balanced trees can be used to store their information.

Advantages of Height-Balanced Binary Tree:

1. The height-balanced binary tree makes a typical case roughly one lookup less but improves the worst-case lookup time.
2. Height-balanced binary search trees provide better search time complexity.
3. As a gentle rule, a height-balanced binary tree works more efficiently when we spread the request frequencies evenly across the data set.

Disadvantages of Height-Balanced Binary Tree:

1. For deletion and insertion operations, height-balanced binary trees take longer running times.
2. To find any node to balance in a given height-balanced binary tree, we must go all the way up from its leaf node to the given node in the height-balanced binary tree.
3. Height balancing binary trees must keep balancing information in each node, increasing its memory size.

How to check if a given tree is a height-balanced binary tree: 

Recursion can be used to check whether a given tree is a height-balanced binary tree, and this is based on the concept that every subtree in a height-balanced binary tree is also height-balanced. The following operations can be performed to know if a given tree is height-balanced or not:

Note:

Recursion is a process in which a function or method calls itself repeatedly (directly or indirectly) until a given condition is fulfilled.

1. For each node, visit its left subtree and right subtree using recursion
2. Check the height of both the right subtree as well as a left subtree.
3. Calculate the difference between the heights of the left subtree and right subtree. If the calculation output is between -1 and 1 (the absolute difference is at most 1), then that particular node is height-balanced.
4. If at least one node is not height balanced in a given tree, it cannot be considered a height-balanced tree.