Understanding AVL Tree Implementation in C

Welcome dear students to the lecture series of data structures and algorithms. The topic that we are going to learn today is AVL tree implementation using C programming language. We have already seen what is the avl tree how to perform the various operations on avl tree like insert delete and there are some rotations which we need to perform so we have seen those operations now we will check the how to implement the pro avl tree using c program so these are the various functions that we are targeting to cover in today's video okay so here first of all The functions that we will perform is inserting a new node in a tree, deleting a given node from a tree and displaying the AVL tree. So when we are actually planning to insert a new node in a tree, I may be have to perform some rotations and there are four types of rotations that come in a insert function. For which I have written two functions that is left rotate and right rotate. When I am deleting a particular node, there also I am calling the same functions left rotate and right rotate. And when I am displaying the tree, I can display in three different traversal techniques, that is pre-order, in-order and post-order. So these are all the functions which I have written in my particular program. So now these are the extra functions which we are using or the sub-functions which are used. in this particular function say for example height max new node gate balance and minimum value node okay so now let us go ahead and understand it all with the help of a code so here this is the code for avl tree in beginning we are writing the header files and then here i'm declaring a struck node the node here is having four value four members that is key left right and height and height okay so when i'm dealing with the avl tree i need to have a height of the tree so that's why a node of the avl tree will have four members left address address of left child key value is nothing but data right address of right child and height of the node okay so after creating the struct node definition what we are doing is now we are doing this integer height function these are the small small sub functions which we are using in larger or the bigger functions so the height function what is this task okay so here the height function will tell you if any node is there it will have a last item as a height okay and we have to calculate the height of a node ok so what is the height of a node will be reflected in this particular integer element so height of any node struct and node will be given as an input so if that node is null that means there is nothing in that node ok that node is completely blank in that case we will return the height is 0 otherwise we will return whatever is the height of that node that is n height so that particular node whatever I have written inside height I will return that if it is 1 2 I'll return accordingly okay so this is all about the height function the next is max function what we are doing in max it's okay I will I have given two integers as a input that is a and B okay so when you are doing this max functions you are getting two input at is a and B what you are doing is you are comparing who if a is greater than B If the answer is yes, then we are returning A as our output and if answer is no, then we are returning B as output. That means this function overall returns the maximum value among A and B. Okay, that is done with this one line of code. okay and it is returning the integer value that is earning but maximum value among a and b so this is all about integer max function the next function that we have written is a new node function which is taking as a input a key value which is a integer value so now let us see this function so this new node function is actually creating one node for us and allocating some values to the node so here we can see new node is taking as an input only key value or the data item which I want to store inside the node then I'm creating a node with a variable no de from struct node definition and I'm allocating the size that is malloc from the main memory and then in that node I have four fields so I'm just putting the values in all the four fields key I'm storing the value which I have given which is provided by the user Left I am keeping as null, right I am keeping as null and height of every node by default I am giving as a 1. And then I am returning the address of the newly created node to the user as a return type. So that is nothing but I am just filling this left child as null, right child as null. Value is having key which is provided by the user and by default I am giving height as 1. and the address of this node i'm giving back to the user okay so this way we are creating a new node with the value provided fine so then the next function that we are going to learn is get balance these are all the sub functions small small functions which we may be using in the other functions so get balance is taking as input one node okay so if a node is given to you the job of this function is to tell you what is the balance factor of the given node Suppose if this node is given to me that is n. So in this function it is taking as input node n. What it has to do? It has to tell you what is the balance factor of the node. If the node is completely empty that is it is null. There is nothing in that particular node. There is no tree available. I will return 0 as a balance factor. Otherwise what I will return? Height of n left minus height of n right. that is nothing but what is there in the left of n that is this particular subtree the height of this subtree if it is one and height of this subtree if it is one so one minus one so we i am getting it as zero that's why i can say balance factor of node and is zero okay so here i can get the balance of any node with this particular function so here we are storing the height of the node and balance factor is something which we find within by using the function height of left minus height of right okay it's the same formula I have used here and I have returned the balance factor of any node which I am calling after that the last from a small function that we will be seeing is mean minimum value node so sometimes I need to find out the in order successor of a node Inorder successor means if I am reading my tree in inorder traversal sequence, so which node comes after the given node that is nothing but a successor. So normally if for any node, its inorder successor is always found on the right subtree of that node and that value is the lowest value in the right subtree. That means it is the leftmost element in your right subtree. So minimum value node function will give over here now suppose if this is the function given to me okay so minimum value node what it will do if struck node is given to me what will i do is Struck node current is equal to node. So this node is given to me. I have taken a variable called as a current which is also pointing to the same node. That is by doing this particular line current is equal to node. Now current is also pointing to node. Now what I am doing I am going in a while loop. While current dot left is not null. okay so whenever i have a left child what will i do current will now change to the current of left okay that means if current is having left child yes so current will now go to the left child again it will go in while loop and check if there is having a left child yes then current will go to the left child again if there is a left child yes then current will go to the left child this way i am able to find the minimum value uh in the given but as for that particular value node okay and then wherever i stop i come out of the while loop i return the current so here my current is at 4 so i have found the minimum value in this particular subtree under the node given 12 okay so this way this current value i am returning to the user Okay, so is this all clear with the everyone that is these are the small small sub functions at least we just understand the functionality of this functions. Now we will understand the main functions. Okay, so main functions when I say I mean that actually we are so here we are targeting to perform insert delete and display function these are the main functions so for insert inside insert i'm going to call left rotate and right rotate function so first of all let's understand how do we write left rotate and right rotate functions one by one okay so now you The first I will see is a left rotation. Left rotation functions is we apply whenever while adding a new node. If the new node is after adding a new node, say for example, after adding a node C in this particular tree, if the balance factor is not same as minus one zero or one. that is if it is going to minus 2 or like that in that case i have to apply rotation so whenever you have minus 2 followed by minus 1 i have to apply left rotation on the root node okay for detailed information on this rotations you can refer to the my video which is uh theoretical explanation of avl and all its operations okay after applying right rotation left rotation on the root uh this particular node a i will get my tree balanced okay so now let us see that in the code this is a left rotate function so now here i'm checking the node on which uh there is a critical node yeah so critical node we are taking as an input over here so critical node is a one which is having a balance factor minus two okay now what i'm doing is So say for example this is the case here you have added a new node d okay and after adding d the tree balance factor is imbalanced because for a the balance factor is minus 2 which is not allowed. So what you will do in that case your a is a critical node which you are giving as an input to this particular function say for example x. So x is pointing to a okay now what you will do First of all, you make struck node Y which is equal to X dot right. Okay, so X dot right will be pointed to Y. Then T2 will point to Y left. So who is on Y left? C. So T2 will point to C. Now what will I do? I want to perform the rotation. I want to perform left rotation on root node that is on X. So if I apply left rotation on A, that means A will go down. and B will be the parent of A. Okay, that means what I will do, I will write these two lines. Okay, what is this? Y ka left is X. Okay, so on left of Y, I will put X. So who is Y? Is B. So B ke left mein A aana chahiye. So B ke left mein A aayega. So B ke left mein jo C tha, that is been removed. And next line that I am doing is, X ka right should be T2. So who is on right of x? X ke right me, A ke right me kaun hai? B hai. But now A ke right me kaun ana chahiye? C. So when I am taking this particular thing, B ka left is pointing to A. That time A is coming down as a left child of B. And now A was still pointing to B. So now what I did, x right is equal to t2. So x ke right me, matlab A ke right me t2 matlab C aega. And with this, I got my tree balanced. Now you can see the balance factor are all in the acceptable range that is minus 1, 0 or 1. So now my tree is balanced properly. So this way we are doing it. Now after performing rotations, I need to adjust the height properly. So I will just change the height of X and Y because X and Y have changed their locations. So what will be the height of X? That is maximum between height of X left sub... tree and X car right sub tree so if X kill left well in Norka or XK right well in order to hide there would only messages called maximum height and so X collect mirror is nothing but right I have one node that means the height is maximum height is 1 from 0 and 1 plus 1 because I'm adding the height for X node which is one level up okay so 0 plus 1 so that means X height of X X will be 2 and Now what is the height of Y? Maximum of Y's left child and Y's right child. So Y's left child's height is 2 and Y's right child's height is 1. So 2 and 1 makes a maximum of 2 plus 1. So when I am doing plus 1, Y's height will be H is equal to 3. So that means the node at this level will have height 1, node at this level will have height 2. Okay, and this will be having height 3. Obviously, D is having height 1, okay, because it has no sub... Children's or do it it is a leaf node and then we are returning this Y to the you So Y is given or returned as a return type because here after performing this rotations the root of this tree is changed. Earlier it was A now it is B. So wherever is a root I have to return that. That's why I am returning Y. Okay. So now what I am doing is I am returning Y. I have performed the left rotation. Next let's go and see the right rotation. So right rotation. is something in this case when the new node a is added in a tree the balance factor of c is disturbed okay so i call c as a critical node and over here i will apply the right rotation and then my tree will be balanced so how do we do that let's take an example of this particular small tree if i add a then the balance factor of tree b is becoming 2 and now i need to balance it okay so how do we do that So first of all the struct we are getting as a input Y node from the user. So we are creating a new node X which is Y's left. So Y is given by the user that is the root of the tree. I am saying that X is left of Y that means X will point to B. So X is left of Y that means it is pointing to B and T2 will now point to X's right. So X's right is C and T2 is pointing to it. Now I will perform the rotation in these two lines. What I am doing is, I want to perform the right rotation on D. That means D should go down and become the child of B. Okay, so what will I do? X's right is equal to Y. So X's right means B's right should be D. So D should be on B's right. So D should be on B's right. So C should not be on B's right. So if I do this way that means B ke right me D aagya but D is also pointing to B. Now what should I do? I will perform the next line. Y ka left should be T2. So now what will I do? Y ke left jo D B ko point kar raha hai wo abhi C ko point karega. So Y ka left will be pointing to T2 that means it is pointing to C. After doing these two lines you can see the tree is now balanced. All the balance factors are in acceptable range. Okay. And now your tree is balanced. You just need to calculate the height of X and Y because we have modified our X and Y. So now I am calculating the height of Y that is maximum of Y's left height and Y's right height. So Y's left height is C whose height is 1. Y's right height is 0. So 1 and 0 makes maximum of 1 plus 1. yeah you see the plus one that means like a height will be now equal to two and what is the height of X that is left child and right child missing maximum who is the rep what is the height of left child one and height of right child two so one and two miss a maximum con head two plus one so that is the height of node X so this way I have updated height of X and Y and then I'm returning X why I'm returning X because after performing this rotation who becomes a root node of the tree x so whoever becomes a root node i have to return that that's why i'm returning x over here so this is all about the left and right rotate functions now we will go and understand the insert node function in detail so for performing insert node function just consider we have a tree okay having such nodes And the node is a variable is pointing to the root node. And I want to insert a new value into the AVL tree. Okay. So what we will do, we will first take as an input this node. Okay. As a root node and the key value or the value which I want to insert in a new node. Okay. What will I do is first of all, I'll check if node is equal to null. If the node which you want to insert is completely null, then we will return new node dot. new node and so here we are calling a function new node with the value key so new node will create a new node put the value key inside it and that node we will return as a root of your tree and we are returning it okay so if the tree is completely empty then we will this particular case will take place else if your tree is not empty and tree is having some values And I want to insert a value which is 2. So, I will compare 2 with the value 10. So, how I am doing it? If key is less than node key. Now, what is node key? Node's key is 10. If 2 is less than 10, it should go to the left child. If it is greater, it should go to the right child. So, if key is less, then I am going to the left child. That means I am calling the same insert node function recursively. for the left child with the same key value as the input. Getting it? And that, jo bhi naya node yahaan pe banega, wo naya node mein, is node ke left mein uska add, So it will point to that particular node. Okay. so it will point to that particular node over here now this is if the key is lesser than node ok if the key is greater than nodes key that means the value to a value 30 is greater than 10 so then I should be going to the right child and here I will call the function recursively ok so if it is greater than node key then I'm going to the right child and I'm calling the insert node function recursively to the right of the right child of the root node and passing the same key to insert the value over there okay so this way it will keep on going recursively in your tree and it will traverse through the entire tree and reach the proper location where you have to actually add a new node so it will reach some of the leaf node where there is nothing on the right and there a new node you will be added say for example in this case i have reached the left of five which is none okay you so left of phi is null now i can add 2 over there so what will i do in that case so there the node will be null so when i reach the left of phi and my node becomes null that time i can create a new node with value 2 and this 2 should be linked to 5. so here this particular function is taking place at some place when your node is null here you are creating a new node with the value key which is provided by the user and that is your returning to the calling function so it will go to the calling function of left because left one called it it was a left child so when it is returning that particular node's address that address is stored in the previous calling function left pointer that means five node left pointer so fives left will hold the address of node two this way these functions are returning and getting connected so in this particular lines what is happening is that your new node is getting added or getting inserted in your avl tree now after adding a new node you may get your tree unbalanced unbalanced means the balance factor is not proper so in that case rotations need to be applied yeah so this next part here update the balance factor of each node after performing insert operation we will update the balance factor of each node and we will check if any balance factor is improper so how do we do that so we are checking the nodes height okay the new node which we added so what will be the height over there that is for each node maximum height of nodes left and nodes right okay so max kisi bhi node ka height kya hota hai uske left ya right me se jo bhi node ka maximum height hai plus one so i will update this height for each and every node then i will update the balance okay so balance is holding the balance factor of any node it will just call the function get balance get balance will give you me give me the balance factor of every node and with this i will calculate what is the balance factor so after adding a new node some critical node will have the improper balance factor say for example in this case a and b was there in my tree after adding c A's balance factor is minus 2 which is a critical node because this is not acceptable. So in this case I should be applying a single left rotation on A. Okay, so what will I do? Here after calculating balance I will see if any rotations need to be applied. So there are four cases single right rotation, single left rotation, LR rotation which is double rotation and RL rotation which is double rotation. So single right rotation takes place only when when the single right rotation takes place when your critical node has a value which is 2. Yeah, it is positive 2 not negative. So when your balance factor is greater than 1 means 2, 3, whatever. Okay, so that means yes, this is the case. Your balance factor is greater than 1 and the new node which you are added is the leftmost child. Yeah, so the key or the value which you are added is less than the nodes left key. So, node ke left me jo hai, it is lesser than the node and obviously and the new node is which you added is also lesser than the left child. That means you have added the new node in the left of left. In that case, we are supposed to apply the right rotation on C. So, what will I do? If these conditions are true, I have to apply right rotation and I am just applying a right rotation for that given node. Okay, and then whatever is the value I am returning to the user. Okay, else if this is not the case, then I will check if balance factor is less than minus 1. If it is less than minus 1 means it is minus 2 minus 3. 3 so i will check if balance factor is minus 2 say for example and key is greater than no whatever is there in the right of node is greater than it and the new value which i've added is more is greater than the nodes right that means i have added the c over here and in that case i should be applying one single left rotation at a so if this particular LL case is there this condition will be true and I will apply left rotation on that critical node okay else if it is a LR rotation how do I come to know LR rotation is the one where your balance factor is greater than 1 that is it is positive value 2 or 3 and the new value which you added is greater than the left node is greater than the left child yes Here it was earlier case it was less than the left child but now it is greater than the left child. So here I am checking if balance factor is greater than 1 that means positive 2 and the value which you added is greater than the nodes left key. So value is greater than the nodes left key. In that case I should be apply LR. In LR, on which rotation we will apply first rotation? On the left child of node. so here we are applying left rotation on the left child of the node on the left child of the node I am applying left rotation first and then I am applying right rotation on the node itself on C node so after that I am applying right rotation on the node this is all about the LR rotation next I will check for the RL rotation in this case your balance factor is minus 2 so when your balance factor is less than minus 1 means minus 2 minus 3 And the key which you have added is less than node's right key. So, is it less than node's right? Yes. So, now I have to apply RL rotation. What will I do in this case? First of all, right rotation will come on C. Right rotation will come on C. Means right rotation will come on node's right child. So, here node's right child will be applied. and then then on node i am applying left rotation then on given node i am applying left rotation so this way i am doing with the l rl rotation and at the end i am returning the node that is a root of that tree to the calling function so here we are done with the insert function okay hope you have understood this insert function What we are doing in the insert function if you just look at this in parts. So in the first part what I am doing is I am traversing through the tree and reaching the proper place where the node has to be added and there I am adding a new node. After adding a new node what I am doing is I am calculating the height and balance factor of each and every node and then I am checking if any rotations are required then I am applying those four rotations. okay this is all about the insert function now let's go and understand the delete function Okay, so here in the delete function, if the tree is given to us and we want to delete a particular value, okay, so the node is pointing to the root node, okay, so now let's see the delete function. I am taking the root node of my tree and the value which I want to delete that I am taking in a variable key from the user as a input. First of all, I am checking if the root is null, that means the value which you are searching for is not available or else your tree is empty. Okay, so we are returning the root and we are stopping there itself. Okay, so when we return something, we stop the function, right? Else, if the root is not null, means your tree is not empty, in that case, what will I do? I have to traverse either left or right. So, I will check the value. If the key which you are looking for is less than the root key, okay, suppose I am looking for value 2. If it is less than root key, then I will go to the left, otherwise I will go to the right. So what it is checking if it is less I am calling the same delete node function recursively and I am going to the left child and I am giving the same key as the input. Here we are calling the same function recursively if it is lesser. Else if the key is greater we are going to the right child and calling again the function recursively. After deleting whatever node is there, it is again giving us value return and that we are saving in the address of right node or left node over here. Okay, so this way we are just traversing in a tree and we are calling this function. Now, if the value which you are looking for is not available, yeah, suppose I am looking for 2 and it is not available in my tree. So what will happen in that case? I will end up at this particular if condition. And I will return that value is not found. Because I will return the null value. which is obviously not found okay else case if the value which i'm looking for is found yeah so uh if this if and else if will just help me to traverse to left right left right left right and if once i reach i want to delete node 5 value 5 and i have reached to the value 5 i have reached this node so in that case i will enter the else case you okay now in this else case i am checking okay the node which i want to delete i have reached that node now i just need to delete that node properly okay so when we are deleting something we have to free the memory also and all those conditions okay so here we are checking the node which i want to delete is either having zero child one child or two child so depending on that we will delete and we will replace some values over there so here the first condition i'm checking is If root.left is null or root.right is null, means the node you want to delete, suppose there are 5 nodes, I want to delete the node 5, and whether its left subchild is null and right child is also null, if there is one of the two, then it means, Say for example, the 5 ke right me mere paas 8 hai. So 5 ke left me kuch bhi nahi hai. Matlab 5 ka left is none. So the node which you want to delete is having single child. So what I am checking with this particular node is that the node which you want to delete is having single child. is either left is null or right is null. Okay. So, then what we are doing is we are taking a temporary variable and temporary variable will have which value. So, this is the ternary condition. So we are checking if root left is having some value. That means, jo hum lo ko delete karna hai, usko root ne point karke rakhay. So the node 5 ke left me kuch hai kya? Agar node 5 ke left me kuch bhi hai, if there is some value or some node connected to it, we will have temp storing the left child of 5. But if the node 5 is not having a left child and it is having a right child, in that case, temp will hold the address of right child of 5 getting it so that means whichever child is available either left or right temp will point to that child so now your temp is pointing to 8 getting it So here I am checking if temp is equal to null. If temp is equal to null, when your left or right child is one of them, then your temp will point that particular child. If left is not there, then it will point right. If right is not there, then it will point left. It is equal. But just consider your root is at 20 and 20 has no child, not on left also and not on right also. So in that case, your temp... what will it will hold your temp will hold value null because it's both the child's are So we are checking that if both the values are null, okay, so in that case, we can say the node which I want to delete, I have reached that node, but it is a leaf node, it has no child. Okay, or leaf node ko delete karna bahut easy hai. So how do we do that? We will now point to root. Okay, so temp jo null kiya hai, wo abhi root, matlab is node ko point karega. So temp will also point to this node. Okay, temp is no more null and then I will say root is equal to null this particular Job any delete can I hear no? Poe this come a root Joe's copoint garrison so I'll say root is equal to null that means I have deleted that value When root says null that means that node is no more there and I just need to free the memory so that I will handling Outside the if case free temp so the temp is holding the address of 20 Okay, so it will free that means release the memory occupied by node 20 getting it So this if condition will take place when you are reaching the node Which you want to delete is having zero child else else condition cup true Hoga So I keep us yato left child here to write child head on omiss a quick a key child Hey, the web else major audience so that time the node to be deleted has only one child Maybe it is a left child. Maybe it is a right child Suppose in this case after node 5 left child was not there but right child is there. So if right child is there your temp is pointing to right child and root is pointing to the node which you want to delete. So what will I do in this case? I have to delete 5 and right child is 8. So 8 will come in place of 5. That means root's value is 8. will be the value of 10 that means what i'm doing in this else condition is value at root is equal to value at 10 so poora root ka jo bhi values hai ye hum log copy paste karenge and this node 8 will be overwritten on this particular node so automatically 8 and all its child will take place over there and just 5 node we can now you delete okay so in that case i can just free temp because temp was pointing to this node okay so with this we have covered the condition two conditions the node which i want to delete is having zero child or one child now we are coming out of the if condition here and if we reach this else condition means both are not null your left child is not null and right child is not null then we reach the else case and that means the node which I want to delete is having both the two child in that case how do I delete? so whenever I want to delete a node and it is having both the child say for example I want to delete 10 and it is having two child so how do I do that? so I find out is inorder successor means from right side, right subtree, I will choose smallest value which is nothing but inorder successor and that particular value I will replace with the node which I want to delete so now your root is pointing to the node which you want to delete which is having two child ok how do we go ahead so what I am doing is I am taking a temp variable temp is equal to minimum value node we have seen this function earlier what we are doing in this whatever root right node we got root right means we are in 20 we are in 20 So who is pointing to 20? I have passed root of 20. The minimum value from 20, means 20's leftmost, leftmost, leftmost child will be found, which is the smallest. And that smallest value which will return me the function, this minimum value function, that value will be held by my temporary variable. So temporary variable will point to the smallest or leftmost value in your tree, which is nothing but inorder successor. and this value say for example it is 11 okay so this value now what i'm doing is root key is equal to temp key so root key is nothing but 10 and i want to replace 10 i want to delete 10 so 11 will replace that so root key is equal to temp key so now 11 will come here okay and then whatever I do my job is done 11 has come here I just need to delete node 11 so how do I do that root.write is equal to delete node root.write and its value I gave key of temporary so what was the key of temporary 11 so to delete 11 I called recursive function from where I told its root from root right means I started from 20 so 25 starting a delete function it will go ahead and delete the value 11 which is at the leaf node i'm not starting from this node so this node will not be deleted only the leaf node having value 11 will be deleted so with this i have handled the case where i have two childs and i want to i'm done with the delete uh okay so again in delete function all these things are they are doing what here we are traversing and reaching a node Here after reaching the node we are deleting it properly considering one child, two child, zero child and after deleting the node we have to check the balance factor of the tree. So what I am doing if your root is null then I am returning root that means value which you are looking for is not found. After that I am calculating the height and balance of the node. So I will first calculate the height. Say for example after deleting 20 I have to change or check what is the height of 10. What is the balance factor of 10. It is changed or do I need to adjust or do balancing over there. Okay. So I will check the root height is equal to okay. 1 plus maximum of left child or right child. Okay, so left or right message of maximum plus one. So I will be updating height of every node. I will be finding out the balance factor for the root node for which we deleted the value. Okay, so now I will check the after performing delete we have to apply the rotations. So delete rotations are different than the rotations which we apply in insert. So delete rotations are this rotations. That is L rotation or R rotation. L rotation is of three types L0, L1, L-1 and R rotation is R0, R1, R-1. Okay, so what exactly we are doing in R0. So after deleting a node from the right side, okay, your root node is having a critical node is getting. improper balance factor and in that case the left child yeah so left child of your tree if it is having balance factor 0 then i'm applying r0 rotation what i'm doing i'm i'm just moving the critical node to the right side okay so now let's just check this if balance factor is greater than 1 that means here yes the balance factor is 2 which is greater than 1 and balance of root left is greater than equal to 0 so the balance of root left is equal to 0 so if it is equal to 0 then I will apply R0 rotation R0 rotation only rotates the right side of the root so apply right rotation on that root node means at 20, after this we will perform R1 rotation, R1 is something when we are getting a critical factor 2, okay, and the left node is having value 1, so again this is the condition, if same condition, yeah, if balance factor is more than 1, that is 2 and get balance of roots left is greater than 0. So, if the left value of the root is 40, the balance factor is greater than 0. Yes, it is 1. What will I do? Apply right rotation on root node. That's why I have combined them together into 1. Okay. So, greater than sign is for R1, equal to sign is for R0. It is covering both these rotations. And what they are doing? They are rotating only one single right. After that R-1 rotation is little different. So R-1 rotation says you get a critical node having valance factor 2 but the left node is having valance factor minus 1. So then I have to apply two rotations. First is to apply to the left one. L rotation apply and then root ko right rotation apply karenge. Okay. So now here I am checking the next condition. If balance factor is greater than 1 that is 2. And balance of roots left is less than 0. So root ke left ka balance factor is less than 0 hai. Yes. So now what will I do? I will apply two rotations. Pahela me left apply karenge. Phir right apply karenge. Left rotation on root ke left me. Matlab root ke left kaun hai? 40. 40 ke upar mujhe left rotation apply karna hai. And then root node pe mujhe right rotation apply karna hai. Matlab 50 pe right rotation apply karna hai. So with this after applying these two rotations I am doing this R-1 rotation. Similarly the opposite case comes for L rotation. L rotation means when our balance factor is less than minus 1, then it is minus 2. And the balance factor of root dot right is less than equal to 0, then it is L minus 1 or L0 rotation. There we are just applying a single left rotation on root. okay or l1 rotation me kya hoga hamara balance factor minus 2 hai or root ke right me okay the root ka right is greater than 0 that means 1 hai okay so if your balance factor is minus 2 and root ka right is 1 which is l1 rotation i will apply 2 rotation so root ke right pe ham log right rotation karenge and root ke upar left rotation karenge so with this after applying two rotations in l1 we are done so this all are just performing the rotations depending on the balancing required after delete okay and at the end i am returning the root node whichever is there okay so with this we are done with the delete function after delete function there are these three extra functions which are printing the tree or displaying your tree in inorder preorder and postorder okay so this is all same as we have seen in the binary search tree also so i am not repeating the same thing again if you want more details you can just go and watch the explanation which i have given for code in binary search tree okay so what we are doing i am checking the root of my tree as an input and until the root is not null or until i am not traversing to the leaf node okay what will i do i will follow the pre-order what is the sequence in pre-order pre-order is root node first then left then right so that's why i'm displaying the value of root node and then i'm going to in the root left and then right so root left and right is nothing but recursive call of the same function pre-order to the left and right if it is in order that means it is following the pattern is left child first then root then right child So it is giving the left recursive call first then printing the root value and then printing the right. Then recursive call to the right as per the notation Lrv. And what about post order notation? It is LRV. So left recursive call will go first. Right recursive call will go after that. And third line will be the printing the root value. This way we are just calling this in order, pre order, post order function. We have done with all the functions. Now let's see the main function. main function i'm just declaring a root variable beginning with the null so i'm just creating an empty tree here and i'm checking this while loop which is continuously running there is no stop for this while loop so here i'm giving this cases one two three four okay insert delete and four to exit so whatever choice user is entering i'm going if case one i'm calling insert function with the value taken from the user if case two i'm calling delete function if case 3 i'm calling all the three in order pre-order post-order and i'm displaying in all the three patterns and if case 4 that means exit i'm calling this i'm writing this exit function which will come out of the while loop so easily i have my while loop condition and then i will return and i will close the main function here so with this we have done the entire code okay okay so now we are done with the program so now let us run a program and check the output so i'm running my code so here i get four options first of all i'll insert say for example 10 then i insert say for example 20 uh so here i will just check my tree 10 will become a root node okay so pre-order my root node is the first one and last one in post order means my train is my root node now if i am adding one more value which is say for example 30 so 10 20 30 will be there in that case my balance factor is not balanced now so i will just display and i will check so now the root node is no more 10 the root node is become 20 you can see in pre order and post order 20 with a start or a last me i i mean 10 will become a left child 30 will become a right child so it is balancing itself properly now suppose i will add value 40 okay and again i display so 40 has become the right side of 30 okay now if i want to delete a value say for example 20 which is the root node okay so after deleting the root node having two child i will just display my tree so now my tree has three values 30 10 and 40 so it has taken the in order successor that is 30 on the right side 30 or 40 30 become the root node and now i can see my tree so here we are the tree is this program is working fine okay so we'll just exit a program okay so thank you everyone for watching this video if you have any doubts you can ask me in the comment box below and do subscribe to this channel for more videos thank you

