10.1 AVL Tree - Insertion and Rotations

topic is AVL trees and these are the things I am going to discuss in this one that is what is binary search tree drawbacks of binary search tree how binary search tree can be improved what is an AVL tree how the rotations are performed in AVL tree and how to generate a VLT or create an AVL tree from given set of keys let us start with the binary search tree this is a binary search tree here the keys are arranged such that for any node all the elements on the left hand side are smaller than that node the elements on the right hand side are greater than that node means for any node the elements in the left subtree are smaller than that key element and in the elements in the right subtree will be greater than that element so 30 is greater in 2010 is less than 220 so in this way the elements are arranged reason it is useful for searching how suppose I want to search for a key element say 30 then I will start my search from room and check with the root element is it 30 no 30 is smaller than that key element so go on the left hand side now is it the 30 no this is not 30 30 is greater than this key element so go on the right hand side now right hand side yes this is the key element found so total three comparisons we got the element let us take one more if I am searching for the key element 60 then is it 60 no 60 is greater than this one so go on the right hand side is it 60 no 60 is greater than 50 so go on the right hand side yes I got the element so only in three comparison I got this element let us take one more key suppose I want to search for a key element 32 let us search for it start from here this is not 32 32 is less than this one so go on the left hand side this is not 32 so 32 is greater than this one so go on the right hand side this is not 32 32 is greater than this one to try to go on the right-hand side but there is nothing so now search fails so for this we cannot find the element so the point here is that when you are searching for a key element possibilities either it can be found or it will not be found so search may be successful also search may be unsuccessful also but when the search for unsuccessful how many comparisons I made one two three so total three comparisons so maximum number of comparisons required for searching any element in a tree depends on the height so the time taken for searching in a binary search tree depends on the height usually we mention height starting from zero onwards but I will take from 1 onwards 1 2 3 so let us say height of this binary search tree is a 3 so the time taken is dependent on the height for binary search tree so this is one of the property of a binary search tree that is useful for searching purpose the elements are organized smaller on left side greater on right side and the time taken for searching is depending on the height now the question is what is the height of a binary tree like binary search tree is nothing but a binary tree only what is the height of a binary tree height of a binary tree can be minimum login and maximum and so it depends for same set of keys we can form different binary search trees it may extend its height upto n also or it may reduce its height to logon also so it means the minimum time taken for searching in a binary search tree may be log n maximum time may be n so let us observe the next thing what is the problem with binary search tree let us see you how to create a binary search tree I have set of keys here and the same keys I have taken here also in the different order something I want to show you by creating a binary search tree let us first create a binary search tree for these keys what is the method of creating a binary search tree so we have to insert one element at a time so first key and that is 30 so there is nothing I have taken 30 here now inserting 40 40 is greater than root that is 30 so insert 40 on the right hand side then 10 is a smaller than root that is less than 30 so insert it on left hand side then 50 check from root for every element we should check from rule 50 is greater than 30 and it is greater than 40 so insert it here then d20 smaller than 30 come this side left side and 20 is greater than 10 so insert it on the right hand side the next is 5 5 is smaller than 30 come to left side it is less than 10 smaller than 10 also so insert it on the left hand side 35 is greater than 30 go to right side less than 40 so insert it on the left hand side she supposing if I am inserting again 50 then starts from here 50 is greater than 30 50 is greater than 40 50 it's already 50 50 is already present here so don't insert it so he don't insert duplicates in a binary search tree now this is the binary search tree I got based on these key elements what's the height of a binary search tree this is minimum height that is log n what will be the time taken for searching any key element and this one it will be log and that depends on the height of a binary search tree so height is log n so for the set of keys when I have created a binary search tree I got this height now same keys I have taken them here also see 50 is there 40 is there 35 all the keys are as it is so but the order is different now let me create a binary search tree for that start from the first key element 50 next is 40 40 is less than 50 so it will come as a left hand side then 35 is less than 50 and also less than 40 so it comes from left hand side 30 less than this less than this as well as less than this so it will come on this side then 20 is smaller than smaller than smaller than it comes this side and then come on this side and five comes on this side so this is the height height is what n height of a binary search tree is n see the keys are given such that the binary search tree when I am creating it is becoming height and so this is the problem with binary search team the method of creationists we insert one element at a time the method I have shown you but what will be the final height that is a not inert over control the height may be login also the height may be order of and also it depends how the key elements are inserted if the height is log and then the time taken for searching is login and if the height is n then the time taken for searching is n and it is similar to linear search then if I have to search in this binary search tree that is similar to linear search like see if I want to search for five then I should start from here five is smaller than this and smaller than this and small and so finally how many comparisons I have to make all seven comparisons so this is the problem with binary search tree that height is not under control it all depends on how keys are inserted so this is the drawback of binary search tree next can we improve binary search tree is there any chance let us look at this I have three keys here let us create our binary search tree using those keys see these keys if I insert them and created by the research tree then the tree that I will get is 30 then 20 is smaller than that 20 comes from this side and 10 is smaller than that it comes from this side so what is the order in which I have inserted I have first inserted 13 and 20 and then time can I insert the same keys in a different order yes there are many orders possible for the same of key so if I am getting the keys like this then this is the tree what I am getting is the order is different let us say it is 30 then 10 and 20 then how a tree looks like so 30 10 is a smaller than this so it comes to this side 20 smaller than 30 but greater than 10 so it comes on this side so this is the shape of a tree I am getting and can we take a different order yes I'll try a different order that is 10 30 and 20 so this is 10 and 30 is greater so he's come this side and 20 is greater than 10 but less than 30 so it comes this side the another shape I am getting if I take 10 20 and 30 then this is 10 20 is greater and 30 is greater than that so for different orders I am getting different shapes so for 3 keys how many orders are possible 3 factorial orders are possible that is 6 orders are possible so for already have taken so I will take 2 more 2 more or possible that a 6 are possible so 2 more I will take that is 10 D 10 and 30 or 20 30 and then 10 let us create 20 it comes here 10 is a smaller than this so 10 comes this side 30 is greater than this so it comes this side and for the next order also 21st that 30 comes from the right side 10 comes on the left-hand side so I am getting a tree like this so it means that for the same set of keys if I insert them in different order I am getting different shape of binary search trees if you look at these trees the height of these trees is 1 2 3 all these trees are having high 2 3 4 just three keys height is 3 so these are with a maximum height but this tree is of height 2 so this is of minimum height so this means that if you have some set of you can form a very long binary search tree also or a short hide binary search tree also so what we prefer is a minimum height by binary search tree so that the search time can be reduced this is the objective so the drawback of binary search tree is that for same keys we can get different shaped binary trees that can be of maximum height or even off minimum height what we prefer is we want minimum height binary search tree so now let us see whether by the research tree can be improved or not see for the same set of keys if I am getting in these orders I am getting this shade binary search trees but I want this one is there any way to convert this so there is no way just we say that just remove it and take this one if you're getting any other shape just take this one but there should be some method which we should define some procedure for converting that one into this one so for that we define rotations we say that we rotate this tree around this node that is will pull this 30 on this side so 20 will move up and then we'll move at this place so we say we will perform rotation around this node and we will change the shape of this node like this and similarly we will rotate this a tree around this node and we will change the shape so 10 will come down 20 will come this side and 30 will come this side it's just like you imagine that is a male fixed here and around that does the thread and you're pulling a thread so if you pull that thread here 10 will come this side 20 will move up and 30 will move up so he say that we will perform rotations and convert this larger height binary search trees into smaller hide binary search tree so this is how we can improve and this gives the idea of AVL tree then how about this how do you perform rotation so in one step we cannot do first we'll rotate around this 10 so 10 will come siren 20 will come up then we'll rotate around this 30 so 30 this side and 20 will move up and 10 will remain on the left-hand side so we get this shape and here also around 30 will rotate in this direction then around the stem will rotate in this direction so we will have four different type of rotations which we can convert binary search tree into a balanced binary search tree so that is the idea of AVL tree so in any shape we want this shape now you may ask one thing that just we have three nodes here what if we have many nodes in a binary search tree house rotations are done so remember rotations are done only on three nodes always whatever the size of a binary search tree may be we look for only three nodes and we try to arrange them or adjust them by performing rotation to get a tree like this and the entire tree will get balanced entire tree will be of minimum height only so this is based on three nodes only now I'm going to explain what is AVL tree then I will show the rotation then I will show how to create a AVL tree now AVL tree AVL tree is a height balanced binary search tree so for balancing the height of a binary search tree we define one factor or one property that is balanced factor we calculate balance factor for each node what is balanced factor height of left subtree - height of right subtree and ensure it can be written as balance of balance factorize height of left subtree - height of right subtree and it should be either minus one or zero or one not greater than one not less than minus one if any node is having balanced factor out of these three only then the node is balanced otherwise the node is imbalance if any node is imbalance we should do something for balancing it that is we should perform rotations for balancing that one how do you calculate the balance factors let us see one more formula I have written here that is absolute of balance factor should be less than or equal to one means minus or plus if you take it as positive only then it should be either zero or one positive one so we'll use this one now I mean here I have some binary trees there are no keys just I have taken empty nodes unlabeled nodes now let us see what are the balance factor of this one so how to calculate height of left subtree - height of right subtree for this node what is the height of left subtree so you take the longest distance in the left side one two and the longest this one on the right side 1 2 so this is 2 - 2 this is 0 same way for this node the longest distance on left side is 1 and right side there is nothing so 0 1 minus 0 is 1 and for this one left side it is 1 right side it is 0 so this is also 1 and there is nothing on left hand right so it will be 0 only so for all the nodes we got the balance factors as 0 1 1 0 0 these are within this set only so this tree is balanced because every node is balanced now let us look at this for this node 1 2 3 height is I'm counting edges ok the longest party should take don't count the nodes we are not counting the nodes we are finding the height so 1 2 3 - 1 so this is 2 this is imbalance the node is imbalance let us look at others also this is 0 left side right side is 1 2 2 so this is minus 2 so there's also imbalance this will be 1 - 0 it is 1 this is 0 only and this is 0 only let us calculate for this also left side is 1 right side is 1 2 3 so I am taking height right so this is 3 and this is minus 2 it is imbalance see I'm not counting nodes 1 2 3 4 not for height so take the longest distance now for this is the balance factor will be 0 leaf nodes will have factor 0 this is 0 minus 1 minus 1 this is 1 minus 2 1 minus 2 is minus 1 that's all these two trees are imbalanced they are having some nodes which are not hide balance but DISA tree is perfectly balanced now I learn about rotation if any node is imbalance based on a balance factor then rotations are performed for balancing that node so let us learn what are the rotations now we go for the first rotation the name of the rotation I'll right afterwards let us look at this I have a binary search tree the initial binary search tree just there are two nodes 30 and 20 let us check whether it is balanced or not the balance factor is 1 and 0 so this is 1 and this is 0 so this is balanced now industry if I insert and then they tend should be inserted 10 is a smaller than 30 it goes on the left side and it's less than 20 is goes on the left side and there is no 10 here so I can insert it 30 20 and 10 that is inserted on this side now calling the balance factor this is 0 and this is 1 and this is 1 2 and that side 0 only so this is true so this node became imbalance that node became imbalance now I have to perform rotation for balance that one but let us see why it became imbalance and this became imbalance because I have inserted on the left of left so this is left of left imbalance let us call it as left of left imbalance now I will perform rotation after rotation what type of rotation I should perform see for this node the balance factor is a 2 so it is heavy on the left hand side if it's balance factor is minus 2 then it means it's heavy on the right hand side okay I don't have to check which side it is heavy but one important thing is this note became imbalanced because we have inserted on left of left so perform this rotation on this one over the snore so over this node will perform this type of rotation so how it looks like then we will move up 20 moves up and 30 will move to the right side and 10 will take the place of 2010 now this is perfectly balanced this is balanced so because this was ll imbalance I have performed this rotation so let us call this rotation also as and then the rotation that is left left rotation so this is the first rotation this is initially 30 and 10 balance factors are this is 0 and this is 1 now I will insert 20 in this one so 20 is less than 30 it goes on left side but greater than 10 so comes on right side so 30 here 10 on the left-hand side I'm painting on the right-hand side of 10 now let us calculate balance factors this is 0 and this is minus 1 and this is 2 again this node is imbalance why it became imbalance because I have inserted on the left and then right so this is l/r imbalance and not in balance then you remember I said that whatever the binary search to you get with 3 nodes we will take a balance tree we want that one so on this we have to perform rotation so the rotations these are 2 step rotations so I will write down here 30 10 and 20 so first we'll perform rotation on this one so how it looks like 30 then 20 comes here and 10 comes here so you have perform rotation over 10 on this side by fixing a name here so who will move up 20 will move up that will not be affected so 10 is pull this side so 10 20 will move up it looks like this now perform this rotation if you perform this addition again the result is 20 will be in the root and 10 will be on the left hand side 30 on the right hand side in this way now this is the fixed point over which the rotation is done so 30 is move that side 20 moves up and 10 more so that's it so this is two-step rotation this is not 2 rotations this is double rotation we count that this also as a single one rotation only but this is having two steps inside so we call it as a double rotation now what is the name of this rotation the imbalance was left right type so let us call this rotation also and our rotation so so far we have seen two rotations that was ll rotation it was single step then LR rotation it is a double steps two steps are there now similarly we have two more rotations I will quickly cover them this is initial tree the balance factors are 0 & 1 now insert 30 in this one 30 is greater than 10 and greater than 20 so 30 comes from the right side of 20 then the balance factors are 0 and this is minus 1 and this is minus 2 so this became imbalance so which type of imbalance because you have inserted on the right of right so this is our our imbalance when are our imbalances there we will perform this type of rotation by fixing this mode will pay 20 here so 210 here 20 will move up and 30 will move up right so it looks like this again and the balance factors will be 0 0 0 what was the type of imbalance our our let us call this rotation also as our our rotation so this is the third rotation again this is a single rotation now next rotation initially the tree is 10 30 balance factors are 0 and -1 insert 20 in this one 20 will come as right side of 10 but left side of 30 balance factors are 0 & 1 and this is minus 2 so this note became imbalance hard became imbalance the insertion is done on right left so let us call this as our L imbalance now for this also two steps are required that is double rotation is required so that tree ten and thirty twenty first it is rotated around this one then ten comes here and twenty and thirty comes here then parcel rotation over this one over this mode over this node then the tray looks like this the balance is imbalances are L so the rotation is also RL rotation so that's all these are for rotations and now I will show you how to create a AVL tree by inserting keys one by one so we have seen total four rotations out of which and l and r r are similar these are single rotations and l r and r l are similar these are double rotations now i am going to show you special cases in these rotations suppose our binary search tree is like this these are the nodes ABC and it is having some left shot right child that is right child of a and there is B is also having some right child and C is having left child and right child so it means it's a very big tree don't know how many nodes are there below this one so we have just taken it as a right subtree of a so any number of nodes below that one but suppose this known became imbalance this node became imbalance because of insertion on the left of left the site the site so ll rotation how to perform this one we have to perform rotation around this mode ll rotation means imagine that assume that insertion is done on left of left of this a and a became imbalance so let us look at how rotation is done over that node and the rotation so don't look anything just look at ABC and draw this one so this is B and C and a as I said the rotations are done always within three nodes now what about others see left shine right cheering they will be as it is see left child and sees right child will be as it is then a night shared will also be in its own place then what is missing there B's right child so this is right subtree of B so it should be on the right-hand side of B only then where it should come that is the space remaining here is the space remaining so B's right child will come here B's right child will come here alright so this is you can take it like a formula or an example in a big size strain with lot of nodes beneath this one just we are looking at these three nodes out of which this node has became imbalance so this how we perform rotation I have shown you ll rotation it will be similar for our our rotation also it will be from that side this means that see if I remove everything and just take this one just take this one so imagine there is some nail fixed here and this is the thread and to a thread something is attached so there is a male and there is something attached to a thread and when you pull a thread on this side around that nail it looks like this then what about this thing that is attached it will go that side and look like this one so same thing has happened ABC and B was having write child when you pull this on this side a on this side so a there and what happens to be art it will come as a left of a removing all this if you just see this the effect is similar or if you keep a are so AR is as it is check it is just like there's a thread and a nail and you are pulling a thread on that side something is attached to a thread so after pulling that side this this thing right if it goes there the stick like thing which goes there so it looks like legs look like this this is the shape so the same shape we are getting here so that's all about ll I have shown you same thing you're gonna play on our our now let us look at lr rotation this is a binary search tree I have not taken a big size tree let us first look at just three nodes suppose this node became imbalance because of insertion on left right so we will perform an our rotation because it is a la imbalance so already have shown you how this rotation is perform first step like this then second step like this but finally what will be the result if first step is performed a B on this side see on this side and B comes here then again when this rotation is performed C goes here and B remains here and a will be on the right side it looks like this by taking two steps I'll remove this by taking two steps it looks like this now can we show it in a single step how we can show it in a single step just see this we can say that when you have to perform LR rotation out of three nodes the last node just you bring it into root C left side is B only that a you take it on right side that's all we say that we can directly always rotation is within three nodes only out of these three nodes last node you breaking into root and the root you send it on the right side because it is LR rotation in RL rotation you can bring root on the left side so LR and RL will be same so I have shown you how we can direct perform in our rotation without looking at these two steps directly we can bring this note up here and send a on that side now let us look at how it is done on a bigger sized tree if I have a tree like this a B and C on this side so a is already having its right side B is having its left side and C is having left child and C is having Rachel also and this became imbalance and imbalances alar imbalance l/r imbalance and I have to perform a la rotation now they are already having some children with them their sub trees are there then how rotation is done out of three nodes as we know that this ship moves up so C will move up B remains as it is a will come on the right side now what about the left child of B it will be as it is what about the right child of a it will be as it is now who are remaining left subtree of C a right subtree of C left of a C will go in the left sub left side only so C is here now so its left child will be on the left side only but it will become a right child of B and the right subtree will remain on the right side only but it will become a left child of a this is the method you can take it like a formula now I have shown you that when you have to perform an r and r rotation we can perform in a single step directly so that single step i have send it up so beyond this side only you have moved to the right side then the rest of the children are arranged so this is like a formula formula like you can take it and always follow this method and the last thing is I will take some keys and show you how our AVL tree is generated let us create a AVL tree of these nodes I will insert them one by one we will calculate balance factors if any node is becoming imbalance we will look at it which type of insertion is done why it became imbalance then perform corresponding rotations so let us take first key 40 is inserted this is a single node and it is balanced then insert 2020 we come on the left hand side and balance factors are this is 0 and this is 1 everything is balanced next is 10 insert 10 on this side now tell you add balance factor this is zero and this became 1 and this became 2 so height of left subtree is 1 2 so 2 right subtree is nothing is there so 2 minus 0 this is how it is becoming - so that became imbalance where the insertion is done on the left of left so ll rotation will perform ll rotation around this node so 20 here 10 this side 40 here and the balance factors are all zeros now it is balanced I'll remove this and use that one now insert next 25 25 is greater than 20 but less than 40 so it will come this side let us update balance factor 0 this is 1 and this is 1 and 2 so 1 minus 2 it is minus 1 perfect next 30 30 comes on right side of 20 left side of 40 but right side of 25 so 30 comes here update balance factors balance factors are 0 and this is minus 1 and this is 2 and this is minus 2 this is 1 minus 1 2 3 so this is minus 2 oh 2 moves became imbalance this is all same balance is also imbalance now we are learning one more thing if multiple nodes are becoming imbalance which one we should perform rotation where you have inserted here from there you go towards ancestor the first ancestor which became imbalance perform rotation over that so this is the first time so perform rotation over that one automatically that will also become balanced so according to this imbalance node insertion is done with side left right so this is a large rotation so we'll perform an hour rotation and our rotation means what instead of showing two steps we can simply take this 30 up and 40 this side so this becomes 20 on this side then here and here comes 30 25 remains here and 40 this one that's all l rotation is done the update balance factors 0 0 and this is 1 1 this is also 0 this is 0 this is 1 & 2 so this is minus 1 everything is balanced I'll remove that one now next node 22 where 22 will come right side of 20 left side of 30 and left of 25 so it will come here 22 there is update balance factors this remains 0 only this is 0 this is 1 and this is 1 2 and this is 1 so this is 2 minus 1 this is 1 only what about this this is 1 and minus 1 2 3 longest distance is 3 here so 3 is minus 2 so this became imbalance all our balanced only you see 0 0 0 1 1 and that became minus 2 so this node became imbalance now one thing to observe according to this where insertion is done right left left ah and no just take two steps are means consider only these 3 means no we inserted this one now whatever it may be wherever you insert who became imbalance this became imbalance then only two steps or three goals from that imbalance node so just three nodes you see right see even if I have not insulated 22 if I would have inserted 26 it would have came here then also insertion is on right left we say it will be right left right so will not take all steps just two steps from a imbalance node whoever we can imbalance from there just two steps so if you just take two steps perform a large rotation so as per in the rotation this 25 can be sent up 25 sent up and on this side comes 20 so what about 10 10 will be remain as a left child of 20 and this side 30 will be as it is and this is 40 what about this 22 who was left child of 25 it is still we are in a less subtree of 25 so it will come this side 22 will come this side that's how the rotation is performed like this we have performed our L rotation already I have shown you how our L is performed now last key is remaining that is 50 let us insert this 50 comes this side that is right side of 40 now if you check balance factor these are all 0 0 0 and this is 1 2 & 1 2 3 so this will be minus 1 and this will be 1 2 so this is minus 2 and this is minus 1 & 0 so this node became imbalanced perform rotation along this one so which type of imbalance are our imbalance of perform rotation so 25 and 20 10 and 22 they all remain as it is and this will be 40 and 30 50 now it's perfectly balanced binary search tree we got that is AVL tree Haida balanced ablt or my name is first in accord so this is the method of creating AVL tree now one thing to remember that don't allow any node to exceed the balance factor from minus 2 or 2 you should never get minus 3 or 3 if it is becoming imbalance then under rotation don't wait that first I will insert all the notes then afterwards I will perform all the patient's no this is not possible whenever any node is becoming imbalance just after insertion if any node is become imbalance then just perform rotation and balance the tree now I take you I will show you one more last situation then Howrah distant let us look at one last thing a baby tree I have taken here let us see whether it is balanced or not balance factor for leaves will be zeros only these are all zeros then this node 1 1 so this is 0 this is 1 2 1 2 3 so this is -1 balance only what about this 1 1 2 1 2 so this is 0 and this is also 0 this is minus 1 so all those are perfect so they are all balanced so the tree is balanced now I will insert a new node that is 42 so 42 is greater than 40 less than 50 less than 45 but greater than 41 so 42 comes here let us see what happens I'll update the balance factor this becomes 0 this becomes minus 1 this becomes 1 2 and this is 1 so this becomes 1 and this is 1 1 2 3 and this is 2 so this also becomes 1 and what about this this is 1 2 so this is 2 minus 1 2 3 4 4 and this is minus to this node became imbalance now which rotation I should perform where I have inserted right left left right right left left right don't take all steps just take first two step left right remove this one I have to perform addition by using just three nodes so what happens 45 degrees or 40 moves here what about all other nodes already have shown you the formula how they are adjusted so just you can follow that and complete rotation so that's all the height of a AVL tree is always balanced so it's a balanced height balanced binary search straight so binary search tree only but it will maintain the height and it will try to maintain always log and height it will not exceed 2 n unlike binary search tree so at most the height of a AVL tree is measured as 1 point 4 4 into log n so at most it may be 1 point 4 4 into log n but it cannot be always exactly log and it may be little then little bigger also but it will be multiples of log in only so asymptotically we say the time taken for searching in a AVL tree is log n that's all about AVL tree just like AVL tree there is one more height balanced binary search tree that is a red-black tree the idea of red black tree is also same as AVL tree but AVL tree is more strict and there may be many rotations perform in AVL tree while creating AVL tree we may be performing lot of rotations to avoid bad rotations more frequent rotations red black trees used red black tree is not having that much strict rules as compared to AVL tree but red black tree is also as efficient as AVL tree so these are to hide balanced binary search trees so we have discussed about AVL tree and that's all about this

Channel: Abdul Bari

Views: 540,724

Rating: 4.9527102 out of 5

Keywords: avl trees, binary searcl trees, avl, rotations, rotations in avl trees, algorithms, algorithm, abdul bari, bari, gate

Id: jDM6_TnYIqE

Length: 43min 8sec (2588 seconds)

Published: Fri Mar 16 2018