5.20 Splay Tree Insertion | Data structure

so in this video we will see insertion in split rings see in the previous video we have discussed what is splay tree advantages and drawbacks of spear trees and applications of splay trees and how splay trees are different from other balancing binary search trees so you can check out that video in the cyber turn right and in that video also we have discussed that how to perform searching operation in splay trees what is splaying operation right in this video we will see the insertion operation in splay trees right after that after this example we will see we will write down the code or you you can see we will write down the algorithm for insertion operation as well as for displaying operation means first of all you will discuss it with the help of an example you will create a splay tree by inserting these numbers and then we will write down the algorithm for insertion operation as well as splaying operation right now see as we have discussed in the previous video all the basic operations that we can perform in BST like search insert and delete those operations will be performed in splay tree and the processor will would be same as in BST the difference is what those operations are are going to be followed by one basic operation of splay tree that is splaying operation right now in this case also first of all you will insert the data and then we will loose playing splaying means the data we have inserted on that data on that element we are going to perform splaying operation means now we are going to make that inserted node the newly inserted node as the root of the tree right and why we are going to make that element the root of the tree that we have discussed in the previous video because it's it's because that advantage of the Splane tree is what because of this step only the most frequently exist elements you know move closer to the root so that we can easily or frick quickly we can access those elements right now first data you want to insert is 15 right so obviously this is a BST self-balancing bsts 8 is a self adjusted BST it is roughly balanced not strictly balanced really so first of all you will create an or and after that you will insert that thing in node we have what the data that is the value 15 plus the left pointer plus the right pointer I'm not here representing the node right and I'll just write down 15 the data of that node only right now initially there is nothing in the tree so what you will do we will insert 15 and we will create a node and we will simply insert the 15 in the tree and now you displaying explain on this data on the data on which you are going to perform the operation that is insertion operation so 15 is the data you want to insert and 15 is the root in splaying we will make this as a root but this is already root so no need to do anything right now next is what 10 now simple BST insertion first of all you will do compare with this one 10 is less than 15 so where you will insert here to the left of this 15 right now this is not done in splay tree now you do what splaying playing on this data the data you have inserted that is 10 means now we will make this 10 as the root of the tree how we are going to make this as a root of a root of the tree what is that playing operation check if the this the newly created node or this is what this the data on which you want to do splay operation is what having parent only and the parent of this is what root means this is not having any grandparent so this is what a zigg situation right now check out this is a left child or right child so this is a left child of this root so we will do it right rotation or you can say Zig rotation right this these rotations we have already discussed right rotation about this parent parent of this node you have inserted so right rotation means we will pull this 15 downward and 10 would go upwards so now this is the tree after insertion of this 10 splay tree right next is 17 insert 17 industry say that BST insertion greater than 10 greater than 15 so here you will insert 17 but now you will do splaying operation on this 17 we will splay the 17 now check 17 is having parent as well as grandparent now this is what and 17 is to the right of its parent and 15 is also to the right of its parent means on the same side both this node and parent are on the same side right either maybe left or right but here these are on the right side so this is what a situation of zigzag situation right now here first of all you will do what to left rotation you need to do to make the 17 as a root so first rotation would be about this grandparent next rotation would be about this parent see don't get confused that first rotation would be about this parent and then this no in this situation first rotation would be about this grandparent of the newly inserted node so now left rotation means we will pull this downward and 15 would go upward right after first left rotation again left rotation around this 15 of 17 would go upward 15 and here we have n now this is the tree after insertion of 17 now see this you can say a zigzag situation or a zigzag rotation sorry right somewhere it is written that the left rotation we have already discussed is egg rotation the right is Zig rotation right but somewhere both the cases are taken into one situation that is zig zag situation so it is what zig zag but you can say left rotation situation fine it's up to you how you will write either a zig zag situation or a zig zag left left rotation both are correct right now this is the tree now here you will insert 7 how you will insert 7 compare with the 70 in less than 17 less than 15 less than 10 so now here we will insert 7 now splay the tree so display this seven right because you need to make the seven as a root of the tree now check seven is having parent as well as grandparent and seven is left child of parent and this parent of seven is also left child of its parent right both are on the same side so it is a zigzag situation here first of all two right rotation you need to do if these are left child means right rotation here these are right child so means a left rotation so two right rotation you need to do now first right rotation would be about this this one fifteen grandparent of the seven so now the tree would be seventeen you will pull this fifteen downward and ten would go upward so after first a right rotation tree something like this now again a right rotation around about this in so will right rotate to this means ten would go downward and seven would go upward so now here we have seven ten this side and this side fifteen but we are not done yet because seven is still not root now check which case you need to apply now seven is having the parent of seven is root node means this is not having any grandparent now so this is what I was igg situation now check it is left cell or right child of the root it is left child of the root so do right rotation right rotation about this parent so right rotation means we will pull the seven downwards sorry 17 downward and seven would go upward so now here we have seventeen now see after pulling the seven downward now seven is here now the right child of seven is 10 the right child of seven is where this 10 would go the right child is now 17 so it would go to the left of ten and fifteen would be as a teaser as the and the right child of the stem now this is the final tree after insertion of seven so this is what you can see a physic situation was a groat asian now we will insert 13 compared with this one simple BST insertion first of all you will need to perform greater than say less than 17 greater than 10 less than 15 so here you can insert 13 now it's playing on this elements play the studying now see 13 is having parent as well as grandparent but this is a zigzag situation why so because this and this both are in opposite direction one is in left direction one is in right direction this is not this case that both are in same direction so it is what a zigzag situation now you need to check out which rotation you need to apply a left or right first of all see this is the node this is parent or you can say this is grandparent G you can say right now 13 is to the left of 15 first of all if this is the case that zigzag situation is there then first we will perform the rotation on the parent only not the grandparent here we perform rotation on grandparent then parent right don't get confused in this scenario right now first over will perform rotation on the parent now this is what left child off parent so we will do first of all right rotation on this parent now the tree would be something like this right after first right rotation now we will do left rotation right because it is a zigzag situation left rotation on grandparent on G so now the tree would be something like this left rotation means we will pull this 10 downward so 13 would go upwards so now here we go 13 here we have 10 and here we have 15 but we are not done yet because 13 is still not root node because we have to make this 13 as root mode because we are going to perform insertion of 13 right so now 13 would be root more so now what you will do see now 13 is having parent as well as grandparent now it is also a zigzag situation right so now because both are in opposite direction one is left one is right so 13 is to the left of parent so first of all right rotation on parent right Zig rotation so now that we would be something like we will rotate it something like this so 13 would go upward 17 would go downward and here we have 10 now see 15 is to the right of 13 so it will go right of 13 and left of 15 but we are not done yet now zeg rotation means now 13 is to the right of 7 now zeg rotation means left rotation on grandparent so now the tree would be something like this see here the left side of 13 is 10 to the left of but today it will go to the right of this 7 right so now this is the tree after insertion of 13 now insert 16 industry where you can insert 16 see greater than 13 less than 17 and greater than 16 now here you can insert 16 right now see which rotation you need to do here we have the 16 is having parent as well as grandparent now it is the right child of this one and this is the left child of this one so both are in opposite direction so this is also a zigzag situation or here you can say this is zigzag situation both are correct right now see 16 is to the right of this 15 so we will do first of all left rotation on parent right so now the tree would be something like this left rotation on parent so 16 will go upward and here we go to 15 now we do right rotation on 17 on the grandparent so now the tree would be something like this but we are not done yet because 16 is still not the root node we have to make it root move not check 16 is having only parent not grandparents because 16th parent is root node now this is the situation of only zyg rotation right now here you need to check which left or right rotation so 16 is right of 13 so we you need to do left rotation but you can see here zig left rotation or you can say a seg rotation so now after this rotation the tree would be see here the 16 is left child of 16 is 15 means left child of 16 it will go to the left of 16 but here we have 13 so it will go to the right of now this 13 that is so now this is the final tree I guess we are left with 10 see here to the right of 7 we have n so here you will write 10 to the right of 7 we have 10 and here also to the right of 7 year 10 so this is the final tray now after inserting of this data so now I hope you got how to do insertion splay trees now we will write down the algorithm for insertion operation right and then we'll write down algorithm for splaying operation fine so now we are going to perform insert operation on the tree T and n is what and is the number or the node I want to insert see here n is not the data that is 15 here n is what the complete node in which data part is 15 here we have left pointer here we have right pointer but I am NOT writing this thing simply n means this node you need to take care of this thing right here suppose now I want to insert after the 16 I want to insert 14 so same the BST insertion process and we are going to follow first of all we are comparing we will compare with this root if this is less than root then we will go towards this one the left side and like this if greater than then we will go towards the right subtree right so this thing you will write down here this is same as the BST insertion so suppose I am taking on m variable and there I am storing the root address right T dot root something like this you can write and I'm taking another variable Y and there I am storing now why you are taking this Y this thing you will get cleared further now see now we will write down a while loop while temp not equal to null if you write down the algorithm and simply you can write down this thing right temp not equal to null see in till 10 we are going to move either left or right it depends on the value of this the value you want to insert right so first of all you will set Y is equal to 10 so now I will write if the data you want to insert that is n of data and I you told I have told you this is a node and the data part is having 14 here we have left pointer right pointer now this this is having null this is also not so n of data is less than temp of data right now see here we have temp because temp is equal to T of root root is this one so temp is a variable which is containing address of this root temp is not containing 16 temp is a pointer variable see here I have already told you if I am taking n this is a node temp is what I am taking a complete or you can say pointer variable pointer to node Y is also containing address of these nodes right if the 14 is C temp of data is 16 14 is less than so we will go to the left right so now temper becomes temp of left whatever the value in temp of left that address would be stored in temp right so now you can say temp is pointing to here right and now C else else you will do what temp is equal to temp right else we will go to the right side fine once you reach where you want to insert the data suppose once you here I want to insert 14 so once you reach here so now you you'll write down what here after this while loop after this while loop you will write this n dot parent is equal to Y now see why you we are writing this thing initially temp is this one right so now while temp not equal to null amp is not null because it is containing address of root node Y is equal to M now see Y is equal to temp now tempo is this one so Y is also now this one Y is also containing address of the root node right now comparing of data is 1414 is less than temp of data yes now temp is equal to temp left so temp becomes this one right now again while temp not non yes temp is not null temp is containing address of this node temp is not null now again Y is equal to M now Y becomes here now why is this one right now temp is equal to temp left so now see check n of data now n of data is about 14 less than temp of data temp is this one temp of data is 13 but this is not true so we will go to the else part that is temp is equal to temp right now temp is this one temp right means this one now temp is a containing address of this note that is 15 now again check member is not not yes now Y is equal to temp now Y becomes temp that is why is this one so now check if n of data animal data is 14 14 is less than temp of date and our temp is this one temp of data is 15 yes the condition is true so temp is equal to temp left now temp is equal to temp left so here this node is having M depth is equal to not because this is not having any left or right child so now temp is pointing to null so now you can say tempis here temp is null right because this is not having any left child or any right shine so now temp is now now again check the condition temp is not null but this condition is now more true because temp is null so we are going out from we are going to exit from this while loop and the after this while loop we have the situation right so now you have would the location where you can insert the 14 it means 14 would be child of this 15 this is for sure either left or right child and so that is why I'm tracking this Y so n of parent and it's 14 parent of this 14 would be Y C Y is right now containing address of this node that is 15 node and that is for sure because 15 would be parent of this 14 right so now Y is what parent of this 14 if still Y is equal to null means the parent of 10 is null so n is not having any parent here you can say root would be that element which is having no parent so no need to do any we will simply return and we will not do any splaying operation right so here you will check if still y is equal to is equal to null after checking this then we will set T Oh fruit would be and right only one element we have that is this one that is this case 15 case initially that he was empty so we will insert 15 so 15 would be root right no splaying would be done if Y is not null now else if we're to insert this 14 2 to the left or to the right where you need to check now we will check hence if this n of data is less than Y is this one y of data so this n would be the left child of this Y so here you will set in the left pointer of Y we will store the address of the newly created node that is n right hence Y of right is equal to n now insertion is done and now we will call what display on this tree on which element on the data you have inserted on the node you have inserted that is n see here the n is what this address address is suppose hundreds so n is what the address would in the Y of left means Y is also address Y of left is this one suppose this is y y is data part of Y is 15 here the left so in the left part we will store 100 right so here we are you know considering it as a address not the value when you if you want to access then you need to access something like this n of data right so here also you can write this error or something like this fine now we will see the algorithm for this splay operation I'm going to rub this one and now we will insert see here we have inserted this 14 after this algorithm to the left child of this 15 now we will do splaying on this 14 because 14 you need to make this 14 as a root of the tree now so now this is the pre after insertion of this 14 now we'll lose play on this 14 right so we will do the algorithm for this play playing of the string on the N and node is what 14 right now we will check all the cases of us play suppose this 14 would be the root initially if suppose we have inserted 14 only one element then 14 would be the root so no need to do anything we will do is playing telling this 14 becomes root so we will write down a loop while a no-parent is not null because if the parent of this node is null it means that would be the root node because root is 2 root is not having any parent right what here you can check while you can write way while n is not root node till then we are going to do some splain now what you will do now we will check if if the parent of this n is root node in that case either you will do zig-zag rotation means only one left or only one right rotation that case may be there right so now here you will write what if n of parent is equal to is equal to T of root means both are same right the parent of n is rude suppose taking this example the parent of 13 is root so here you will do what only one right rotation but if this is the case then we will do only left a rotation left or right rotation on this one parent or you can so on root of the tree right so now here also we will check now if n is equal to is equal to n of parent and enough parent means this one so we will check whether n is left side or right side according to that only we will decide we will do left rotation or right rotation so now if this is the left child suppose it is left then we will do one right rotation so here you will write right rotation on the tree on which on the root or you can say on the parent of this n so here you can write you can pass parent of n else else obviously we will do left rotation now this is one case second you said this is one case there's a second case now third case is having four sub cases that is if the N is having parent as well as grandparent now what you will write here C so now this this part is within this if now we have else for this if right else we have parent as well as grandparent so suppose I am taking P is equal to n of parent and G is equal to P of parent so P is parent of n G's grandparent of 10 right so here you can say n is this one parent is this one and grandparent is this one so G would be this one right now we will check the four cases if now here both N and P are left child means suppose here I'm taking seven is n so P parent four seven seven is this one grandparent parent is this one so both have left child it means we will do two right rotation first right rotation on 16 then right rotation on thirteen right so here you will do or simply here you can write if you will not write at this condition in elbow you can write in your simple English language if both N and P are left child or this is the same condition C n of parent and is this one n of parent is this one parent of left means this one only so n would be the left P of parent and left would be P so here you will do two right rotation first right rotation would be on G and second right rotation would be on P this thing you need to take care first of all their own grandparent then parent now else if both and NPR right child that could also be a case so now here you can write in this case we will do two left rotations first left rotation would be on grandpa and then on Baron now third case maybe now suppose I'm taking this case now n is what left child of P but P is what right child of G so here what you will do it is a zigzag situation these are these two are zigzag situation fine this is simply Zig situation right now here first of all we will do right rotation on parent because this n is what left child of this one so right rotation on parent right and after that we will do left rotation on grandparent so see now after the rotation the tree would be something like this now again left rotation you can say zag rotation on this grandparent so now the tree would be thirteen would go downward fourteen would go upward right but still we are not done because obviously I am taking this in while loop so end of parent now n is this one and of parent is no Tinnell so again we are going to follow steps whichever if condition is true that condition we are going to follow now here what you will write else if n is the left child and parent is what the right child then first we will do here right rotation on parent then we will do left rotation on grandparent 1g right hence forth cases only left cases what this n is what the right child and parent is what left child so in that case no need to write down that condition simply first of all we will do left rotation on parent then right rotation on grandparent opposite to this case so this is the elbow force plate now here see this is not yet done now again the while loop we are we are writing these in while loop so while n of parent a knows not now I know parent is not null so again check if a no-parent ut-oh fruit yes and of parent is now root yes so now we will enter into this if condition not in else condition now we will check if this is a left or right child it is left child right so we will do right rotation on end of parent and no parent is this one and here we will do right rotation right Mason this is a zigg situation so after right rotation the tree would be finally would be here to the right of 14 we have 15 so it will go to the right of 14 and to the left of 16 so here we have 15 so this is now the final tree after insertion of this case now see here also the right rotation and this left rotation are also function so you need to write down coding for this right rotation as well as for left rotation so let us write down the steps for the left hand right rotations as well now see let us take example of this right rotation right rotation of T and n of parent will be passed so in this case suppose I am taking this scenario end of parent is 16 so the address of 16 will be passed and Here I am receiving that addressing X right that is a pointer variable it is not simple variable a pointer variable you need to take care of this thing fine now this is X right now what you will do now I am taking this also because this is what n right this 14 I want to make the root node so we have to store address of this also so now this is what X of left right X of left is address of this 14 so you can store that thing in a another variable that is why Y is equal to X of left so Y is a pointer variable which is containing the address of 14 so this is y now how to do right rotation now see steps are after right rotation see you can check the 14 right child is 15 now 15 become left child of 16 means this 15 become left child of X right now I'm writing this step so how you can write down this thing see X is this one right so X of left should contain should contain Y of right yes you can see here X of left containing Y of Y Oh fried that is 15 now next what you need to do now see we have break broken this link right so now here X of left means X of left is now containing this one address off Y of right sorry we have broken this link note this now we have to set this link right means how we will set this link now the right of 14 see the right of 14 would be containing address of X so here X we will store in Y of right and we will return we can return Y right address of this Y node C these are Y and X these are pointer variables so don't get confused I am taking these as a variable so I'm not saying that this is a correct I'm writing a correct program you need to take care of this thing right now how to do left rotation how to write down steps of left rotation see here you need to take care first of all you need to check this link if you write down this line first rather than this one then see Y of right is equal to X means Y of right is equal to X so this is the link and you have broken this link right so now from where you can get this link of 15 so first of all set this link after that second this link you need to take care of this thing also now what about left rotation suppose here I am going on to do left rotation on this 14 right I won't display 16 right 16 is right child so I want to do left rotation so after left rotation the tree would be something like this see the left child of the 16 left child of 16 and it would become the right child of now the 14 so I guess you can easily write down this encoding first of all set the sling after that you can set this link the left side of the 16 so now same here X is this one we are going to pass this 14 address because we are going to do left rotation on this thing now we will set first of all why Y suppose Y is 16 that and that is why I am taking left rotation I won't display 16 so now we will set Y is equal to X off right right now we will set the link for this y of this left child so now Y off left now become the 15 become now right child of 14 that is right child of X so X off right and now simply you can set what Y of left would be X and you can return Y see these are pointer variables these are going to return address of these nodes not value of the nodes right so this is all about insertion in splay trees in the next video we will discuss how to do deletion in Spade rays well so in the next video till then bye-bye take

Channel: Jenny's lectures CS/IT NET&JRF

Views: 49,105

Rating: 4.8565736 out of 5

Keywords: data structure tutorials, data structure and algorithms, insertion in splay tree, splay tree insertion in data structure, splay tree in data structure, splay tree insertion example, what is splay tree in data structure, ugc net computer science preparation, gate cs lectures, jenny lamba, jayanti khatri lamba, jenny data structures, jennys lectures, jenny's lectures cs/it NET&JRF, tree in data structure, what is red black tree in data structure, operating system

Id: 1HeIZNP3w4A

Length: 34min 26sec (2066 seconds)

Published: Thu Nov 14 2019