Self-Balancing Binary Trees Explained

Hey everyone, welcome back to my channel. In another new video we're continuing the Data Structural Algorithms Bootcamp. We are continuing with the Trees playlist for now. So as you know we already did the introduction of Binary Trees, Binary Search Trees, so you can check out the playlist and all the other amazing stuff that we've already done. We're doing the complete interview preparation bootcamp, notes, assignments, everything in the description below. But in this video we're doing the second video of the Trees lecture. We're talking about Self-balancing binary trees. So in this video I'm going to talk about AVL trees and then in next videos we'll talk about like some other types of trees like Fenwick binary index trees, segment trees, red and black trees and then we'll do some interview questions as well for trees which is obviously very important you know we did binary search then we did binary search interview, we did link list links list interview, we did recursion then recursion interview. So for trees also we're doing theory part and implementation part and in the end we'll do some very important questions part like how to identify patterns, how to solve any tree question. Okay, but in this video we're talking about self-balancing binary tree. No need to worry about if you don't know what a self-balancing binary tree is. Only prerequisite is all the videos we have done till now and the trees video specifically that I did previously. So I'm going to start with a challenge like what are the challenges with normal binary trees and then we'll talk about okay how balancing binary trees solve these challenges and in this video we're going to look at a very popular self-balancing binary tree obviously we'll look other ones in the later on but this is very important hence i'm making a dedicated video on this so we'll look at avl trees full form everything i'll tell you later avl trees one thing i want you to notice is sometimes people get intimidated by avl oh it's very difficult you know it's very confusing it is not confusing not confusing. Then what it is Kunal? It is actually, it has a lot of moving parts. Lot of things are happening. So with avial trees, lot of things will happen. But all of those things are very simple. Just the quantity is a little bit, it's not that high, just 4 test cases. Okay, there are only 4 cases, but still some people feel like okay this is too much. but i will actually teach you so if you're looking at it for any topic okay not just tree even when you do dynamic programming or when all the previous topics i've done in the past when you take a concept and you try to memorize that concept in the terms of oh this concept has four cases this concept has six cases this concept has 10 cases you try to memorize that without understanding what are these why are we having these many cases then it becomes overwhelming and difficult to you then you feel like it's difficult but i will make it clear to you why we only have four cases what is the significance of each case the thought process behind it when they created avl why did they only make four cases or whatever okay let's get started forget about avl right now let's just talk about binary trees normal binary trees so if i talk about a normal binary binary search tree in the previous video we have already learned how normal binary trees functions okay so let's say i have a 10 over here and now i'm saying hey kunal insert 5 into it okay 5 is smaller than 10 5 will go over here i've already covered this okay how binary search tree functions so if you are not understanding this please watch tree tutorial number one there's a com there's a tree playlist on my channel now insert 15 okay 15 will go over here now insert 10 uh sorry 10 is already there now insert 12. so 12 is greater than 10, so right hand side less than 15, left hand side so on and so forth you get the idea so the idea is that the maximum height, let's say it's going to be log of n, which is n is the total number of nodes so at any point of time we have already covered in the past how the insertion and your delete and your, you know, when you delete or when you try to search an item it will take log of n time very good, no problem, okay But the problem arises, let's say you are saying Kunal insert 5 in a binary search tree Ok, no problem, I have inserted 5 Now Kunal insert 7 into it Ok, so 7 is greater than 5, it will go on the right hand side, no problem Kunal insert 9 into it Ok, 9 is greater than 5, so it will go on the right hand side 9 is also greater than 7, it will again go on the right hand side Kunal please insert 11 into it Ok, 11 I will insert over here Kunal please insert 13 into it Ok So, can you see what is happening? If I want to search 13, it will have to traverse it n number of times. So instead of log n. it is now taking n complexity which is wrong whole point of binary trees is now destroyed whole point is destroyed this is the problem with binary search trees because a chain can form like this even if you have something like this Still, there is a chain, right? Not perfect log n is the answer. Make sense? That is the problem and that is what we are trying to solve. So, how do we define this problem? Okay, now defining the problem. Kunal, it looks like a problem when I am looking at it from my eyes, but how do you define it in a definition? Define the problem. No problem, we can define it. So, the problem is this, that for any tree, for any tree that you have, let's say we have this tree, something like that, okay? Let's say we have this tree. Now here you can see that the difference of height of left subtree and right subtree for every single node is going to be either plus 1 or minus 1, like less than equal to 1 for example. So here you can see what is the height. Height is the number of edges from the node to the bottom leaf. So for every single node, let's say we're talking about this node first. For every single node, think about the definition. For every single node, the height of the left and the right tree should not have a difference of more than 1. Okay, what is the height of this tree over here? What is the height of this tree? This tree's height is 2. What is the height of this one? 1. 2 minus 1 is equal to 1. Correct. So, this difference should only be less than or equal to 1. So, 1 or 0. And if you do, let's say, for example, if I say, for every node height of left, minus height of right can be equal to minus 1 plus 1 or 0 only. In this case, it is 1. But if you have something like this, in this case, this height is 1, height is 2 for this tree or this tree. 1 minus 2 minus 1 that's fine no problem okay and this you have to do for every single node for every single node you have to do this so now let's see i did it for this node right now i will do the same for this node so again take this tree and this tree here the height is 1 here the height is 0 differences 1 minus 0, 1. Yeah, sure. This is also balanced. Now again do for this node. For this node, 0 and so this is just 1 so I will just leave it. For this node, this is itself, it has no left or right children so I'll leave it and for this one, it's again just 1 as you can see over here. So pretty simple stuff, okay? So as you can see for every single node, I'm repeating it again and again, for every single node the left and right tree height can only be minus 1 plus 1 or 0. Let me take an example of a tree which is not balanced. This is known as balance tree by the way. Okay if I write the definition down, for every node Did my pen run out of ink? not working so actually this is the definition only what formula i have just written above for every node in the tree the difference in height of left and right sub tree of that node for every node should be less than equal to one or yeah should be less than equal to one cool so either one or zero now let's take a look in example and that that is a balanced tree that is called a balanced tree let's take a look at a tree which is not balanced so if i have this tree right here, okay, like this. This is okay for now, something like this. Fine for now, okay. Let's add in one more, okay. Now, how do we determine Kunal, whether this is a balanced tree or not? Look at the definition. The definition says for every node in the tree the difference of the left and right sub-tree height should be less than equal to 1. Okay, then I will start checking from here. What is the height of left and right? So, height of this is 1, 2, 3 and height of this is 1. So, 3 minus 1 is equal to 2, not balanced. Not balanced. Simple? That is basically balanced tree and unbalanced tree. I hope that is clear. Okay. In the previous example also, this is also unbalanced tree. You know, this one. Why? Because the height of the left tree is 1, right tree, left tree is 0, right tree is 1, 2, 3. So 0-3-3. Not good. Difference in height is 3 here. It's minus 3. Okay, very simple stuff. Cool. Now moving forward how to solve this problem solution Solution is self balancing binary tree. For example, one of those is AVL. Self balancing binary tree, now you understand what was the problem and what problem self balancing binary tree is trying to solve. So when you have a tree that is unbalanced, Let's say you're adding something adding something adding something and the tree becomes unbalanced self balancing binary We'll be like, okay. Don't worry. You keep adding into the tree as you wish I will restructure the tree in some way that it will always be balanced and what is balanced You already know the definition that is what self balancing binary is. Don't worry about how it's working Okay, just think about what it's doing for now. We will obviously look into the entire code base entire algorithm, all the theory, everything we will cover in this video. So don't worry about that. Try to focus on what this problem it is solving. What is meaning by self-balancing? Self-balancing means you just keep inserting in it and we will apply some algorithm that whenever you insert an item and that insertion makes the tree unbalanced, it will be like okay Kunal just added 20 in the tree, a node with value of 20 and it has made my tree unbalanced. No problem Kunal, just add it as you want. and normally I will restructure the tree in such a way that it will become balanced For example, this is balanced tree It's the same tree as previously So it's going to be like, Kunal right now this is balanced, no problem Kunal is going to be like, okay I will add one more node over here. The tree is going to be like, oh now you added one more node, now this tree is unbalanced. So don't worry. Add your node where it's supposed to go. I will then restructure the tree and balance it. How we are going to balance it, we will figure out later. Okay? Sounds good? Let's move forward. So that is basically what self-balancing binary tree is. And one of those trees is called AVL tree. So let's see how AVL trees solves this problem and what does it mean by AVL tree. So AVL tree, self balancing binary tree, the full form is, I think based on the people who founded it, could be that. So it's called Adelson, Welski and Landis AVL trees. Okay, cool. How it works? Let's see. Okay. So let's see how AVL tree functions. So Kunal we know that you are saying that AVL tree is a self-balancing binary tree. Okay no problem. Sometimes we may insert some node in a tree and that will make that tree unbalanced. We know what unbalanced means and when tree is like oh Kunal you just inserted this node, tree has become unbalanced. Now don't worry Kunal, I'm an AVL tree so I will make the tree balanced automatically. So obviously if a tree has become unbalanced then to make it balanced you have to change the structure of the tree You have to move some nodes around to make the structure of the tree balanced pretty common sense Now the question is how do we do that? So what is the basic method? Via which the tree will adjust itself. What is the basic method? Let's see. So let's say you have a node Let's say this is a parent node this is a child node, this is tree number 1, this is tree number 2, this is tree number 3. Okay, so there are two methods using which we are going to form our algorithm. But two basic steps. First one is, if you want to, there's only two things you can do. Okay, for every node. So let's say you found a node. and you're like this node is making it unbalanced. For example, if you try to look for... you started adding it from here, let's say you started adding it from here, let me show you how it works. Okay, let me show you how it works. So, before moving forward, I'll just write down the algorithm for AVL tree. Then it will make more sense. Step one you have to do is insert normally. Insert normally node node n for example insert normally node n now Start from node n and find the node that makes the tree unbalanced So, you are saying Kunal start from the bottom up? Yes. Taking an example of the previous question, add the node normally, ok. Added the node normally. Start from this node n, work above. Is this node unbalanced? No, it's not. Is this node unbalanced? Yes, it is. Sorry, no, no, it's not. Is this node unbalanced? Yes, it is. So, Is this node unbalanced? No. No, this is not unbalanced. Okay, keep moving up. No, this is not unbalanced. Okay, keep moving up Yes, this is unbalanced. This node is unbalanced. So now we will solve this particular sub tree before moving more up That is AVL tree. For every sub tree, how you can solve it is for every sub tree, think only two things you can do Let's say we have this subtree so in this case in the bottom one this will be equal to p this will be equal to child this will be equal to tree one this will be equal to tree two and this will be equal to t3 make sense so only two operations you can perform parent child t1 t2 3 3 i showed you in the real world example how this is going to be related so you can check that out you can either rotate it on the right hand side or you can rotate it on the left hand side if I rotate it on the right hand side so this will go down, C will go up, C will go here, P will go down and P will obviously go on the right hand side of C because P is greater than C and in binary trees anything that is greater than the node goes on the right hand side. T3 on the right hand side, no problem. Now C has T1 on the left hand side, no problem. T2 was replaced by P. T2 is actually I know smaller than P because it was originally on the left hand side of P. So it will be on the left hand side of P. Similarly, this is left rotate. This is like the basic concept. Please note that the binary search tree property that all the elements on the left hand side has to be smaller, right hand side has to be bigger for every node is still holding true for this case. Originally T2 was on the left hand side of P, now also T2 is on the left hand side of P. Originally C was actually smaller than P, in the rotated one also C is smaller than P. Similarly you can do the left rotate also. if you want to do left rotate then okay p will come up c will go down t2 will go on the right hand side so on and so forth very simple these are the two basic formulas that we will use okay very simple so avial tree is not difficult it is a little confusing can be getting it can get a little confusing because there are so many moving components after this we will see four rules of how to apply these two methods you can apply these two methods in four ways. Okay? So, it's not difficult at all. It's just like there are too many components. There are two things like this, and then there are four rules. And then there's the balanced and unbalanced thing. So, it's not difficult at all. I hope this is clear. Very simple stuff. So, let's take an example. So, if I take this example over here, if I take this example, this one like we found the tree. So you know how it basically works. That start from the node n, find the one and bottom up and after that using one of the four rules rotate. Okay, that's it. What four rules? Let's see. four rules rule number one it's very simple um in the previous example let's say we had a parent is over here and let's say you have a child over here and that child has a grandchild over here g okay and then this has tree one and uh tree 2, tree 3 and tree 4. Let's say you have a situation like this. There are only four rules possible. Okay, now you will be like Kunal, how did you figure out this is the grandchild and the grandchild is let's say not on the right hand side. That is also one of the cases that we will cover. But the grandchild is actually in the line of where the element was added. So if your element was added over here. then this will be grandchild because it is in the line from the element added to the parent okay if the element was added you know somewhere over here then this would be grandchild because it's in the line to the parent I hope that is clear it's very simple stuff okay let's move forward So let's say we have one of these four cases. So in this case, imagine that the P point, let's say for example, these cases are for unbalanced binary trees, subtrees. So this P is where we're going to be rotating it. So in this case what we're going to do is, if we find a case like this, we're just going to right rotate. right rotate from p so c will come above p will go over here t4 will go over here then what t3 will go over here g will stay here t1 t2 make sense sounds good okay Case number two, let's say parent like this, you have child like this and let's say here you have T4 and let's say now you inserted something, there was a tree over here T3 and let's say you inserted an item over here then the item inserted in that lane the child of child is going to be the grandchild okay t3 t2 t1 these are sub trees t1 t2 t3 okay all right now what we're going to do is this is actually going to be the this one's first one is going to be the left left case so you have the child and grandchild both are on the left left side left left so Left left case here you can see that it's left right So this is left right case your motivation is to convert the tree in a single line this parent child grandchild Right convert it into a single line that should be your motivation so because then you will be able to rotate and make it balanced okay so here you can see it was for example in this case single line parent child grandchild okay similarly you can rotate but here you can see it is not in a single line it is zigzag so i'm going to first make it into a single line so to make it into a single line I start from the bottom and I will what I will do is I will put G over here I will do left rotate G sorry C left rotate C that will bring G above so it will make my tree something like this G will come over here and then child will come over here Tree 1, Tree 2, Tree 3. Now you can see it's in one single line. And is this not the same as this one, first one? So what is the case for first one? What do we do when we have a structure like the first one? We right rotate on P. Right rotate on P. After this, right rotate, T, same as 1. Very simple? Okay. Don't try to think about it. These are the only cases you can have. Then what other solution do you need? What other explanation do you need? Let's say parent, child, grandchild, T4 or I can say T1. T2, T3, T4. It is one single line. So I will just simply rotate It is right right case. So I will rotate it on the left hand side right right case Move it on the left hand side left rotate on P. P will go C will come above P will go here T1 will go over here. T2 will go over here. Okay? Because it has to be greater than P, greater than P. That is fine. G will be here. T4 will be here, T3 will be here. That's it. Balanced. Now you'll be like Kunal, how do you know that the individual trees T1, T2, T3, T4 are balanced? Because we are starting from bottom up. Okay? That's why. Right right case done. One more case left. right left case. This is again very simple. Let's say I have my parent over here, my child over here and my grandchild over here. Tree 1, tree 2, tree 3, tree 4. I have to make it in one single line. I will start from the bottom up. So this one I will see C. and I'm going to right rotate it, right rotate on C. This will become G and C will come over here, T4, T2, T1, T3. Now this is same as point number three. right same as point number three so i will do left rotate on p these are the only four cases why do we have these two extra cases because sometimes you get right left sometimes you get left right those are the only two possible explanations so you first make in a single line and then rotate it and how do you know that individual trees are balanced because we're starting from the bottom up that's the avl algorithm insert it normally start from the bottom node and find the node that makes it unbalanced from bottom up then do the one of the four rotations that's it very simple because that node made it unbalanced right that is why we are going to figure out the first tree that makes it unbalanced we're going to solve that tree so when the sub tree itself is not unbalanced the other tree oh yeah that's one more other point If the subtree itself, so we added one node, then we made sure that the first tree that it unbalances, we solve that. So this subtree we solved. So when the subtree is balanced, the above tree is also going to be fine balanced. If it is already balanced. Try to understand. While we are adding elements, we are making sure tree is balanced. So before I add an element, let's say 100 elements are in the AVL tree. We know that those 100 elements by definition of AVL tree, this is a very important point, I forgot about mentioning this, it's the intuition, the thing that will click. When you are trying to add, let's say you add 100 elements, okay, I know that 100 elements are added, 100 nodes are added in the tree, I know it's an AVL tree, so I know it is a balanced tree, because at every point of time it will make it balanced. Now I add one more node and I'm like, okay, this node made a sub tree, a part of this tree, for example, in this case, this this blue one this blue one this part it made it unbalanced so it will be like okay i added this one node it made this tree unbalanced so i will just solve this subtree i will make this subtree i will make this subtree balanced and when this subtree is balanced it is going to be fine because it's not going to affect the entire tree because the entirety is already balanced make sense sounds good okay so entire tree is already balanced that is established only solve the subtree that became unbalanced and if using that subtree other trees were unbalanced those will also be balanced because the subtree was unbalanced so it got balanced hence the all the other subtrees that were all the trees above it that were unbalanced because of it those are now also automatically solved okay Sounds good? We can take an example and see into a picture. Okay, so I got this example online from GeeksforGeeks and I didn't want to, you know, make it all dirty so this is looking much prettier. So here you can see they have a tree over here and the node values it says minus one plus one zero zero these are just differences in height so don't worry about that okay. We'll see it in the code when we do left heavy and right heavy like how to calculate it using a formula so when you see okay Kunal in these four cases, how are we going to write that in code? We'll see that in just a minute, don't worry. So, here you can see that this is the normal tree, okay, it is balanced. It's saying insert the value 14, okay, it inserted normally 14 in the left-hand 15 as you can see over here, it inserted 14 over here. No problem. Did this make it unbalanced? No, it didn't. Okay, move forward. Now, here it says insert 3, so 3 is inserted over here. No problem, 3 is inserted over here. But this 3 made it unbalanced. Which subtree did it make unbalanced? 4, 4, did it make 4 unbalanced? No. Did it make 5 unbalanced? No. Did it make 10 unbalanced? Yes. This is actually the same case that we had previously. So it's going to be like, okay, this is parent, child, grandchild. Parent, child, grandchild, tree 1, tree 2, tree 3. What is this case? parent child grandchild t1 t2 t3 t4 right rotate right rotate 10 done fixed i hope now it's clear now insert 45 uh in this example it will insert normally 45 over here over here no problem now this is making it what unbalanced is 40 unbalanced no is 35 unbalanced uh 1 minus 0 plus 1, no. Is 30 unbalanced? Yes, 30 is unbalanced. So, P, child, grandchild. This is right-right case. So, right-right case means left rotate. Right-right case, left rotate. How simple is that? How simple? Cool? Now here it's saying insert node 7. 7 will go over here, no problem. So 7 is making which balance, which sub-tree unbalanced? 6? No. 5? No. 10, is it making 10 unbalanced? Yes, it is making 10 unbalanced. Because this height is 2, this height is 0. So minus 2. So it is making it unbalanced. 0 minus 2. 0, this is 2. see 1 2 and 0 you know how it is 0 right height for every sub tree so height for this is because this is only one node 0 how height for this 5 is what 1 2 so 2 minus or 0 minus 2 if you're doing right minus left minus 2. so 10 is unbalanced so if 10 is unbalanced then this is p this is child and Is this going to be grandchild or this going to be grandchild? Grandchild is in the line of the number that is already added right now. 7 was added. So in the path of 7 to P, the one below child will be grandchild. This will be grandchild. So this is left right case. Left-right case. First left rotate child then right rotate P. Left rotate child right rotate P. So left rotate on 5, left rotate on 5 then right rotate on 10. Right rotate on 10. Not a problem at all. Very simple. Okay. Similarly now this case insert 15 15 is added over here. Okay. Is it making 16 unbalanced? No. 9 unbalanced? No. No, actually wait. Is it making 9 unbalanced? Yes, it is making 9 unbalanced because left height is 0, right height is? No, left height is no, nothing. And then the right height is? Here, 1. So it is actually 2. Yeah, 9 is unbalanced. So, P, child, grandchild. So, this is right-left case. So in right-left case, right rotate C, left rotate P. Right rotate on 6, 16. Yep. Then left rotate on 9. Yeah. tree is balanced. Cool? Using these examples, I hope you understand that when you find a tree that is unbalanced which is like this you know if you automatically solve this then whole tree is solved because originally whole tree was balanced as Original whole tree is balanced. This is the intuition behind it. This is where people get doubt. So I believe I cleared that doubt. Okay? Sounds good? Alright? Now let's code this. It's very simple. Okay? So before we move on to the code, let me talk about the important part, time complexity. Time complexity. Let's say we talk about for adding because that's a performance function we're performing. So time complexity. Because at all the times, 3 will be balanced. So it will be log of n. Okay? Log of n. Can you tell me the amount of time, the time complexity that the rotation is taking? Rotation is only at max two steps either left rotate, right rotate or something like that. So rotation is taking constant time because I'm only rotating the sub-tree that was affected and since that affected will be fixed then all the trees will be fixed automatically as I already told you because the original tree was balanced. and the rotation at max we're just doing two rotations at max that's what we're doing right in left right case or right left case we are doing two rotations in left left right right we are doing only one rotation to x maximum two rotations which is constant so total complexity comes out to be o of log n okay now we can code Alright, let's start with the coding part. You can check out the link to my code sample in the description below. That is going to be nice because then you can directly run the file on your browser. So I'm going to write tree to AVL create REPL. And what I'm going to do is I'm actually going to copy paste. In my data search algorithms in the last one, we did trees. So I'm just going to copy paste the binary search tree because we can use some of the functions. You know binary search tree create avl.java copy paste it. AVL, AVL, hide it for now and let me just double check because whenever you copy paste things can go a little wrong. So public class node, everything looks fine, node root, root fine. Insert, we will have to change a little bit so don't worry about that. Populate, populate with sorties, sorted is fine. populate with sorted is okay, display is okay, is empty okay, height okay, balanced is also okay. Good! So if you don't know what these functions are, I mean you obviously will because we just did you know the tutorial but this entire code I have not just copy pasted, we did every we wrote every single line of this code in the previous lecture. So please watch the previous lecture. You know it doesn't make sense I write the same thing in again and again in every lecture. So every single line I have explained in the previous lecture. Okay, now what do we need to do? So we are inserting normally, that is fine. But one thing we are changing is that we have to rotate for this node that we have just entered. So this node that we have just entered, let's say for root, and it's going to in the end when it goes down, down, down, you know how the insertion works, right? So it's going down, and in the previous example like it will go down, it will go down, it will go down then it will update it over here. So when it updates it over here, I have to call this node in let's say I have to do what I have to do rotate. So whatever you have just added, I will call a rotate on this node and this rotate is actually going to return the node itself which is the root. So we'll go up and up and up and up. So after rotating So after it is done rotating it will go up and up and up and it will rotate the root. Sorry, return the root. Okay. So that's the one thing we have to change over here. And now what I have to do is I have to create a rotate function. Okay. So let's see how we can do that. I'm going to turn off the AI feature. okay i hope the screen is visible the code can be found in the description below you can directly click on run and you can run the code that i'm writing so that's pretty cool the link for this can be found in the description just like every other link so private node rotate node node okay we have to rotate so no problem Here think about what is happening. Kunal why did you call rotate over here? So when you're adding your node in the end it's going to be like okay node is equal to the new node added then return which is going to rotate that node it's going to rotate this node and whenever you're trying to rotate and then it's going to it keeps on returning it like rotate on the nodes that I have called here in the previous part okay So even though it keeps on calling it, it will not execute because these will all be balanced. There only will be one node that is unbalanced. So how do we make that check? I hope this is clear. You can run it on pen and paper. You know recursion very good now. So I hope this is clear. Please don't be confused on Kunal. Why are you returning this node? I am in the end returning the in the end, it will return the root node only. Okay. for every function call first function call it is going to return the node and it will partially to rotate rotate itself is returning the node only so in reality it is just fixing the structure of the tree and then rotating the node itself that is it private node rotate so four cases so one thing i have to i want you to know is that in this case when the height of if you are on parent of if you're on this node if the height of left minus the height of right is greater than one it basically means that it is left heavy because left has more height very simple so you will just do right rotate so left heavy is two cases which is left left and left right case so in left right case you can see let me just write it down first so if height of node.left minus height of node.right is greater than 1, then I know that it is left heavy and now left heavy has two cases. So if I take this child over here, if the height of node.left, p.left, dot left, if the height of this tree and this tree is positive it means that it is left left case because this is greater so left left case so left left case is this height will be more this height will be less that is left left case as you can see on the screen so if height of node dot left dot left and node dot left dot right see the thing is don't try to think how these things are happening when it is right in front of your eyes this is why in linked list many people get confused in linked list you get questions like okay every three items you have to reverse or whatever so when you're debugging it and writing it down and it is the diagram is telling you where all the arrows will go then why do you need to think there are two types of problem one type of problem is in which you have to think other type of problems like this are the visual problems the diagram is telling me what to do there is no intuition behind it okay whatever the diagram is saying i'm doing So if height of node.left.left is minus height of node.left.right is actually positive. In that case, I know it is left-left case. What is the answer in left-left case? Right rotate on P. P is node. So right rotate. right rotate i'll create later on node similarly if this is negative meaning this height is greater this height is smaller means it is left right case and left right case we do what left rotate on child means node.left so we do left rotate on node.left node.left is going to be equal to left rotate node.left and then return right rotate on the original node right rotate on the original node no problem no problem at all it will actually be equal to if this is negative makes sense very simple in recursion you will understand in recursion i told you if the no if the return type is node then you're going to be returning node so if you're trying to fix it for this node if you're trying to fix it then this function is actually should also return the type node because this function is accepting node that is why it's returning node otherwise it will give you error it will not even let you you know compile or whatever So if you debug it, you can debug it on pen and paper, I showed you the entire thing. When I add it in over here, it's going to say like, okay, new node added, return node. So it's going to call the node for this one, call the rotate for this one. For this one, it will not execute because none of the conditions will satisfy. Hence, it will come out of here. And when it will come out of here, it will be like, okay, either over here or over here. So if it comes out over here, then load.left will be equal to whatever it was so node.left will be equal to whatever it was unchanged and then it will be okay i'm not going to call rotate for this call rotate for this it's going to say okay this does not satisfy the condition so no worries i will just return the node normally itself return the node normally itself and this will either be returned from here or here so it will be like node.right node.left means c.left So for this node in recursion, node.left will be equal to this only. So remaining unchanged, as you can see, remaining unchanged. I told you I won't show you the pen and paper stuff, but I'm still doing, okay? So now this for p, it will be like, okay, rotate it. So it's going to be like, okay, is this unbalanced? It's going to be like, yeah. Then it will rotate it normally, and then whatever the node is supposed to be over here, which is going to be child, it is going to return that. And where it will return? From where it was called. So return. the child that we have over here and it will be called from here, so it will return over here so this node.left will now be equal to child and this tree will be rotated okay, cool use the pen and paper, you will understand this is very simple stuff because we have done such questions before and I showed you the problem by running it also copy paste now, write heavy write heavy is when this is actually less than minus one and write write case will be what note dot note dot write write write case let's check the write write case right right case okay node dot right dot left and node dot right dot right the difference between this and this should be negative because this is small this is big so left minus right should be negative so node dot right dot left node dot right dot right should be negative that will be right and in right right case i do left rotate on the note left rotate on the note similarly node.right.left node.right.right should be positive should be positive in this case I am going to say right rotate on child child is node.right so right rotate that is going to be right right rotate node dot right and then left rotate on the node in the end just return the node so even though this is being called for every single path as we move above it will only run once because this condition will only be satisfied once in other cases just return the node itself so in reality this function that you're saying canal you were returning node previously and now you're returning it in a function. I'm still returning the node only but I'm performing some functions. In one of the cases where the tree is unbalanced, it will adjust the size, sorry adjust the structure, return the correct node. For everything else, it will return the node only. Doing nothing, just returning the node only. What we were doing previously. Okay now we have to create left rotate and right rotate. Okay, left rotate and right rotate. Let's see how we can do that. Okay, now right rotate and left rotate. Very simple stuff. So we have already done the overwhelming complex part. All the test cases I showed you, the run through of the code as well. You can also debug yourself. I've showed you how to put debug pointer into it but I showed you like what the return node is, what the calling the function in the node return is. In the reality, it's only returning the node itself like previously in the previous binary search tree lecture how it was returning the node in insert over here. but now it's only going to rotate it in one single case and this if condition will only be valid for one single case because it will have that one case that will be subtree that is rotated sorry unbalanced and we're doing uh right rotate left rotate now so we already have this thing over here so ideally you know think about when we were doing linked list the diagram was telling us what to do and we were just coding that i will do the same thing i am shutting off my brain now because my brain it's not required now because whatever the diagram is telling me i will code it i don't even need to understand anything because it's not worth it because we've already understood how right rotate work how ref rotate works now the diagram is telling me what to do so i will just do it understanding part is done okay we did that in theory so think about what all things we don't need to touch uh t3 is not going to be changed Don't touch T3. T1 is not going to be changed. Don't touch T1. T2 will be changed. So P, just gonna write it down. Right rotate across node P. Node child is equal to P dot left. Node C is equal to P dot left, no problem. Node T is equal to P dot left dot right. now or c dot right t is equal to c dot right t is equal to c dot right okay now right rotate um c dot left will become p and p dot left sorry c dot right will become p c dot right will become p and p.left will become t. Done. That's it. One last thing you have to do is update the heights now because c was added above, p was coming down. So, update the height. p.height is equal to math.max Cool? So new height is going to be equal to maximum of left and right plus 1 for this. We have done the height formula before, so don't worry about that. Similarly, c dot height will be equal to mat dot max c dot Left, c dot right, plus 1. Now, what is the new node? New node is c. Return c. I am telling it again and again. The only intuition problem that you are going to have, I know you are having this doubt, is over in this line 43. Please try to understand that in original format, it was return node. Right now also, it is return node only. See. it is doing nothing but return node but for that one case in which the sub tree is unbalanced it will balance in then return the node so new node will be returned like c and that will be added over here so it will return then wherever it will be returned from where it was called which is somewhere over here and then that new child will be equal to the node.left of the above the one above that one as i showed you in the example right now when i was writing this code. Okay, it was very simple. It is don't overthink it. It's very simple. I shared it like three four times. I won't share it again now because then it will get cringy. Anyway, So I told you where you might get doubt. I solved that doubt now we can move forward. Okay, now left rotate. Left rotate is very simple. Copy paste. You can still you can just do the use the you know this thing over here. okay so again no need to think i will take in this example only it's saying c i will have node c over here left rotate so node p is going to be equal to c dot right node p is going to be equal to c dot right and what will remain unchanged um p t3 will remain unchanged t1 will remain unchanged, t2 will be changed. So, c dot right or p dot left, p dot left. Okay? Okay? So, here we have p dot left is equal to my t. And now, how to change it? So, if I'm changing it left rotate, then p dot left becomes c. No problem at all and c.right becomes t. No problem. Similarly, p.height and c.height. Looks good. Now new node is equal to p so I will return p. That's it. AVL tree done. Very cool stuff. Simple, right? now you can run this let's try running it okay so here in the main function i can write my code i can say avl tree is equal to new avl tree and let's say i insert i'm trying to insert you know ascending order so in binary search state we'll just make a line like i showed in the previous one uh and i is equal to 0 i is less than let's say 1000 and i plus plus I'm going to say tree.insert . If I check the height of this in a binary search tree which is not balancing, it will be like okay right right right right right right right right right right right right right it will give 1000. So system.out.println . This should give log of 1000. Let's see. Okay so log of around 1000 so it should give me one plus log 1000. so log 1000 2 plus 1 3 3 I inserted thousand elements in a tree in binary search tree height would be 1 1 1 1 you know just go right right right right right right right as I showed in the previous example this example but now no it's balancing it that is why always height will be log of n simple very easy very nice self-balancing binary tree is a piece of cake done okay so lastly i'd say you can take a screenshot share it on social media hashtag dsa with kunal join the learning public initiative i'll make tutorials uh much faster at least four videos you can accept expect in a month and as the next one's recorded as well i have to edit those but i wanted to make sure we do this one first before jumping on to the questions because These are some of the concepts that are being used. So, few things. Number one, like. Number two, comment. Number three... take a screenshot and share with hashtag DSA with Kunal and that's it. These three things you need to do. For follow-ups, the assignments and everything notes and the code link can be found in the description below. So you can directly use the URL that I will share with you in the description below and you can just run it after signing up. You can run it and you can run the code that I'm writing, make it, modify it, fork it, do whatever you want and it's very nice because you can do it right from your browser itself like I'm doing. for teaching it makes it much more convenient so yeah like comment if you comment more people will view it and more views will get and more people will learn from these free courses and more motivation i'll get to make such videos so like and comment it at least something you can do and share you can do it if you don't want to that's fine but like and comment please do it if you've watched it till now please like and comment i cannot stress this enough and assignments everything all the links code description below and i'll see you in the next one have a great day bye if you have any doubts comment section