So when we are actually planning to insert a new node in a tree, I may be have to perform some rotations and there are four types of rotations that come in a insert function. For which I have written two functions that is left rotate and right rotate. When I am deleting a particular node, there also I am calling the same functions left rotate and right rotate.

And when I am displaying the tree, I can display in three different traversal techniques, that is pre-order, in-order and post-order. So these are all the functions which I have written in my particular program. So now these are the extra functions which we are using or the sub-functions which are used. in this particular function say for example height max new node gate balance and minimum value node okay so now let us go ahead and understand it all with the help of a code so here this is the code for avl tree in beginning we are writing the header files and then here i'm declaring a struck node the node here is having four value four members that is key left right and height and height okay so when i'm dealing with the avl tree i need to have a height of the tree so that's why a node of the avl tree will have four members left address address of left child key value is nothing but data right address of right child and height of the node okay so after creating the struct node definition what we are doing is now we are doing this integer height function these are the small small sub functions which we are using in larger or the bigger functions so the height function what is this task okay so here the height function will tell you if any node is there it will have a last item as a height okay and we have to calculate the height of a node ok so what is the height of a node will be reflected in this particular integer element so height of any node struct and node will be given as an input so if that node is null that means there is nothing in that node ok that node is completely blank in that case we will return the height is 0 otherwise we will return whatever is the height of that node that is n height so that particular node whatever I have written inside height I will return that if it is 1 2 I'll return accordingly okay so this is all about the height function the next is max function what we are doing in max it's okay I will I have given two integers as a input that is a and B okay so when you are doing this max functions you are getting two input at is a and B what you are doing is you are comparing who if a is greater than B If the answer is yes, then we are returning A as our output and if answer is no, then we are returning B as output.

