AVL Trees & Rotations (Self-Balancing Binary Search Trees)

so in this video we're going to be covering AVL trees if you have not subscribed to the channel hit the subscribe button and like this video or watch the video and then like it it helps us out a lot if you want to support us go to the backs of X we comm websites we are hosting a growing service and we're going to all talk about it at the end but let's get into the lesson first in this video we're going to be looking at AVL trees now we've looked at binary search trees before we know that they have the property if we look in the left subtree we're gonna have items less if we look in the right subtree we're gonna have items greater than or equal to sometimes I've seen it less than equal to and then greater well all that AVL trees add on to that is we're going to have a self-balancing property to them and they're going to balance themselves after we do inserts and outer we do deletes and why do we want to do that remember that if we have a binary search tree let's say we were inserting 3 2 & 1 that is skewed to the left we see so that's going to be linear if we were trying to search because we have three nodes and we're going to have to search all of those nodes we could go as deep as that last note the whole thing that we're trying to avoid is that skewed 'no sand if we balance our tree and define certain thresholds on the balance we have at each node we can keep these searches logarithmic and that's what we want to do so that's what we want we're going to talk about balance we're going to review what balances we're going to look at rotation where do these rotation operations we're going to look to look at left rotations right rotations left to right and right left and then we're going to be doing an implementation of insertion in the interest of time we're just going to do insertion it's going to be a good bit of code so I just realize that's not a binary search tree let me fix that going back to that property we know that our left subtree is less than and then that right subtree is greater than or equal to and what we're gonna do is we're gonna have a rebalancing threshold and we're going to look at the balance at every node in the tree if we break a certain threshold in standard AVL trees that's going to be one we're going to need to rebalance I keep talking about balance thresholds let's actually look at the idea of balance first and then we'll get into our rotations so now balanced remember we always talk about trees in a recursive manner we have this node N and this node is going have a left sub-tree and a right sub-tree they're both going to be recursively defined so every single node routes its own subtree we think about it recursively and if we were thinking in terms of a function we would have a function and then we would have that node as a parameter to the function and do something with the left and right subtrees we need to define a height what is the height of a subtree so if we have nothing if we just have a null node we're going to say that the height is minus 1 we could call it height 0 it could be either as long as we stay consistent so we have a height of minus 1 and I sometimes like to say it's underwater if we just have a null node it's like we're underneath the tree that's just kind of how I remember it I have a little fish swimming there and then if we have a single node we're going to have a height of zero so in this case if we just had a single note that's height zero and then as soon as we start adding nodes on we need to have a recursive definition for this height so we're going to say let me find the height out of this left subtree and remember this guy up here that node n wants to know the height of his subtree the way he's going to get his height is he needs to look at the left subtree he he owns and the right subtree we're gonna look at the left subtree right there we're gonna look at the right subtree right here we're gonna see between these guys who has the larger height and then we're gonna add one to that so then there we go that's going to give us the height and we're going to see more examples of this as we continue on so that is height if we have nothing it's going to be minus one if we have a single node is going to be zero if we have more than a single node we're going to need a recursive definition now what is balanced at a specific node mean balance is going to be the height of the left subtree minus the height of the right subtree that is going to give us the balance at a certain node n and so what an AVL tree does is it's going to keep this balance the absolute value of this balance within a certain threshold and here we see it can be parameterised so AVL trees are going to have a threshold of 1 we can make that threshold more but the standard threshold is going to be 1 so that's what we're going to see in our examples now let's do some examples and start calculating some balance I've kept these two things up here are balance equation and how our threshold is going to be one we're going to start at the root node what is the balance of that node 3 so we have the balance of 3 we need to look at the left subtree so do you see this tree right there that is a whole tree to itself and we need to consider what the height of that is so we see a single node at the root so that's a height of 0 as we defined before and then we have a left subtree which is just a single node we have a right subtree which is just a single node ultimately the heights of that left subtree becomes just 1 and so the height of that left subtree is 1 and now what is the height of the right subtree that's going to be this guy we see that it's a single node and since it's a single node we know that's height 0 and then once we evaluate this we're just going to get 1 so okay now this is 1 and what was our threshold our threshold is 1 we look at this threshold right there 1 is less than or equal to 1 1 is equal to 1 we know that the balance at that top node is 1 so let's just make a note of that okay so we just calculated the balance at the root node the balance is 1 and I want you to notice something this is left heavy so I want you to notice look at the equation if we have a positive balance that means that that left side of the equation that guy right there is dominating and he's going to bring us positive that means we're left heavy if we're right heavy our balance is going to be negative this guy over here is gonna dominate our equation that is something to just pay attention to that's going to be a part of our pattern matching later it'll make us it'll make it really easy to internalize our rotations later so now we can continue on we can calculate the balance for this guy right here what is the balance for him so we're going to say what is the height of his left subtree minus 1 what is the height of his right subtree minus 1 and then 1 minus 1 minus minus 1 that's just going to be 0 so the balance F 4 is 0 ok so now let's look at the 1 let's calculate the balance over there he has a left subtree single node what is a single node height 0 and then we need to find the right subtree height we need to find the subtree the height of that guy right there his high to 0 he's just a single node so 0 minus 0 is 0 so that means that the height at this one going to be zero or the balance is going to be zero and so if we continue on we're going to see that the balance of this zero here is a zero he is a minus one left two minus one writes that's just going to become zero same thing for that guy right here so we're just going to make those zero so we can see that this tree is special we have a balance of one balance of zero balance of zero balance of zero a balance of zero all of those are within our balance parameter we want to stay within a balance of one so the absolute value of any of those will be less than or equal to one this is an AVL tree it is adhered to our threshold all of the balances check out and there's nothing we need to do here this tree is balanced we're going to have logarithmic search now let's look at a tree that might not adhere to this property so let's look at this tree okay so we have a tree right here let's start at the four and let's find the balance out of four we're going to need the left subtree minus the right subtree and that's going to give us our balance the right subtree of four let's do that very quickly it's empty so just minus one so the left subtree has a height of a height of zero and then we have one and then two so then we can just eyeball this and we can see that the height is two we could do the math but we can see that we have a single node which is zero one and then that is two minus this minus one to plus one equals three we see that instantly at our root node we have broken the the the property and and this is not an AVL tree so this is not an AVL tree and this brings us to rotations rotations are how we're going to maintain we're going to maintain the binary search tree invariant at the same time as maintaining this balance threshold right here that let's look at what rotations are and specifically what are they trying to achieve when we're talking about rotations we could start out with abstract sub trees and and that can get confusing if you're not used to the notation I'm going to just start off with some pattern recognition and just get kind of build up a intuitive sense of what should we do when a tree looks a certain way although in reality you would you look at the math we'll look at implementation but I think this is a good way to step into this first and then we'll go to the concrete implementation you'll become very straightforward rotations fix imbalance in archery basically what we're doing we're trying to move notes over to the other side of the tree that needs notes if we're left heavy we want to go to the right if we're right heavy we want to move notes to the left and there's specific ways we have to do this so specifically if we're left heavy we're going to do right a right rotation or a left rotation and then a right rotation we would call it a left-to-right rotation and we're going to see exactly what these look like no worry about that if we're right heavy we're gonna throw nodes over to the left we can do a left rotation or we'll do a right rotation first and then a left and we'll see these two guys are confusing at first these are confusing until we see examples of what they look like here we see a right to rotation so this guy is a rights rotation and I want you to notice the tree on the left up here it could be left heavy and we're trying to move notes to the right sub-tree the key thing I want you to notice is there's always two nodes in a tango whenever we are doing these rotations two nodes are going to be critical and then all of the other sub trees are going to dance around and they're going to maintain that binary search tree invariants as we move these two critical notes notice those x and y's those are the nodes were going to care about and notice the special properties we're maintaining doing this right rotation and these will be clear as we do examples there's a node X and there's a node Y we know that we know that Y is less than X let's just write some things we know Y is less than X so we see this little red triangle what do we know about that red triangle we know that that red triangle is less than Y in less than X okay we're just going off base we're just going off what we know we're we're not taking any we're not doing any abstract rotations we're not making abstract sub trees we're just looking at what the tree is telling us and this is a really good way to reason about data structure problems let's look at this blue triangle this blue triangle is greater than Y greater than or equal to Y and it's going to be less than X that blue triangle fits that property this purple triangle will be greater then or equal to Y and it will be greater than or equal to X what we do here is we want to move these nodes to the right we're gonna turn Y and we're gonna push Y up to where X is and then we're gonna bring X down and move it to become the rights child of this Y which has just become the root of this new tree before ok forget about all of these sub trees forget about those sub trees down there before we do anything I just want you to notice whenever we're doing rotations just move the Y in the X so the Y's gonna move to the root the X is gonna move down now we need to know where do the sub trees fall in place so that we maintain the binary search tree invariant and we don't lose any node so you don't want to lose any nodes let's look at the properties that we had before so we see that this sub tree right here the red one less than y less than x over here this subtree right there that makes sense that's also less than Y in less than X so that holds so then let's look at this blue sub tree right here so this guy is greater than or equal to Y and less than X and yeah that makes sense we went greater than or equal to Y and then we want less than X so everything's checking out so now this purple sub tree right there we're going to go greater than or equal to Y great we did that and then greater than or equal to X so we did the same thing and guess what we just did we just performed a rotation of these two elements and we kept all of these sub trees we maintained they their positioning and their ordering so this is still a binary search tree and we have fixed the balance now that we we've seen a rotation in action let's look at all the specific rotations so that we can get a better feel for them so remember order matters when we're doing insertions on binary search trees we're going to perform these insertions every single time we perform an insertion we're going to be checking to make sure we didn't break balance at any no to break this threshold property ok so let's insert 3 ok we inserted 3 we're gonna insert 2 if we insert 2 we're gonna want to go to the left so let's insert 2 so we just inserted 2 this is still a binary search tree all of the balances check out and we could recalculate them but for the sake of time I'm just going to you can do that in your head we'll just continue with this demonstration now we're going to need to insert the one so we're gonna go to the left and then we're gonna go to the left but there's a problem and so the more of these that you do you're just going to be able to see it I don't want to do the math at every node eventually you're just going to be able to see whether there's an imbalance but in reality if you were coding this you would want to know concretely we're going to be recursively after this after this node gets inserted the call stack will return to this function call he's gonna check his balance then he returns he's gonna check his balance that's how it would actually be implemented but for the sake of just you know speed we're just not gonna trace it as the code would do it we're gonna just talk it through root is imbalanced we have the low the right is minus one and then the left is going to be depth of one so this leads to a two so this is bad we just broke the property and so what rotation can we use notice what our balance is our balance is two and remember since our balance is to the left guy the left sub-tree is dominating we are left heavy so what does that mean we can do a a right rotation get those nodes out and let the left subtree move them to the right and so there's there's a catch to this we'll see that when we get to the left right rotation which is next so remember when we do the rotation only focus on x and y only focus on two nodes we're going to move this two up we're going to move the three down we need to fix the subtrees remember there's actually three sub trees going on going on here we're going to have this sub tree we're going to have this sub tree and we're gonna have that sub tree what do we do with those so first off these guys don't even exist so they don't even there they're not even the in the picture the code would have to handle them if they were populated but this one where does that one go well we know one is less than this Y we know one is less than this X so this one is can this one can just go here this is less than y less than X so we've maintained our property so that is the right rotation come notice how we started out we just rotated these guys just worry about X&Y just rotate the nodes that matter and then adjust the subtrees we saw that this subtree gets adjusted that is the right rotation take these guys move them to the right we're rotating to the right left heavy we fix the left heavy by moving to the right so now let's look at a different situation where we're left heavy but we can't just do the right rotation so now we're at a left-to-right rotation let's do this let's insert the three then we insert the one we can eyeball this we still see that we're balanced and then we insert the two we are left heavy if we calculate the balance at the root node which is where balance is broken we're going to see that we have minus one in the right subtree and then we're gonna see we have a balance of one in the left so again we have a balance of two can we just do the right rotation we're going to try that let's just try doing the right rotation pull the one up push the three down that is the right rotation started and then the two the two is gonna have to go right there because it's greater than one in less than three it's greater than one in less than three it's greater than one in less than three but this is not balanced if we look at the root the root has a -1 - if we look at the right this has a balance of 1 this is minus 2 that this is not balanced this breaks the AVL property so we can't just do a right rotation here there's something different we have to do this is where we would do something called a left-to-right rotation we're gonna take these two guys right here these two guys we're gonna do a left rotation and then once we do a left rotation there we're gonna do a right rotation on the subsequent node so first let's do a left two rotation so we're gonna pop over the to pop over the one so we did a left rotation there and the 3 is just gonna be up here now we've performed the left rotation right there that's the left rotation and so now we need to perform the right rotation up here so we're gonna do the right rotation so now we're gonna push the 2 up and then the three down and then the one goes here so this is it this is the final tree and this is a balanced binary search tree within our threshold so that's a left-to-right both of these are left heavy restorations now that we understand how these rotations are done our least we saw initial examples we can look at how we fix write heaviness and it's the exact it's just the opposite it's the same operations so now let's insert one let's insert two and then let's insert three we see we have a problem and now we can do a left rotation so we're going to bring the two up we're going to bring the one down so remember these are our nodes we're focusing on and we're moving to the left so that one moves to the left because it's the left rotation and then this three just goes right there and then this is our finished binary search tree so choose the root left right and that is the tree so that's our left rotation and then let's look at right left so insert a 1 we're going to insert a 3 and then we're gonna insert a 2 and this is when the balance is broken but again if we just do a left rotation what happens we're going to see 3 we're gonna have a 1 there and then the 2 is just the 2 is greater than 1 less than 3 greater than 1 less than 3 then the 2 is going to go here and again this is not an AVL tree so we need to do something different we're going to first do they're the right rotation we're going to do a right rotation so it's going to become 1 2 3 and then we're gonna do a left rotation so it becomes 2 1 3 and then that is an AVL tree this might be confusing at first this might not you might not get it at first but if you do a few examples do a couple practice problems on this it's going to become very very intuitive how these rotations happen so that's all we're going to cover for this video if you want to see the full implementation you can go to back-to-backs we comm we have a growing service we're working very hard on it in the past month we have released I think for programming languages we've released Java we've released sharp we really see sharp two days ago we released Python we release JavaScript we're going to release C++ in a week we're going to be releasing Swift golang maybe Ruby soon maybe in the next month and we have a ton of great things we want to build we've put the infrastructure in place to scale right now we have about a hundred thirty or so problems we want to we want to create three hundred problems five hundred high signal problems and that's what we're going to do with our service so the best way that you can support us is to go to back to vex we calm the link is in the description so that is all

Channel: Back To Back SWE

Views: 100,408

Rating: 4.9189272 out of 5

Keywords: software engineering interviews, avl trees, trees, binary search trees, back to back swe, programming interviews, dsa, data structures, data structures and algorithms, tree rotations

Id: vRwi_UcZGjU

Length: 20min 37sec (1237 seconds)

Published: Tue Apr 28 2020