But in this video we're doing the second video of the Trees lecture. We're talking about Self-balancing binary trees. So in this video I'm going to talk about AVL trees and then in next videos we'll talk about like some other types of trees like Fenwick binary index trees, segment trees, red and black trees and then we'll do some interview questions as well for trees which is obviously very important you know we did binary search then we did binary search interview, we did link list links list interview, we did recursion then recursion interview. So for trees also we're doing theory part and implementation part and in the end we'll do some very important questions part like how to identify patterns, how to solve any tree question.

Okay, but in this video we're talking about self-balancing binary tree. No need to worry about if you don't know what a self-balancing binary tree is. Only prerequisite is all the videos we have done till now and the trees video specifically that I did previously.

So I'm going to start with a challenge like what are the challenges with normal binary trees and then we'll talk about okay how balancing binary trees solve these challenges and in this video we're going to look at a very popular self-balancing binary tree obviously we'll look other ones in the later on but this is very important hence i'm making a dedicated video on this so we'll look at avl trees full form everything i'll tell you later avl trees one thing i want you to notice is sometimes people get intimidated by avl oh it's very difficult you know it's very confusing it is not confusing not confusing. Then what it is Kunal? It is actually, it has a lot of moving parts. Lot of things are happening. So with avial trees, lot of things will happen.

