Table of Contents
• What is Binary search Tree (BST)
• Drawback OF BST
• How BST CAN BE IMPROVED?
• AVL TREE AND ITS ROTATION
Binary Search Tree
At first how we could create an BST Tree from given set of keys. Let’s see an example given below you could see the key are arranged such that all the element at left side are smaller than the root node and the right side will always contain the element greater than the root node. In this way the element are arranged in AVL Tree. Reason for making AVL Tree, it is very helpful for searching the element in a tree. There are two possibilities when we do searching either search is found or not. I will discuss both search with example as you read ahead.
Successful Scenario:
No lets found the key element 30 in our tree. Searching will always start from the root node, as we know the root node is 40 so in this case our key is smaller than 40 so we will go to left side when we go left we reach at root node 20 and now we will compare our key element node with node 20 we found key node > 20 so now we will go in right direction in depth we will ultimately find the our key element.
Unsuccessful Scenario:
Now here we have to find key = 65. So again, we will start from root node and start comparing the key with node until we found the solution but this time what will happen as you could see in the figure below. If (65 > 40) so start moving in the right side/path then next node is 50. Again 65 > 50 move in right path ahead we reach at node 60. Here also we don’t find the case again if condition will be applied but we don’t have any node ahead after 60 neither in the left side nor in the right side. So, this is what unsuccessful search looks like. If there is 65 it will always be at the right side of node 60 and not in the left side.
From both the scenario, we also come to know that maximum number of comparison will depend/ equal to height of the tree. Height of the tree is counted from zero so in my case the height will be two as shown below. Time take for searching will depend on the height of the binary tree. Height of the binary tree will be maximum, or we could say the worst case will be O (n) and the best/ min will be O (log n).
DRAWBACK OF BINARY SEARCH TREE
Problem with Binary search Tree:
First creating a binary search tree: We will create the tree using the key given below
Key: 40, 50,10, 20, 30, 35, 5
Now we will put 40 as root node and start from 40. We will check whether the next key provided is smaller than the root node or greater, if it is smaller, we will go in left otherwise right. Now 50 > 40 we will go in the right we found there is no node at right to compare so we will insert 50 as a new node to the right of 40. The same Process will be going on until all the key are placed in a tree. There is a problem with binary search tree is that height of a tree is not in our control which may lead to O (n)and is totally dependent how the key elements are inserted which might lead our diagram to be somewhat like this as shown below. This is the case where binary search tree become similar to the linear search tree as 60 >40> 30> 20 > 10 > 5. Drawback of binary search is that for same key we could get different shape of binary tree that could be of max height or min height.
HOW BST TREE CAN BE IMPROVED
Let key: 40, 60, 70
From three key, we have total 6 order possible or we could say 3! Order are possible as shown above and from those order we could see that there are four order or fig with maximum height 2 but there are also two order where we have minimum height 1. Our objective is to find the min height for our binary tree so that search time is reduced. In order to find the minimum height for the BST we have to look for a certain method, and here the rotations come in handy through which we could balanced our tree while inserting the key elements in a tree. Balancing position of the node will be {0, 1, -1}. Let us talk about how we could balance the order:
For 40, 70, 60: We could see there is RL Imbalance so in order to make this one we will do this in two first we will do right rotation from 60 to 70 ad then left rotation as shown below together this is going to be known as Right Left Rotation.
For 40, 60, 70: In order to do rotation first we have to identify what imbalance is there in our order. In this we could clearly see it has RR imbalance, so we will use single left rotation to make our order balanced shown below.
For 70, 60, 40: In this we have (left left) LL Imbalance and single-right rotation will make our order balanced and provide us with a minimum height binary search tree.
For 70, 40, 60: In this we have Left-Right Imbalance and will be balanced by Left-right rotation as shown below.
For other two we already have those Balanced so no need of doing rotations. This is how we could use rotation to build a tree with minimum height. A balanced tree after doing rotation is considered as an AVL Tree. Moreover, if we have large number of binary tree, rotation will always be done at three node, whatever the size of the binary search tree is, we will always looks for three node and by doing rotation on them we balanced those node and our tree will automatically will be balanced.
AVL TREE AND ITS ROTATION
AVL tree is known as height balanced binary search tree. For this we defined one entity called balance factor. How to Calculate this? The formula will be:
BF = Height of left (HL) – height of right (HR) = { -1, 0, 1} It means they are balanced
So now let take an example to make a balanced AVL Tree by doing rotation and also complete labelling of balanced factor.
Keys: 40, 20, 10, 25, 30, 22, 60
This is the method of creating AVL Tree. One point to remember don’t allow any node to exceed the balance factor to 2 or -2, etc. As soon as it become imbalance just do the rotation and try to balance the tree and then do the insertion again.
Latest comments (4)
The concept of binary tree is cleared but when you started explaining about balancing the tree I was lost, I wasn't able to understand. I would suggest you to explain how to balance a tree and then move forward with explaining AVL tree. It's a great post. Looking forward to more post like this explaining different data structures and algorithms.
it was difficult for me to understand binary search tree and how it rotates when it gets unbalanced nodes. This blog helped me a lot as it explains each step very clearly. this blog was very helpful.
I had some doubts regarding BST and I tried to understand regarding it via a lot of websites and youtube videos but wasn't that successful. I got this website after a lot of research and found out that it's really informative. All the basic concepts can be understood via this website clearly without any doubts. Thanks for the post
Hey bud, I was actually working on an assignment on AVL tree, and this post really helped a lot. It has all necessary information about Binary Search tree and AVL tree. Thanks for the post and keep on going, cheers! :)