That means this function overall returns the maximum value among A and B. Okay, that is done with this one line of code. okay and it is returning the integer value that is earning but maximum value among a and b so this is all about integer max function the next function that we have written is a new node function which is taking as a input a key value which is a integer value so now let us see this function so this new node function is actually creating one node for us and allocating some values to the node so here we can see new node is taking as an input only key value or the data item which I want to store inside the node then I'm creating a node with a variable no de from struct node definition and I'm allocating the size that is malloc from the main memory and then in that node I have four fields so I'm just putting the values in all the four fields key I'm storing the value which I have given which is provided by the user Left I am keeping as null, right I am keeping as null and height of every node by default I am giving as a 1. And then I am returning the address of the newly created node to the user as a return type.

So that is nothing but I am just filling this left child as null, right child as null. Value is having key which is provided by the user and by default I am giving height as 1. and the address of this node i'm giving back to the user okay so this way we are creating a new node with the value provided fine so then the next function that we are going to learn is get balance these are all the sub functions small small functions which we may be using in the other functions so get balance is taking as input one node okay so if a node is given to you the job of this function is to tell you what is the balance factor of the given node Suppose if this node is given to me that is n. So in this function it is taking as input node n.

What it has to do? It has to tell you what is the balance factor of the node. If the node is completely empty that is it is null.

