Balanced Binary Search Tree
A balanced binary tree is also known as height balanced tree. It is defined as binary tree in when the difference between the height of the left subtree and right subtree is not more than m, where m is usually equal to 1. The height of a tree is the number of edges on the longest path between the root node and the leaf node.
The above tree is a binary search tree. A binary search tree is a tree in which each node on the left side has a lower value than its parent node, and the node on the right side has a higher value than its parent node. In the above tree, n1 is a root node, and n4, n6, n7 are the leaf nodes. The n7 node is the farthest node from the root node. The n4 and n6 contain 2 edges and there exist three edges between the root node and n7 node. Since n7 is the farthest from the root node; therefore, the height of the above tree is 3.
Now we will see whether the above tree is balanced or not. The left subtree contains the nodes n2, n4, n5, and n7, while the right subtree contains the nodes n3 and n6. The left subtree has two leaf nodes, i.e., n4 and n7. There is only one edge between the node n2 and n4 and two edges between the nodes n7 and n2; therefore, node n7 is the farthest from the root node. The height of the left subtree is 2. The right subtree contains only one leaf node, i.e., n6, and has only one edge; therefore, the height of the right subtree is 1. The difference between the heights of the left subtree and right subtree is 1. Since we got the value 1 so we can say that the above tree is a height-balanced tree. This process of calculating the difference between the heights should be performed for each node like n2, n3, n4, n5, n6 and n7. When we process each node, then we will find that the value of k is not more than 1, so we can say that the above tree is a balanced binary tree.
In the above tree, n6, n4, and n3 are the leaf nodes, where n6 is the farthest node from the root node. Three edges exist between the root node and the leaf node; therefore, the height of the above tree is 3. When we consider n1 as the root node, then the left subtree contains the nodes n2, n4, n5, and n6, while subtree contains the node n3. In the left subtree, n2 is a root node, and n4 and n6 are leaf nodes. Among n4 and n6 nodes, n6 is the farthest node from its root node, and n6 has two edges; therefore, the height of the left subtree is 2. The right subtree does have any child on its left and right; therefore, the height of the right subtree is 0. Since the height of the left subtree is 2 and the right subtree is 0, so the difference between the height of the left subtree and right subtree is 2. According to the definition, the difference between the height of left sub tree and the right subtree must not be greater than 1. In this case, the difference comes to be 2, which is greater than 1; therefore, the above binary tree is an unbalanced binary search tree.
Why do we need a balanced binary tree?
Let’s understand the need for a balanced binary tree through an example.
The above tree is a binary search tree because all the left subtree nodes are smaller than its parent node and all the right subtree nodes are greater than its parent node. Suppose we want to want to find the value 79 in the above tree. First, we compare the value of node n1 with 79; since the value of 79 is not equal to 35 and it is greater than 35 so we move to the node n3, i.e., 48. Since the value 79 is not equal to 48 and 79 is greater than 48, so we move to the right child of 48. The value of the right child of node 48 is 79 which is equal to the value to be searched. The number of hops required to search an element 79 is 2 and the maximum number of hops required to search any element is 2. The average case to search an element is O(logn).
The above tree is also a binary search tree because all the left subtree nodes are smaller than its parent node and all the right subtree nodes are greater than its parent node. Suppose we want to find the find the value 79 in the above tree. First, we compare the value 79 with a node n4, i.e., 13. Since the value 79 is greater than 13 so we move to the right child of node 13, i.e., n2 (21). The value of the node n2 is 21 which is smaller than 79, so we again move to the right of node 21. The value of right child of node 21 is 29. Since the value 79 is greater than 29 so we move to the right child of node 29. The value of right child of node 29 is 35 which is smaller than 79 so we move to the right child of node 35, i.e., 48. The value 79 is greater than 48, so we move to the right child of node 48. The value of right child node of 48 is 79 which is equal to the value to be searched. In this case, the number of hops required to search an element is 5. In this case, the worst case is O(n).
If the number of nodes increases, the formula used in the tree diagram1 is more efficient than the formula used in the tree diagram2. Suppose the number of nodes available in both above trees is 100,000. To search any element in a tree diagram2, the time taken is 100,000µs whereas the time taken to search an element in tree diagram is log(100,000) which is equal 16.6 µs. We can observe the enormous difference in time between above two trees. Therefore, we conclude that the balance binary tree provides searching more faster than linear tree data structure.