But all of those things are very simple. Just the quantity is a little bit, it's not that high, just 4 test cases. Okay, there are only 4 cases, but still some people feel like okay this is too much. but i will actually teach you so if you're looking at it for any topic okay not just tree even when you do dynamic programming or when all the previous topics i've done in the past when you take a concept and you try to memorize that concept in the terms of oh this concept has four cases this concept has six cases this concept has 10 cases you try to memorize that without understanding what are these why are we having these many cases then it becomes overwhelming and difficult to you then you feel like it's difficult but i will make it clear to you why we only have four cases what is the significance of each case the thought process behind it when they created avl why did they only make four cases or whatever okay let's get started forget about avl right now let's just talk about binary trees normal binary trees so if i talk about a normal binary binary search tree in the previous video we have already learned how normal binary trees functions okay so let's say i have a 10 over here and now i'm saying hey kunal insert 5 into it okay 5 is smaller than 10 5 will go over here i've already covered this okay how binary search tree functions so if you are not understanding this please watch tree tutorial number one there's a com there's a tree playlist on my channel now insert 15 okay 15 will go over here now insert 10 uh sorry 10 is already there now insert 12. so 12 is greater than 10, so right hand side less than 15, left hand side so on and so forth you get the idea so the idea is that the maximum height, let's say it's going to be log of n, which is n is the total number of nodes so at any point of time we have already covered in the past how the insertion and your delete and your, you know, when you delete or when you try to search an item it will take log of n time very good, no problem, okay But the problem arises, let's say you are saying Kunal insert 5 in a binary search tree Ok, no problem, I have inserted 5 Now Kunal insert 7 into it Ok, so 7 is greater than 5, it will go on the right hand side, no problem Kunal insert 9 into it Ok, 9 is greater than 5, so it will go on the right hand side 9 is also greater than 7, it will again go on the right hand side Kunal please insert 11 into it Ok, 11 I will insert over here Kunal please insert 13 into it Ok So, can you see what is happening?