There is nothing in that particular node. There is no tree available. I will return 0 as a balance factor.

Otherwise what I will return? Height of n left minus height of n right. that is nothing but what is there in the left of n that is this particular subtree the height of this subtree if it is one and height of this subtree if it is one so one minus one so we i am getting it as zero that's why i can say balance factor of node and is zero okay so here i can get the balance of any node with this particular function so here we are storing the height of the node and balance factor is something which we find within by using the function height of left minus height of right okay it's the same formula I have used here and I have returned the balance factor of any node which I am calling after that the last from a small function that we will be seeing is mean minimum value node so sometimes I need to find out the in order successor of a node Inorder successor means if I am reading my tree in inorder traversal sequence, so which node comes after the given node that is nothing but a successor. So normally if for any node, its inorder successor is always found on the right subtree of that node and that value is the lowest value in the right subtree. That means it is the leftmost element in your right subtree.

So minimum value node function will give over here now suppose if this is the function given to me okay so minimum value node what it will do if struck node is given to me what will i do is Struck node current is equal to node. So this node is given to me. I have taken a variable called as a current which is also pointing to the same node. That is by doing this particular line current is equal to node.

Now current is also pointing to node. Now what I am doing I am going in a while loop. While current dot left is not null.

okay so whenever i have a left child what will i do current will now change to the current of left okay that means if current is having left child yes so current will now go to the left child again it will go in while loop and check if there is having a left child yes then current will go to the left child again if there is a left child yes then current will go to the left child this way i am able to find the minimum value uh in the given but as for that particular value node okay and then wherever i stop i come out of the while loop i return the current so here my current is at 4 so i have found the minimum value in this particular subtree under the node given 12 okay so this way this current value i am returning to the user Okay, so is this all clear with the everyone that is these are the small small sub functions at least we just understand the functionality of this functions. Now we will understand the main functions. Okay, so main functions when I say I mean that actually we are so here we are targeting to perform insert delete and display function these are the main functions so for insert inside insert i'm going to call left rotate and right rotate function so first of all let's understand how do we write left rotate and right rotate functions one by one okay so now you The first I will see is a left rotation.

