5.27 Insertion in B-Tree of Order 4 (Data Structure)

hi guys welcome back to my channel and in this video I'm going to discuss with you how to construct a b-tree of order 4 so the question is construct a b-tree of order 4 with the following set of data we are given some integers and we are supposed to create a b-tree and that Petri will be having order of 4 ok see the order is for means M value is for the maximum keys any node can have as M minus 1 that is 4 minus 1 and that is 3 ok now see first of all scan this you know this even a set of data from left to right first number is 5 we will insert this 5 into B tree but initially we have you know MPTV tree so one node will be created when node will be created and that node can have maximum keys 3 ok 1 2 & 3 first as first number is 5 5 will be inserted at this position and this node now next is 3c now I have already told you that all the numbers in that node will be you know stored in ascending order or the data will would be in sorted fashion so next number is 3 we cannot put 3 at this please why because 3 is less than 5 so first of all we'll compare 3 with this one 3 is less than 5 ok so where 3 will inserted 3 and here it will be fine fine next s2121 would be inserted at which place greater than 3 greater than 5 21 is greater than 3 and 5 to 21 will be inserted at this place now next is 9 now first of all see it's not like this node is because maximum we can insert only three keys any in any node so firstly we would split this node and then we will insert this nine no first of all we have to find out proper place to insert this nine in this node where you can insert this nine after five means at this place before 21 and after nine three four after five three five nine and twenty one now now see maximum keys can be three only and but in this node we have four keys so what is the procedure now this tree would be splitted in two parts and how this splitting will be done we'll find out the median or you can say the middle element of this node and that middle element would go one level up or you can say to the parent of this node but obviously you can see in this node we have only one no truth note the parent is kakou any in that case that middle element would go on level up and that middle element will become the root or though is take our joining those root K children now see three five nine and twenty one now what is the middle element of this one and we have only four numbers now the middle element can be see even number has a middle element SK those of them five either you can take five as a middle element or you can take nine as a middle element 3 5 9 and 21 sorry either you can take five as a metal element or nine as a middle element if you take five as a metal element then the tree up create guru-guru KOCO five up aperture logica and the left child of five is three the right child of five is 9 and 21 okay if you take nine as metal element then what will happen 9 would go one level up 90 haja again the left child of nine would be 3/5 and right would be 21 and this 1 3 5 and right would be 21 okay both please sir right now this tree is known as left biased and this tree hugger a basically eight kuru Gary if you would create take nine as a metal element and this is known as right biased Applebee's miss a metal element lace-up to take it when you know the order is even in that case it will happen so see let us take five US metal element okay that tree would be left biased how many five core metal element considered here than the tree would be five would go one level up left child off here you can say left subtree of this fight would be only three okay and the right would be nine to anyone fine okay sorry the next number is one nine hundred cooking the next is one no no ha you have to find out the proper position to insert this one in this bee tree and one rule is that any new number will always be inserted in leaf node you cannot insert into root node 1 but firstly we will compare this one himesh a compare Jehovah's yoga insert carrying a tow from the root node compare root node say start over but insert huh Michigan's over our leaf node so one would be compared with this five from a path I 1 is less than 5 so we will go to the left part of 5 now we have tree in this node now this is leaf node the 1 would be inserted at this place but you cannot insert one and in this place why so because one is less than 3 to a 3k left my hand so 2 to 1 cap insert over at this place and here would be 3 now next is 13:13 go Vampiro 13 is greater than five I'm right part Matangi 13 is greater than 9 but less than 21 to 30 in would be inserted at this place 13 and 21 now next is to now find out proper place 4 to 2 is less than 5 from your hapa jiying a 2 is greater than 1 and less than 3 the 2 would be inserted at this place 2 & 3 fine next number is 7 now find out 7 is greater than 5 so we'll go to the right part greater than Heather less than over the left middle now find out the proper place for 7 after that we will split this node okay now 7 can be inserted at this place before 9 because 7 is less than 9 less than 13 in less than 21 obviously the 7 campaigns are to achieve at this place 7 but we cannot insert 7 at this place why so because maximum key any node can hold this 3 only those splitting would be done now splitting seok up key were here middle element find out Kannada kupuna your happy home Natalia the middle element 5 MATLAB tree was left biased okay you have a biopic a leaner middle element 9 Lena 13 carbonyl a certificate trees left by some left element go middle limit consider curvy m3 create carbine take a split current so here 9 would be middle element 2 9 comma PJ I got to to its this node K parent node more you can say one level up to nine copies a notch here you have a 5k position and we can insert nine at this place because Hammadi past maximum k can use up to three and we have only one key now the tree would be five and nine left part of v phase one two and three c9 other one level up Shailaja MATLAB s this node would be splitted in two parts the nine car left child would be seven this one seven up Cuyahoga and the 90 right child kidney only thirteen and twenty one you have 13 and 21 fine next s7 home insert cut sugar next element is in now compare ten with five and nine five and nine say but I had ten so we'd go to the right part of nine okay then you hop insert rows up there now ten can find out grow proper place ten is sorry less than 13 to 10-year happens hurt over ten after that you have had 13 OD hompage a cop car 21 fine next is 12 now find out find out proper position for 12 12 is also greater than this 9 to him right partners hang it while you're happy Kehinde set ho sakta hai after 10 and before 13 so 12 of cahuachi at this place - el 13 in 21 Yahoo notch a but you cannot insert this at this place why so because maximum key is happening evening or something a 3 so splitting would be done splitting call the middle element middle element here / 12 left biased have not read well o 13 layers at they become left biased become Quran 12 Kohi consider occurring as my daily limit take that middle part middle element would go one level up and you can say to its parent no disc apparent node have 5 for 9 in this node so 1200 I skip Assam Toya I insert cursive theme because one place still we have left now the tree would be may see me update career develop a hot July of ever 12 commercial again this node will be splitted in two parts 10 would be the left child of 12 okay - lk left make our hagar a gap new pass only 10 or 12 your right part to make a happening pass gas at 30 knots 21 take a 12 right path now next is 4 now compare 4 is less than 5 205 cut your left part our Hodja in your for copper your high insert corner for a coin circles after one two three after three four up coins our community visa to Yahoo together but come in sir disco carnies at the because obviously maximum company through subhansin splitting would be done splitting my middle element middle element emits piss considering is too cool then to would go 111 upper you can say to its parent node see I got to have got to Jagger at this place to a guru pers I got through obviously apna five say less than Heather you happy insert or not you to five nine and twelve but here also we have you know that this note is also full because three key already here so we cannot put two at this place so yeah happy be again yeah okay splitting movies after come proper find out any curses cuddle a position to splitting again and again ho today yeah by splitting way to Korea very happy Jaya in that case yeah be splitting movie appeal or Ajay part split okay Kafka the middle element will go one level up to its parent node parent any to the middle element won't become the root of this tree now this middle element is Co considering if v go because trees have now left biased so the tree would be five five up now partial again this node would be splitted now then what is the left part of five this to fine and what is the right part of this five right children nine and this five got nine and twelve ticket now come to this level up took a left part yoga to forget a to took a left part mega hope now only one we have only one what is the right children of two three and four you have your right can be up K three and four ticket see seven copies I got seven o'clock I have five cigarette within her to five K right part of me he's on a TV but 9 K left me here to you 9 you're happy Niner this car left part media hog only 7 now 10 is the right children of this 9 9 K right make a solid a gap now this one 10 and 13 and 2 LR this right part of actual children of this 12 right sub-tree or you can say 13 and 21 fine the last number is 8 now find out the proper position for it where you can insert this 8 compared with this 5 8 is greater than 5 then we would go to the right part of this 5 take a now compare it with this place you see you cannot insert it at this node because why so because you cannot you cannot insert you know any newly coming number into the internal nodes you can only insert the data into leaf node okay now it would be compared with this one now 8 is less than 9 to hommies 9 ke ke left part measuring you okay see now this node is leaf node fine yep Naga has 7 leaf nodes can eat a scale ft apart right part which mean a now find out proper position 4 8 8 is greater than 7 throw it up campaigns are to get this place fine next up nahin e so this is the final B tree of order 4 fine another variant is say this is also right another variant is that right biased tree you can take this 9 as a you know middle part and you can put 9 at this place 3 5 at this place into and 21 at this place like this you'll proceed and that one another tree would be there though jo aapke even number what the hair that order is given with this even number to up K 2 3 is possible have one is left biased and one is right biased fine so I'll see you in the next video guys till then bye bye yes