If I want to search 13, it will have to traverse it n number of times. So instead of log n. it is now taking n complexity which is wrong whole point of binary trees is now destroyed whole point is destroyed this is the problem with binary search trees because a chain can form like this even if you have something like this Still, there is a chain, right? Not perfect log n is the answer.

Make sense? That is the problem and that is what we are trying to solve. So, how do we define this problem? Okay, now defining the problem. Kunal, it looks like a problem when I am looking at it from my eyes, but how do you define it in a definition?

Define the problem. No problem, we can define it. So, the problem is this, that for any tree, for any tree that you have, let's say we have this tree, something like that, okay? Let's say we have this tree. Now here you can see that the difference of height of left subtree and right subtree for every single node is going to be either plus 1 or minus 1, like less than equal to 1 for example.

So here you can see what is the height. Height is the number of edges from the node to the bottom leaf. So for every single node, let's say we're talking about this node first.

For every single node, think about the definition. For every single node, the height of the left and the right tree should not have a difference of more than 1. Okay, what is the height of this tree over here? What is the height of this tree?

This tree's height is 2. What is the height of this one? 1. 2 minus 1 is equal to 1. Correct. So, this difference should only be less than or equal to 1. So, 1 or 0. And if you do, let's say, for example, if I say, for every node height of left, minus height of right can be equal to minus 1 plus 1 or 0 only.