Left rotation functions is we apply whenever while adding a new node. If the new node is after adding a new node, say for example, after adding a node C in this particular tree, if the balance factor is not same as minus one zero or one. that is if it is going to minus 2 or like that in that case i have to apply rotation so whenever you have minus 2 followed by minus 1 i have to apply left rotation on the root node okay for detailed information on this rotations you can refer to the my video which is uh theoretical explanation of avl and all its operations okay after applying right rotation left rotation on the root uh this particular node a i will get my tree balanced okay so now let us see that in the code this is a left rotate function so now here i'm checking the node on which uh there is a critical node yeah so critical node we are taking as an input over here so critical node is a one which is having a balance factor minus two okay now what i'm doing is So say for example this is the case here you have added a new node d okay and after adding d the tree balance factor is imbalanced because for a the balance factor is minus 2 which is not allowed.

So what you will do in that case your a is a critical node which you are giving as an input to this particular function say for example x. So x is pointing to a okay now what you will do First of all, you make struck node Y which is equal to X dot right. Okay, so X dot right will be pointed to Y.

Then T2 will point to Y left. So who is on Y left? C. So T2 will point to C.

Now what will I do? I want to perform the rotation. I want to perform left rotation on root node that is on X.

So if I apply left rotation on A, that means A will go down. and B will be the parent of A. Okay, that means what I will do, I will write these two lines.

Okay, what is this? Y ka left is X. Okay, so on left of Y, I will put X. So who is Y? Is B. So B ke left mein A aana chahiye.

So B ke left mein A aayega. So B ke left mein jo C tha, that is been removed. And next line that I am doing is, X ka right should be T2.

So who is on right of x? X ke right me, A ke right me kaun hai? B hai. But now A ke right me kaun ana chahiye?

C. So when I am taking this particular thing, B ka left is pointing to A. That time A is coming down as a left child of B. And now A was still pointing to B.

So now what I did, x right is equal to t2. So x ke right me, matlab A ke right me t2 matlab C aega. And with this, I got my tree balanced.

Now you can see the balance factor are all in the acceptable range that is minus 1, 0 or 1. So now my tree is balanced properly. So this way we are doing it. Now after performing rotations, I need to adjust the height properly.