In this case, it is 1. But if you have something like this, in this case, this height is 1, height is 2 for this tree or this tree. 1 minus 2 minus 1 that's fine no problem okay and this you have to do for every single node for every single node you have to do this so now let's see i did it for this node right now i will do the same for this node so again take this tree and this tree here the height is 1 here the height is 0 differences 1 minus 0, 1. Yeah, sure. This is also balanced. Now again do for this node. For this node, 0 and so this is just 1 so I will just leave it.

For this node, this is itself, it has no left or right children so I'll leave it and for this one, it's again just 1 as you can see over here. So pretty simple stuff, okay? So as you can see for every single node, I'm repeating it again and again, for every single node the left and right tree height can only be minus 1 plus 1 or 0. Let me take an example of a tree which is not balanced.

This is known as balance tree by the way. Okay if I write the definition down, for every node Did my pen run out of ink? not working so actually this is the definition only what formula i have just written above for every node in the tree the difference in height of left and right sub tree of that node for every node should be less than equal to one or yeah should be less than equal to one cool so either one or zero now let's take a look in example and that that is a balanced tree that is called a balanced tree let's take a look at a tree which is not balanced so if i have this tree right here, okay, like this.

This is okay for now, something like this. Fine for now, okay. Let's add in one more, okay. Now, how do we determine Kunal, whether this is a balanced tree or not? Look at the definition.

The definition says for every node in the tree the difference of the left and right sub-tree height should be less than equal to 1. Okay, then I will start checking from here. What is the height of left and right? So, height of this is 1, 2, 3 and height of this is 1. So, 3 minus 1 is equal to 2, not balanced.

Not balanced. Simple? That is basically balanced tree and unbalanced tree. I hope that is clear. Okay.

In the previous example also, this is also unbalanced tree. You know, this one. Why? Because the height of the left tree is 1, right tree, left tree is 0, right tree is 1, 2, 3. So 0-3-3. Not good.

Difference in height is 3 here. It's minus 3. Okay, very simple stuff. Cool. Now moving forward how to solve this problem solution Solution is self balancing binary tree. For example, one of those is AVL.

Self balancing binary tree, now you understand what was the problem and what problem self balancing binary tree is trying to solve. So when you have a tree that is unbalanced, Let's say you're adding something adding something adding something and the tree becomes unbalanced self balancing binary We'll be like, okay. Don't worry. You keep adding into the tree as you wish I will restructure the tree in some way that it will always be balanced and what is balanced You already know the definition that is what self balancing binary is.

Don't worry about how it's working Okay, just think about what it's doing for now. We will obviously look into the entire code base entire algorithm, all the theory, everything we will cover in this video. So don't worry about that. Try to focus on what this problem it is solving. What is meaning by self-balancing?

Self-balancing means you just keep inserting in it and we will apply some algorithm that whenever you insert an item and that insertion makes the tree unbalanced, it will be like okay Kunal just added 20 in the tree, a node with value of 20 and it has made my tree unbalanced. No problem Kunal, just add it as you want. and normally I will restructure the tree in such a way that it will become balanced For example, this is balanced tree It's the same tree as previously So it's going to be like, Kunal right now this is balanced, no problem Kunal is going to be like, okay I will add one more node over here.

The tree is going to be like, oh now you added one more node, now this tree is unbalanced. So don't worry. Add your node where it's supposed to go. I will then restructure the tree and balance it. How we are going to balance it, we will figure out later.

Okay? Sounds good? Let's move forward. So that is basically what self-balancing binary tree is.

And one of those trees is called AVL tree. So let's see how AVL trees solves this problem and what does it mean by AVL tree. So AVL tree, self balancing binary tree, the full form is, I think based on the people who founded it, could be that.

So it's called Adelson, Welski and Landis AVL trees. Okay, cool. How it works?

Let's see. Okay. So let's see how AVL tree functions.

So Kunal we know that you are saying that AVL tree is a self-balancing binary tree. Okay no problem. Sometimes we may insert some node in a tree and that will make that tree unbalanced. We know what unbalanced means and when tree is like oh Kunal you just inserted this node, tree has become unbalanced. Now don't worry Kunal, I'm an AVL tree so I will make the tree balanced automatically.

So obviously if a tree has become unbalanced then to make it balanced you have to change the structure of the tree You have to move some nodes around to make the structure of the tree balanced pretty common sense Now the question is how do we do that? So what is the basic method? Via which the tree will adjust itself.

What is the basic method? Let's see. So let's say you have a node Let's say this is a parent node this is a child node, this is tree number 1, this is tree number 2, this is tree number 3. Okay, so there are two methods using which we are going to form our algorithm. But two basic steps.

First one is, if you want to, there's only two things you can do. Okay, for every node. So let's say you found a node. and you're like this node is making it unbalanced. For example, if you try to look for...

you started adding it from here, let's say you started adding it from here, let me show you how it works. Okay, let me show you how it works. So, before moving forward, I'll just write down the algorithm for AVL tree. Then it will make more sense.

Step one you have to do is insert normally. Insert normally node node n for example insert normally node n now Start from node n and find the node that makes the tree unbalanced So, you are saying Kunal start from the bottom up? Yes. Taking an example of the previous question, add the node normally, ok. Added the node normally.

Start from this node n, work above. Is this node unbalanced? No, it's not.

Is this node unbalanced? Yes, it is. Sorry, no, no, it's not. Is this node unbalanced? Yes, it is.

So, Is this node unbalanced? No. No, this is not unbalanced.

Okay, keep moving up. No, this is not unbalanced. Okay, keep moving up Yes, this is unbalanced. This node is unbalanced. So now we will solve this particular sub tree before moving more up That is AVL tree.

For every sub tree, how you can solve it is for every sub tree, think only two things you can do Let's say we have this subtree so in this case in the bottom one this will be equal to p this will be equal to child this will be equal to tree one this will be equal to tree two and this will be equal to t3 make sense so only two operations you can perform parent child t1 t2 3 3 i showed you in the real world example how this is going to be related so you can check that out you can either rotate it on the right hand side or you can rotate it on the left hand side if I rotate it on the right hand side so this will go down, C will go up, C will go here, P will go down and P will obviously go on the right hand side of C because P is greater than C and in binary trees anything that is greater than the node goes on the right hand side. T3 on the right hand side, no problem. Now C has T1 on the left hand side, no problem.

T2 was replaced by P. T2 is actually I know smaller than P because it was originally on the left hand side of P. So it will be on the left hand side of P.

Similarly, this is left rotate. This is like the basic concept. Please note that the binary search tree property that all the elements on the left hand side has to be smaller, right hand side has to be bigger for every node is still holding true for this case. Originally T2 was on the left hand side of P, now also T2 is on the left hand side of P.

Originally C was actually smaller than P, in the rotated one also C is smaller than P. Similarly you can do the left rotate also. if you want to do left rotate then okay p will come up c will go down t2 will go on the right hand side so on and so forth very simple these are the two basic formulas that we will use okay very simple so avial tree is not difficult it is a little confusing can be getting it can get a little confusing because there are so many moving components after this we will see four rules of how to apply these two methods you can apply these two methods in four ways.

Okay? So, it's not difficult at all. It's just like there are too many components. There are two things like this, and then there are four rules.

And then there's the balanced and unbalanced thing. So, it's not difficult at all. I hope this is clear. Very simple stuff.

So, let's take an example. So, if I take this example over here, if I take this example, this one like we found the tree. So you know how it basically works.

That start from the node n, find the one and bottom up and after that using one of the four rules rotate. Okay, that's it. What four rules? Let's see. four rules rule number one it's very simple um in the previous example let's say we had a parent is over here and let's say you have a child over here and that child has a grandchild over here g okay and then this has tree one and uh tree 2, tree 3 and tree 4. Let's say you have a situation like this.

There are only four rules possible. Okay, now you will be like Kunal, how did you figure out this is the grandchild and the grandchild is let's say not on the right hand side. That is also one of the cases that we will cover. But the grandchild is actually in the line of where the element was added. So if your element was added over here.

then this will be grandchild because it is in the line from the element added to the parent okay if the element was added you know somewhere over here then this would be grandchild because it's in the line to the parent I hope that is clear it's very simple stuff okay let's move forward So let's say we have one of these four cases. So in this case, imagine that the P point, let's say for example, these cases are for unbalanced binary trees, subtrees. So this P is where we're going to be rotating it. So in this case what we're going to do is, if we find a case like this, we're just going to right rotate.

right rotate from p so c will come above p will go over here t4 will go over here then what t3 will go over here g will stay here t1 t2 make sense sounds good okay Case number two, let's say parent like this, you have child like this and let's say here you have T4 and let's say now you inserted something, there was a tree over here T3 and let's say you inserted an item over here then the item inserted in that lane the child of child is going to be the grandchild okay t3 t2 t1 these are sub trees t1 t2 t3 okay all right now what we're going to do is this is actually going to be the this one's first one is going to be the left left case so you have the child and grandchild both are on the left left side left left so Left left case here you can see that it's left right So this is left right case your motivation is to convert the tree in a single line this parent child grandchild Right convert it into a single line that should be your motivation so because then you will be able to rotate and make it balanced okay so here you can see it was for example in this case single line parent child grandchild okay similarly you can rotate but here you can see it is not in a single line it is zigzag so i'm going to first make it into a single line so to make it into a single line I start from the bottom and I will what I will do is I will put G over here I will do left rotate G sorry C left rotate C that will bring G above so it will make my tree something like this G will come over here and then child will come over here Tree 1, Tree 2, Tree 3. Now you can see it's in one single line. And is this not the same as this one, first one? So what is the case for first one?

What do we do when we have a structure like the first one? We right rotate on P. Right rotate on P. After this, right rotate, T, same as 1. Very simple? Okay.

Don't try to think about it. These are the only cases you can have. Then what other solution do you need? What other explanation do you need?

Let's say parent, child, grandchild, T4 or I can say T1. T2, T3, T4. It is one single line.

So I will just simply rotate It is right right case. So I will rotate it on the left hand side right right case Move it on the left hand side left rotate on P. P will go C will come above P will go here T1 will go over here. T2 will go over here. Okay?

Because it has to be greater than P, greater than P. That is fine. G will be here. T4 will be here, T3 will be here.

That's it. Balanced. Now you'll be like Kunal, how do you know that the individual trees T1, T2, T3, T4 are balanced? Because we are starting from bottom up. Okay?

That's why. Right right case done. One more case left.

right left case. This is again very simple. Let's say I have my parent over here, my child over here and my grandchild over here.

Tree 1, tree 2, tree 3, tree 4. I have to make it in one single line. I will start from the bottom up. So this one I will see C. and I'm going to right rotate it, right rotate on C. This will become G and C will come over here, T4, T2, T1, T3.

Now this is same as point number three. right same as point number three so i will do left rotate on p these are the only four cases why do we have these two extra cases because sometimes you get right left sometimes you get left right those are the only two possible explanations so you first make in a single line and then rotate it and how do you know that individual trees are balanced because we're starting from the bottom up that's the avl algorithm insert it normally start from the bottom node and find the node that makes it unbalanced from bottom up then do the one of the four rotations that's it very simple because that node made it unbalanced right that is why we are going to figure out the first tree that makes it unbalanced we're going to solve that tree so when the sub tree itself is not unbalanced the other tree oh yeah that's one more other point If the subtree itself, so we added one node, then we made sure that the first tree that it unbalances, we solve that. So this subtree we solved. So when the subtree is balanced, the above tree is also going to be fine balanced.

If it is already balanced. Try to understand. While we are adding elements, we are making sure tree is balanced.

So before I add an element, let's say 100 elements are in the AVL tree. We know that those 100 elements by definition of AVL tree, this is a very important point, I forgot about mentioning this, it's the intuition, the thing that will click. When you are trying to add, let's say you add 100 elements, okay, I know that 100 elements are added, 100 nodes are added in the tree, I know it's an AVL tree, so I know it is a balanced tree, because at every point of time it will make it balanced. Now I add one more node and I'm like, okay, this node made a sub tree, a part of this tree, for example, in this case, this this blue one this blue one this part it made it unbalanced so it will be like okay i added this one node it made this tree unbalanced so i will just solve this subtree i will make this subtree i will make this subtree balanced and when this subtree is balanced it is going to be fine because it's not going to affect the entire tree because the entirety is already balanced make sense sounds good okay so entire tree is already balanced that is established only solve the subtree that became unbalanced and if using that subtree other trees were unbalanced those will also be balanced because the subtree was unbalanced so it got balanced hence the all the other subtrees that were all the trees above it that were unbalanced because of it those are now also automatically solved okay Sounds good? We can take an example and see into a picture.