So I will just change the height of X and Y because X and Y have changed their locations. So what will be the height of X? That is maximum between height of X left sub... tree and X car right sub tree so if X kill left well in Norka or XK right well in order to hide there would only messages called maximum height and so X collect mirror is nothing but right I have one node that means the height is maximum height is 1 from 0 and 1 plus 1 because I'm adding the height for X node which is one level up okay so 0 plus 1 so that means X height of X X will be 2 and Now what is the height of Y? Maximum of Y's left child and Y's right child.

So Y's left child's height is 2 and Y's right child's height is 1. So 2 and 1 makes a maximum of 2 plus 1. So when I am doing plus 1, Y's height will be H is equal to 3. So that means the node at this level will have height 1, node at this level will have height 2. Okay, and this will be having height 3. Obviously, D is having height 1, okay, because it has no sub... Children's or do it it is a leaf node and then we are returning this Y to the you So Y is given or returned as a return type because here after performing this rotations the root of this tree is changed. Earlier it was A now it is B.

So wherever is a root I have to return that. That's why I am returning Y. Okay.

So now what I am doing is I am returning Y. I have performed the left rotation. Next let's go and see the right rotation. So right rotation.

is something in this case when the new node a is added in a tree the balance factor of c is disturbed okay so i call c as a critical node and over here i will apply the right rotation and then my tree will be balanced so how do we do that let's take an example of this particular small tree if i add a then the balance factor of tree b is becoming 2 and now i need to balance it okay so how do we do that So first of all the struct we are getting as a input Y node from the user. So we are creating a new node X which is Y's left. So Y is given by the user that is the root of the tree.

I am saying that X is left of Y that means X will point to B. So X is left of Y that means it is pointing to B and T2 will now point to X's right. So X's right is C and T2 is pointing to it. Now I will perform the rotation in these two lines.

What I am doing is, I want to perform the right rotation on D. That means D should go down and become the child of B. Okay, so what will I do?

X's right is equal to Y. So X's right means B's right should be D. So D should be on B's right.

So D should be on B's right. So C should not be on B's right. So if I do this way that means B ke right me D aagya but D is also pointing to B. Now what should I do? I will perform the next line.

Y ka left should be T2. So now what will I do? Y ke left jo D B ko point kar raha hai wo abhi C ko point karega.

So Y ka left will be pointing to T2 that means it is pointing to C. After doing these two lines you can see the tree is now balanced. All the balance factors are in acceptable range.

Okay. And now your tree is balanced. You just need to calculate the height of X and Y because we have modified our X and Y.

So now I am calculating the height of Y that is maximum of Y's left height and Y's right height. So Y's left height is C whose height is 1. Y's right height is 0. So 1 and 0 makes maximum of 1 plus 1. yeah you see the plus one that means like a height will be now equal to two and what is the height of X that is left child and right child missing maximum who is the rep what is the height of left child one and height of right child two so one and two miss a maximum con head two plus one so that is the height of node X so this way I have updated height of X and Y and then I'm returning X why I'm returning X because after performing this rotation who becomes a root node of the tree x so whoever becomes a root node i have to return that that's why i'm returning x over here so this is all about the left and right rotate functions now we will go and understand the insert node function in detail so for performing insert node function just consider we have a tree okay having such nodes And the node is a variable is pointing to the root node. And I want to insert a new value into the AVL tree.

Okay. So what we will do, we will first take as an input this node. Okay. As a root node and the key value or the value which I want to insert in a new node.

Okay. What will I do is first of all, I'll check if node is equal to null. If the node which you want to insert is completely null, then we will return new node dot. new node and so here we are calling a function new node with the value key so new node will create a new node put the value key inside it and that node we will return as a root of your tree and we are returning it okay so if the tree is completely empty then we will this particular case will take place else if your tree is not empty and tree is having some values And I want to insert a value which is 2. So, I will compare 2 with the value 10. So, how I am doing it?

If key is less than node key. Now, what is node key? Node's key is 10. If 2 is less than 10, it should go to the left child. If it is greater, it should go to the right child. So, if key is less, then I am going to the left child.

That means I am calling the same insert node function recursively. for the left child with the same key value as the input. Getting it?

And that, jo bhi naya node yahaan pe banega, wo naya node mein, is node ke left mein uska add, So it will point to that particular node. Okay. so it will point to that particular node over here now this is if the key is lesser than node ok if the key is greater than nodes key that means the value to a value 30 is greater than 10 so then I should be going to the right child and here I will call the function recursively ok so if it is greater than node key then I'm going to the right child and I'm calling the insert node function recursively to the right of the right child of the root node and passing the same key to insert the value over there okay so this way it will keep on going recursively in your tree and it will traverse through the entire tree and reach the proper location where you have to actually add a new node so it will reach some of the leaf node where there is nothing on the right and there a new node you will be added say for example in this case i have reached the left of five which is none okay you so left of phi is null now i can add 2 over there so what will i do in that case so there the node will be null so when i reach the left of phi and my node becomes null that time i can create a new node with value 2 and this 2 should be linked to 5. so here this particular function is taking place at some place when your node is null here you are creating a new node with the value key which is provided by the user and that is your returning to the calling function so it will go to the calling function of left because left one called it it was a left child so when it is returning that particular node's address that address is stored in the previous calling function left pointer that means five node left pointer so fives left will hold the address of node two this way these functions are returning and getting connected so in this particular lines what is happening is that your new node is getting added or getting inserted in your avl tree now after adding a new node you may get your tree unbalanced unbalanced means the balance factor is not proper so in that case rotations need to be applied yeah so this next part here update the balance factor of each node after performing insert operation we will update the balance factor of each node and we will check if any balance factor is improper so how do we do that so we are checking the nodes height okay the new node which we added so what will be the height over there that is for each node maximum height of nodes left and nodes right okay so max kisi bhi node ka height kya hota hai uske left ya right me se jo bhi node ka maximum height hai plus one so i will update this height for each and every node then i will update the balance okay so balance is holding the balance factor of any node it will just call the function get balance get balance will give you me give me the balance factor of every node and with this i will calculate what is the balance factor so after adding a new node some critical node will have the improper balance factor say for example in this case a and b was there in my tree after adding c A's balance factor is minus 2 which is a critical node because this is not acceptable. So in this case I should be applying a single left rotation on A.

Okay, so what will I do? Here after calculating balance I will see if any rotations need to be applied. So there are four cases single right rotation, single left rotation, LR rotation which is double rotation and RL rotation which is double rotation. So single right rotation takes place only when when the single right rotation takes place when your critical node has a value which is 2. Yeah, it is positive 2 not negative. So when your balance factor is greater than 1 means 2, 3, whatever.

Okay, so that means yes, this is the case. Your balance factor is greater than 1 and the new node which you are added is the leftmost child. Yeah, so the key or the value which you are added is less than the nodes left key. So, node ke left me jo hai, it is lesser than the node and obviously and the new node is which you added is also lesser than the left child. That means you have added the new node in the left of left.