Okay, so I got this example online from GeeksforGeeks and I didn't want to, you know, make it all dirty so this is looking much prettier. So here you can see they have a tree over here and the node values it says minus one plus one zero zero these are just differences in height so don't worry about that okay. We'll see it in the code when we do left heavy and right heavy like how to calculate it using a formula so when you see okay Kunal in these four cases, how are we going to write that in code? We'll see that in just a minute, don't worry. So, here you can see that this is the normal tree, okay, it is balanced.

It's saying insert the value 14, okay, it inserted normally 14 in the left-hand 15 as you can see over here, it inserted 14 over here. No problem. Did this make it unbalanced? No, it didn't.

Okay, move forward. Now, here it says insert 3, so 3 is inserted over here. No problem, 3 is inserted over here. But this 3 made it unbalanced. Which subtree did it make unbalanced?

4, 4, did it make 4 unbalanced? No. Did it make 5 unbalanced? No.

Did it make 10 unbalanced? Yes. This is actually the same case that we had previously. So it's going to be like, okay, this is parent, child, grandchild. Parent, child, grandchild, tree 1, tree 2, tree 3. What is this case?

parent child grandchild t1 t2 t3 t4 right rotate right rotate 10 done fixed i hope now it's clear now insert 45 uh in this example it will insert normally 45 over here over here no problem now this is making it what unbalanced is 40 unbalanced no is 35 unbalanced uh 1 minus 0 plus 1, no. Is 30 unbalanced? Yes, 30 is unbalanced. So, P, child, grandchild.

This is right-right case. So, right-right case means left rotate. Right-right case, left rotate.

How simple is that? How simple? Cool? Now here it's saying insert node 7. 7 will go over here, no problem. So 7 is making which balance, which sub-tree unbalanced?

6? No. 5? No. 10, is it making 10 unbalanced?

Yes, it is making 10 unbalanced. Because this height is 2, this height is 0. So minus 2. So it is making it unbalanced. 0 minus 2. 0, this is 2. see 1 2 and 0 you know how it is 0 right height for every sub tree so height for this is because this is only one node 0 how height for this 5 is what 1 2 so 2 minus or 0 minus 2 if you're doing right minus left minus 2. so 10 is unbalanced so if 10 is unbalanced then this is p this is child and Is this going to be grandchild or this going to be grandchild?

Grandchild is in the line of the number that is already added right now. 7 was added. So in the path of 7 to P, the one below child will be grandchild. This will be grandchild. So this is left right case.

Left-right case. First left rotate child then right rotate P. Left rotate child right rotate P.

So left rotate on 5, left rotate on 5 then right rotate on 10. Right rotate on 10. Not a problem at all. Very simple. Okay.

Similarly now this case insert 15 15 is added over here. Okay. Is it making 16 unbalanced?

No. 9 unbalanced? No. No, actually wait. Is it making 9 unbalanced?

Yes, it is making 9 unbalanced because left height is 0, right height is? No, left height is no, nothing. And then the right height is?

Here, 1. So it is actually 2. Yeah, 9 is unbalanced. So, P, child, grandchild. So, this is right-left case.

So in right-left case, right rotate C, left rotate P. Right rotate on 6, 16. Yep. Then left rotate on 9. Yeah.

tree is balanced. Cool? Using these examples, I hope you understand that when you find a tree that is unbalanced which is like this you know if you automatically solve this then whole tree is solved because originally whole tree was balanced as Original whole tree is balanced. This is the intuition behind it.

This is where people get doubt. So I believe I cleared that doubt. Okay? Sounds good? Alright?

Now let's code this. It's very simple. Okay?

So before we move on to the code, let me talk about the important part, time complexity. Time complexity. Let's say we talk about for adding because that's a performance function we're performing.

So time complexity. Because at all the times, 3 will be balanced. So it will be log of n.

Okay? Log of n. Can you tell me the amount of time, the time complexity that the rotation is taking?

Rotation is only at max two steps either left rotate, right rotate or something like that. So rotation is taking constant time because I'm only rotating the sub-tree that was affected and since that affected will be fixed then all the trees will be fixed automatically as I already told you because the original tree was balanced. and the rotation at max we're just doing two rotations at max that's what we're doing right in left right case or right left case we are doing two rotations in left left right right we are doing only one rotation to x maximum two rotations which is constant so total complexity comes out to be o of log n okay now we can code Alright, let's start with the coding part. You can check out the link to my code sample in the description below.

That is going to be nice because then you can directly run the file on your browser. So I'm going to write tree to AVL create REPL. And what I'm going to do is I'm actually going to copy paste. In my data search algorithms in the last one, we did trees. So I'm just going to copy paste the binary search tree because we can use some of the functions.

You know binary search tree create avl.java copy paste it. AVL, AVL, hide it for now and let me just double check because whenever you copy paste things can go a little wrong. So public class node, everything looks fine, node root, root fine.

Insert, we will have to change a little bit so don't worry about that. Populate, populate with sorties, sorted is fine. populate with sorted is okay, display is okay, is empty okay, height okay, balanced is also okay.

Good! So if you don't know what these functions are, I mean you obviously will because we just did you know the tutorial but this entire code I have not just copy pasted, we did every we wrote every single line of this code in the previous lecture. So please watch the previous lecture. You know it doesn't make sense I write the same thing in again and again in every lecture.

So every single line I have explained in the previous lecture. Okay, now what do we need to do? So we are inserting normally, that is fine.

But one thing we are changing is that we have to rotate for this node that we have just entered. So this node that we have just entered, let's say for root, and it's going to in the end when it goes down, down, down, you know how the insertion works, right? So it's going down, and in the previous example like it will go down, it will go down, it will go down then it will update it over here. So when it updates it over here, I have to call this node in let's say I have to do what I have to do rotate.

So whatever you have just added, I will call a rotate on this node and this rotate is actually going to return the node itself which is the root. So we'll go up and up and up and up. So after rotating So after it is done rotating it will go up and up and up and it will rotate the root.

Sorry, return the root. Okay. So that's the one thing we have to change over here. And now what I have to do is I have to create a rotate function.

Okay. So let's see how we can do that. I'm going to turn off the AI feature. okay i hope the screen is visible the code can be found in the description below you can directly click on run and you can run the code that i'm writing so that's pretty cool the link for this can be found in the description just like every other link so private node rotate node node okay we have to rotate so no problem Here think about what is happening. Kunal why did you call rotate over here?

So when you're adding your node in the end it's going to be like okay node is equal to the new node added then return which is going to rotate that node it's going to rotate this node and whenever you're trying to rotate and then it's going to it keeps on returning it like rotate on the nodes that I have called here in the previous part okay So even though it keeps on calling it, it will not execute because these will all be balanced. There only will be one node that is unbalanced. So how do we make that check?

I hope this is clear. You can run it on pen and paper. You know recursion very good now. So I hope this is clear.

Please don't be confused on Kunal. Why are you returning this node? I am in the end returning the in the end, it will return the root node only.

Okay. for every function call first function call it is going to return the node and it will partially to rotate rotate itself is returning the node only so in reality it is just fixing the structure of the tree and then rotating the node itself that is it private node rotate so four cases so one thing i have to i want you to know is that in this case when the height of if you are on parent of if you're on this node if the height of left minus the height of right is greater than one it basically means that it is left heavy because left has more height very simple so you will just do right rotate so left heavy is two cases which is left left and left right case so in left right case you can see let me just write it down first so if height of node.left minus height of node.right is greater than 1, then I know that it is left heavy and now left heavy has two cases. So if I take this child over here, if the height of node.left, p.left, dot left, if the height of this tree and this tree is positive it means that it is left left case because this is greater so left left case so left left case is this height will be more this height will be less that is left left case as you can see on the screen so if height of node dot left dot left and node dot left dot right see the thing is don't try to think how these things are happening when it is right in front of your eyes this is why in linked list many people get confused in linked list you get questions like okay every three items you have to reverse or whatever so when you're debugging it and writing it down and it is the diagram is telling you where all the arrows will go then why do you need to think there are two types of problem one type of problem is in which you have to think other type of problems like this are the visual problems the diagram is telling me what to do there is no intuition behind it okay whatever the diagram is saying i'm doing So if height of node.left.left is minus height of node.left.right is actually positive.

In that case, I know it is left-left case. What is the answer in left-left case? Right rotate on P.

P is node. So right rotate. right rotate i'll create later on node similarly if this is negative meaning this height is greater this height is smaller means it is left right case and left right case we do what left rotate on child means node.left so we do left rotate on node.left node.left is going to be equal to left rotate node.left and then return right rotate on the original node right rotate on the original node no problem no problem at all it will actually be equal to if this is negative makes sense very simple in recursion you will understand in recursion i told you if the no if the return type is node then you're going to be returning node so if you're trying to fix it for this node if you're trying to fix it then this function is actually should also return the type node because this function is accepting node that is why it's returning node otherwise it will give you error it will not even let you you know compile or whatever So if you debug it, you can debug it on pen and paper, I showed you the entire thing. When I add it in over here, it's going to say like, okay, new node added, return node.

So it's going to call the node for this one, call the rotate for this one. For this one, it will not execute because none of the conditions will satisfy. Hence, it will come out of here. And when it will come out of here, it will be like, okay, either over here or over here. So if it comes out over here, then load.left will be equal to whatever it was so node.left will be equal to whatever it was unchanged and then it will be okay i'm not going to call rotate for this call rotate for this it's going to say okay this does not satisfy the condition so no worries i will just return the node normally itself return the node normally itself and this will either be returned from here or here so it will be like node.right node.left means c.left So for this node in recursion, node.left will be equal to this only.

So remaining unchanged, as you can see, remaining unchanged. I told you I won't show you the pen and paper stuff, but I'm still doing, okay? So now this for p, it will be like, okay, rotate it.

So it's going to be like, okay, is this unbalanced? It's going to be like, yeah. Then it will rotate it normally, and then whatever the node is supposed to be over here, which is going to be child, it is going to return that.

And where it will return? From where it was called. So return. the child that we have over here and it will be called from here, so it will return over here so this node.left will now be equal to child and this tree will be rotated okay, cool use the pen and paper, you will understand this is very simple stuff because we have done such questions before and I showed you the problem by running it also copy paste now, write heavy write heavy is when this is actually less than minus one and write write case will be what note dot note dot write write write case let's check the write write case right right case okay node dot right dot left and node dot right dot right the difference between this and this should be negative because this is small this is big so left minus right should be negative so node dot right dot left node dot right dot right should be negative that will be right and in right right case i do left rotate on the note left rotate on the note similarly node.right.left node.right.right should be positive should be positive in this case I am going to say right rotate on child child is node.right so right rotate that is going to be right right rotate node dot right and then left rotate on the node in the end just return the node so even though this is being called for every single path as we move above it will only run once because this condition will only be satisfied once in other cases just return the node itself so in reality this function that you're saying canal you were returning node previously and now you're returning it in a function.

I'm still returning the node only but I'm performing some functions. In one of the cases where the tree is unbalanced, it will adjust the size, sorry adjust the structure, return the correct node. For everything else, it will return the node only. Doing nothing, just returning the node only.

What we were doing previously. Okay now we have to create left rotate and right rotate. Okay, left rotate and right rotate. Let's see how we can do that.

Okay, now right rotate and left rotate. Very simple stuff. So we have already done the overwhelming complex part. All the test cases I showed you, the run through of the code as well.

You can also debug yourself. I've showed you how to put debug pointer into it but I showed you like what the return node is, what the calling the function in the node return is. In the reality, it's only returning the node itself like previously in the previous binary search tree lecture how it was returning the node in insert over here.

but now it's only going to rotate it in one single case and this if condition will only be valid for one single case because it will have that one case that will be subtree that is rotated sorry unbalanced and we're doing uh right rotate left rotate now so we already have this thing over here so ideally you know think about when we were doing linked list the diagram was telling us what to do and we were just coding that i will do the same thing i am shutting off my brain now because my brain it's not required now because whatever the diagram is telling me i will code it i don't even need to understand anything because it's not worth it because we've already understood how right rotate work how ref rotate works now the diagram is telling me what to do so i will just do it understanding part is done okay we did that in theory so think about what all things we don't need to touch uh t3 is not going to be changed Don't touch T3. T1 is not going to be changed. Don't touch T1. T2 will be changed. So P, just gonna write it down.

Right rotate across node P. Node child is equal to P dot left. Node C is equal to P dot left, no problem. Node T is equal to P dot left dot right. now or c dot right t is equal to c dot right t is equal to c dot right okay now right rotate um c dot left will become p and p dot left sorry c dot right will become p c dot right will become p and p.left will become t.

Done. That's it. One last thing you have to do is update the heights now because c was added above, p was coming down.

So, update the height. p.height is equal to math.max Cool? So new height is going to be equal to maximum of left and right plus 1 for this. We have done the height formula before, so don't worry about that. Similarly, c dot height will be equal to mat dot max c dot Left, c dot right, plus 1. Now, what is the new node?

New node is c. Return c. I am telling it again and again. The only intuition problem that you are going to have, I know you are having this doubt, is over in this line 43. Please try to understand that in original format, it was return node.

Right now also, it is return node only. See. it is doing nothing but return node but for that one case in which the sub tree is unbalanced it will balance in then return the node so new node will be returned like c and that will be added over here so it will return then wherever it will be returned from where it was called which is somewhere over here and then that new child will be equal to the node.left of the above the one above that one as i showed you in the example right now when i was writing this code.

Okay, it was very simple. It is don't overthink it. It's very simple. I shared it like three four times.

I won't share it again now because then it will get cringy. Anyway, So I told you where you might get doubt. I solved that doubt now we can move forward.

Okay, now left rotate. Left rotate is very simple. Copy paste. You can still you can just do the use the you know this thing over here.

okay so again no need to think i will take in this example only it's saying c i will have node c over here left rotate so node p is going to be equal to c dot right node p is going to be equal to c dot right and what will remain unchanged um p t3 will remain unchanged t1 will remain unchanged, t2 will be changed. So, c dot right or p dot left, p dot left. Okay? Okay?

So, here we have p dot left is equal to my t. And now, how to change it? So, if I'm changing it left rotate, then p dot left becomes c.

No problem at all and c.right becomes t. No problem. Similarly, p.height and c.height. Looks good. Now new node is equal to p so I will return p.

That's it. AVL tree done. Very cool stuff. Simple, right?

now you can run this let's try running it okay so here in the main function i can write my code i can say avl tree is equal to new avl tree and let's say i insert i'm trying to insert you know ascending order so in binary search state we'll just make a line like i showed in the previous one uh and i is equal to 0 i is less than let's say 1000 and i plus plus I'm going to say tree.insert . If I check the height of this in a binary search tree which is not balancing, it will be like okay right right right right right right right right right right right right right it will give 1000. So system.out.println . This should give log of 1000. Let's see. Okay so log of around 1000 so it should give me one plus log 1000. so log 1000 2 plus 1 3 3 I inserted thousand elements in a tree in binary search tree height would be 1 1 1 1 you know just go right right right right right right right as I showed in the previous example this example but now no it's balancing it that is why always height will be log of n simple very easy very nice self-balancing binary tree is a piece of cake done okay so lastly i'd say you can take a screenshot share it on social media hashtag dsa with kunal join the learning public initiative i'll make tutorials uh much faster at least four videos you can accept expect in a month and as the next one's recorded as well i have to edit those but i wanted to make sure we do this one first before jumping on to the questions because These are some of the concepts that are being used. So, few things.

Number one, like. Number two, comment. Number three...

take a screenshot and share with hashtag DSA with Kunal and that's it. These three things you need to do. For follow-ups, the assignments and everything notes and the code link can be found in the description below.

So you can directly use the URL that I will share with you in the description below and you can just run it after signing up. You can run it and you can run the code that I'm writing, make it, modify it, fork it, do whatever you want and it's very nice because you can do it right from your browser itself like I'm doing. for teaching it makes it much more convenient so yeah like comment if you comment more people will view it and more views will get and more people will learn from these free courses and more motivation i'll get to make such videos so like and comment it at least something you can do and share you can do it if you don't want to that's fine but like and comment please do it if you've watched it till now please like and comment i cannot stress this enough and assignments everything all the links code description below and i'll see you in the next one have a great day bye if you have any doubts comment section

Transcript for:Self-Balancing Binary Trees Explained

Transcript for:
Self-Balancing Binary Trees Explained