In that case, we are supposed to apply the right rotation on C. So, what will I do? If these conditions are true, I have to apply right rotation and I am just applying a right rotation for that given node. Okay, and then whatever is the value I am returning to the user. Okay, else if this is not the case, then I will check if balance factor is less than minus 1. If it is less than minus 1 means it is minus 2 minus 3. 3 so i will check if balance factor is minus 2 say for example and key is greater than no whatever is there in the right of node is greater than it and the new value which i've added is more is greater than the nodes right that means i have added the c over here and in that case i should be applying one single left rotation at a so if this particular LL case is there this condition will be true and I will apply left rotation on that critical node okay else if it is a LR rotation how do I come to know LR rotation is the one where your balance factor is greater than 1 that is it is positive value 2 or 3 and the new value which you added is greater than the left node is greater than the left child yes Here it was earlier case it was less than the left child but now it is greater than the left child.

So here I am checking if balance factor is greater than 1 that means positive 2 and the value which you added is greater than the nodes left key. So value is greater than the nodes left key. In that case I should be apply LR.

In LR, on which rotation we will apply first rotation? On the left child of node. so here we are applying left rotation on the left child of the node on the left child of the node I am applying left rotation first and then I am applying right rotation on the node itself on C node so after that I am applying right rotation on the node this is all about the LR rotation next I will check for the RL rotation in this case your balance factor is minus 2 so when your balance factor is less than minus 1 means minus 2 minus 3 And the key which you have added is less than node's right key.

So, is it less than node's right? Yes. So, now I have to apply RL rotation.

What will I do in this case? First of all, right rotation will come on C. Right rotation will come on C.

Means right rotation will come on node's right child. So, here node's right child will be applied. and then then on node i am applying left rotation then on given node i am applying left rotation so this way i am doing with the l rl rotation and at the end i am returning the node that is a root of that tree to the calling function so here we are done with the insert function okay hope you have understood this insert function What we are doing in the insert function if you just look at this in parts.

So in the first part what I am doing is I am traversing through the tree and reaching the proper place where the node has to be added and there I am adding a new node. After adding a new node what I am doing is I am calculating the height and balance factor of each and every node and then I am checking if any rotations are required then I am applying those four rotations. okay this is all about the insert function now let's go and understand the delete function Okay, so here in the delete function, if the tree is given to us and we want to delete a particular value, okay, so the node is pointing to the root node, okay, so now let's see the delete function.

I am taking the root node of my tree and the value which I want to delete that I am taking in a variable key from the user as a input. First of all, I am checking if the root is null, that means the value which you are searching for is not available or else your tree is empty. Okay, so we are returning the root and we are stopping there itself.

Okay, so when we return something, we stop the function, right? Else, if the root is not null, means your tree is not empty, in that case, what will I do? I have to traverse either left or right. So, I will check the value. If the key which you are looking for is less than the root key, okay, suppose I am looking for value 2. If it is less than root key, then I will go to the left, otherwise I will go to the right.

So what it is checking if it is less I am calling the same delete node function recursively and I am going to the left child and I am giving the same key as the input. Here we are calling the same function recursively if it is lesser. Else if the key is greater we are going to the right child and calling again the function recursively. After deleting whatever node is there, it is again giving us value return and that we are saving in the address of right node or left node over here. Okay, so this way we are just traversing in a tree and we are calling this function.

Now, if the value which you are looking for is not available, yeah, suppose I am looking for 2 and it is not available in my tree. So what will happen in that case? I will end up at this particular if condition.

And I will return that value is not found. Because I will return the null value. which is obviously not found okay else case if the value which i'm looking for is found yeah so uh if this if and else if will just help me to traverse to left right left right left right and if once i reach i want to delete node 5 value 5 and i have reached to the value 5 i have reached this node so in that case i will enter the else case you okay now in this else case i am checking okay the node which i want to delete i have reached that node now i just need to delete that node properly okay so when we are deleting something we have to free the memory also and all those conditions okay so here we are checking the node which i want to delete is either having zero child one child or two child so depending on that we will delete and we will replace some values over there so here the first condition i'm checking is If root.left is null or root.right is null, means the node you want to delete, suppose there are 5 nodes, I want to delete the node 5, and whether its left subchild is null and right child is also null, if there is one of the two, then it means, Say for example, the 5 ke right me mere paas 8 hai.

So 5 ke left me kuch bhi nahi hai. Matlab 5 ka left is none. So the node which you want to delete is having single child.

So what I am checking with this particular node is that the node which you want to delete is having single child. is either left is null or right is null. Okay. So, then what we are doing is we are taking a temporary variable and temporary variable will have which value.

So, this is the ternary condition. So we are checking if root left is having some value. That means, jo hum lo ko delete karna hai, usko root ne point karke rakhay. So the node 5 ke left me kuch hai kya? Agar node 5 ke left me kuch bhi hai, if there is some value or some node connected to it, we will have temp storing the left child of 5. But if the node 5 is not having a left child and it is having a right child, in that case, temp will hold the address of right child of 5 getting it so that means whichever child is available either left or right temp will point to that child so now your temp is pointing to 8 getting it So here I am checking if temp is equal to null.

If temp is equal to null, when your left or right child is one of them, then your temp will point that particular child. If left is not there, then it will point right. If right is not there, then it will point left. It is equal. But just consider your root is at 20 and 20 has no child, not on left also and not on right also.

So in that case, your temp... what will it will hold your temp will hold value null because it's both the child's are So we are checking that if both the values are null, okay, so in that case, we can say the node which I want to delete, I have reached that node, but it is a leaf node, it has no child. Okay, or leaf node ko delete karna bahut easy hai. So how do we do that? We will now point to root.

Okay, so temp jo null kiya hai, wo abhi root, matlab is node ko point karega. So temp will also point to this node. Okay, temp is no more null and then I will say root is equal to null this particular Job any delete can I hear no? Poe this come a root Joe's copoint garrison so I'll say root is equal to null that means I have deleted that value When root says null that means that node is no more there and I just need to free the memory so that I will handling Outside the if case free temp so the temp is holding the address of 20 Okay, so it will free that means release the memory occupied by node 20 getting it So this if condition will take place when you are reaching the node Which you want to delete is having zero child else else condition cup true Hoga So I keep us yato left child here to write child head on omiss a quick a key child Hey, the web else major audience so that time the node to be deleted has only one child Maybe it is a left child.

Maybe it is a right child Suppose in this case after node 5 left child was not there but right child is there. So if right child is there your temp is pointing to right child and root is pointing to the node which you want to delete. So what will I do in this case?

I have to delete 5 and right child is 8. So 8 will come in place of 5. That means root's value is 8. will be the value of 10 that means what i'm doing in this else condition is value at root is equal to value at 10 so poora root ka jo bhi values hai ye hum log copy paste karenge and this node 8 will be overwritten on this particular node so automatically 8 and all its child will take place over there and just 5 node we can now you delete okay so in that case i can just free temp because temp was pointing to this node okay so with this we have covered the condition two conditions the node which i want to delete is having zero child or one child now we are coming out of the if condition here and if we reach this else condition means both are not null your left child is not null and right child is not null then we reach the else case and that means the node which I want to delete is having both the two child in that case how do I delete? so whenever I want to delete a node and it is having both the child say for example I want to delete 10 and it is having two child so how do I do that? so I find out is inorder successor means from right side, right subtree, I will choose smallest value which is nothing but inorder successor and that particular value I will replace with the node which I want to delete so now your root is pointing to the node which you want to delete which is having two child ok how do we go ahead so what I am doing is I am taking a temp variable temp is equal to minimum value node we have seen this function earlier what we are doing in this whatever root right node we got root right means we are in 20 we are in 20 So who is pointing to 20? I have passed root of 20. The minimum value from 20, means 20's leftmost, leftmost, leftmost child will be found, which is the smallest. And that smallest value which will return me the function, this minimum value function, that value will be held by my temporary variable.

So temporary variable will point to the smallest or leftmost value in your tree, which is nothing but inorder successor. and this value say for example it is 11 okay so this value now what i'm doing is root key is equal to temp key so root key is nothing but 10 and i want to replace 10 i want to delete 10 so 11 will replace that so root key is equal to temp key so now 11 will come here okay and then whatever I do my job is done 11 has come here I just need to delete node 11 so how do I do that root.write is equal to delete node root.write and its value I gave key of temporary so what was the key of temporary 11 so to delete 11 I called recursive function from where I told its root from root right means I started from 20 so 25 starting a delete function it will go ahead and delete the value 11 which is at the leaf node i'm not starting from this node so this node will not be deleted only the leaf node having value 11 will be deleted so with this i have handled the case where i have two childs and i want to i'm done with the delete uh okay so again in delete function all these things are they are doing what here we are traversing and reaching a node Here after reaching the node we are deleting it properly considering one child, two child, zero child and after deleting the node we have to check the balance factor of the tree. So what I am doing if your root is null then I am returning root that means value which you are looking for is not found. After that I am calculating the height and balance of the node. So I will first calculate the height.

Say for example after deleting 20 I have to change or check what is the height of 10. What is the balance factor of 10. It is changed or do I need to adjust or do balancing over there. Okay. So I will check the root height is equal to okay.

1 plus maximum of left child or right child. Okay, so left or right message of maximum plus one. So I will be updating height of every node. I will be finding out the balance factor for the root node for which we deleted the value. Okay, so now I will check the after performing delete we have to apply the rotations.

So delete rotations are different than the rotations which we apply in insert. So delete rotations are this rotations. That is L rotation or R rotation.

L rotation is of three types L0, L1, L-1 and R rotation is R0, R1, R-1. Okay, so what exactly we are doing in R0. So after deleting a node from the right side, okay, your root node is having a critical node is getting. improper balance factor and in that case the left child yeah so left child of your tree if it is having balance factor 0 then i'm applying r0 rotation what i'm doing i'm i'm just moving the critical node to the right side okay so now let's just check this if balance factor is greater than 1 that means here yes the balance factor is 2 which is greater than 1 and balance of root left is greater than equal to 0 so the balance of root left is equal to 0 so if it is equal to 0 then I will apply R0 rotation R0 rotation only rotates the right side of the root so apply right rotation on that root node means at 20, after this we will perform R1 rotation, R1 is something when we are getting a critical factor 2, okay, and the left node is having value 1, so again this is the condition, if same condition, yeah, if balance factor is more than 1, that is 2 and get balance of roots left is greater than 0. So, if the left value of the root is 40, the balance factor is greater than 0. Yes, it is 1. What will I do? Apply right rotation on root node.

That's why I have combined them together into 1. Okay. So, greater than sign is for R1, equal to sign is for R0. It is covering both these rotations.

And what they are doing? They are rotating only one single right. After that R-1 rotation is little different. So R-1 rotation says you get a critical node having valance factor 2 but the left node is having valance factor minus 1. So then I have to apply two rotations. First is to apply to the left one.

L rotation apply and then root ko right rotation apply karenge. Okay. So now here I am checking the next condition. If balance factor is greater than 1 that is 2. And balance of roots left is less than 0. So root ke left ka balance factor is less than 0 hai.

Yes. So now what will I do? I will apply two rotations.

Pahela me left apply karenge. Phir right apply karenge. Left rotation on root ke left me.

Matlab root ke left kaun hai? 40. 40 ke upar mujhe left rotation apply karna hai. And then root node pe mujhe right rotation apply karna hai. Matlab 50 pe right rotation apply karna hai. So with this after applying these two rotations I am doing this R-1 rotation.

Similarly the opposite case comes for L rotation. L rotation means when our balance factor is less than minus 1, then it is minus 2. And the balance factor of root dot right is less than equal to 0, then it is L minus 1 or L0 rotation. There we are just applying a single left rotation on root.

okay or l1 rotation me kya hoga hamara balance factor minus 2 hai or root ke right me okay the root ka right is greater than 0 that means 1 hai okay so if your balance factor is minus 2 and root ka right is 1 which is l1 rotation i will apply 2 rotation so root ke right pe ham log right rotation karenge and root ke upar left rotation karenge so with this after applying two rotations in l1 we are done so this all are just performing the rotations depending on the balancing required after delete okay and at the end i am returning the root node whichever is there okay so with this we are done with the delete function after delete function there are these three extra functions which are printing the tree or displaying your tree in inorder preorder and postorder okay so this is all same as we have seen in the binary search tree also so i am not repeating the same thing again if you want more details you can just go and watch the explanation which i have given for code in binary search tree okay so what we are doing i am checking the root of my tree as an input and until the root is not null or until i am not traversing to the leaf node okay what will i do i will follow the pre-order what is the sequence in pre-order pre-order is root node first then left then right so that's why i'm displaying the value of root node and then i'm going to in the root left and then right so root left and right is nothing but recursive call of the same function pre-order to the left and right if it is in order that means it is following the pattern is left child first then root then right child So it is giving the left recursive call first then printing the root value and then printing the right. Then recursive call to the right as per the notation Lrv. And what about post order notation? It is LRV.

So left recursive call will go first. Right recursive call will go after that. And third line will be the printing the root value. This way we are just calling this in order, pre order, post order function.

We have done with all the functions. Now let's see the main function. main function i'm just declaring a root variable beginning with the null so i'm just creating an empty tree here and i'm checking this while loop which is continuously running there is no stop for this while loop so here i'm giving this cases one two three four okay insert delete and four to exit so whatever choice user is entering i'm going if case one i'm calling insert function with the value taken from the user if case two i'm calling delete function if case 3 i'm calling all the three in order pre-order post-order and i'm displaying in all the three patterns and if case 4 that means exit i'm calling this i'm writing this exit function which will come out of the while loop so easily i have my while loop condition and then i will return and i will close the main function here so with this we have done the entire code okay okay so now we are done with the program so now let us run a program and check the output so i'm running my code so here i get four options first of all i'll insert say for example 10 then i insert say for example 20 uh so here i will just check my tree 10 will become a root node okay so pre-order my root node is the first one and last one in post order means my train is my root node now if i am adding one more value which is say for example 30 so 10 20 30 will be there in that case my balance factor is not balanced now so i will just display and i will check so now the root node is no more 10 the root node is become 20 you can see in pre order and post order 20 with a start or a last me i i mean 10 will become a left child 30 will become a right child so it is balancing itself properly now suppose i will add value 40 okay and again i display so 40 has become the right side of 30 okay now if i want to delete a value say for example 20 which is the root node okay so after deleting the root node having two child i will just display my tree so now my tree has three values 30 10 and 40 so it has taken the in order successor that is 30 on the right side 30 or 40 30 become the root node and now i can see my tree so here we are the tree is this program is working fine okay so we'll just exit a program okay so thank you everyone for watching this video if you have any doubts you can ask me in the comment box below and do subscribe to this channel for more videos thank you

Transcript for:Understanding AVL Tree Implementation in C

Transcript for:
Understanding AVL Tree Implementation in C