GATE CSE 2003 | Question: 65

Question

Consider the following $2-3-4$ tree (i.e., B-tree with a minimum degree of two) in which each data item is a letter. The usual alphabetical ordering of letters is used in constructing the tree.

What is the result of inserting $G$ in the above tree?

• A.
• B.
• C.
• D. None of the above

Comments

Why??

If we observe then here we can say right biasing is done right??

---

@mahendrapatel in option A, at leaf node when we insert G right biasing is done and G we took as parent node we get GLPU, but as you can see root node is P that suggest left biasing. 
But both right biasing and left biasing both cannot be there in same tree. That's why option B is correct as only, left biasing is done there. 

---

You have to follow consistent biasing, if choosing to be left biased then split all the nodes based on the left biasing through out the tree and all the insertions and all the splits. You cannot choose left bias for one split and right bias for another.

And that is why option A fails and option B wins

Answer 1

(B) is the correct answer.

Once we add $G$, the leaf node becomes $B \ G \ H \ I$, since we can have only $3$ keys. the node has to split at $G$ or $H$, and $G$ or $H$ will be added to parent node.

Since $P$ is the parent node in options $1$ and $2$, its evident the $3$rd element i.e. $H$ should be selected for splitting (because after adding any key from the leftmost child node, $P$ becomes the $3$rd element in the node)

Now parent node becomes $H \ L \ P \ U$, select $P$ as for splitting, and you get option B.

Hence, answer is B.

Comments

Absolutely Correct bro.

---

But why we can't conclude by seeing tree that it is right biasing and right biasing has been done

---

@gaurav_kumar bhai I'll only upvote you due to following lines let's support if any newbie is hitting this questions,

 

only your's comment must float on their eyes.

 

have followed Left Biasing at both split

 

Answer 2

If we consider this just as B tree, order of tree is 4.

Because minimum degree is 2.

Then m/2 = 4, m =4. (As it is upper bound, m can not be 5, m = Order of tree.)

If we insert G leaf node B H I becomes B G H I. As we can have maximum 3 keys in any node, we split it. G Goes up !

Then root becomes G,L,P,U.

Then We need to split root. L becomes root.

Answer -> D

Comments

When we get BGHI, why can't H go up? How can we say G must go up- because both are median. 

http://faculty.cs.niu.edu/~freedman/340/340notes/340redblk.htm

---

@sir one confusion. what I thought about spliting of nodes when there were one exact middle element was possible was . we just follow any convention like 2,5,6,7 . either we can send 5 to root or 6 to root. but have to follow the convention in the whole tree. whether i am right in the case of b tree. ?? or we have to see the median as stated in the pdf everywhere. ?? and sir i have one confusion two . first split like given ,

53,27,75,25. to decide we have to take the median of elements  . i.e (27+53)/2 = 40 so left side should be less than 40 and right side should be grater than 40 . so again i have two choices sending 27 or 53 both satisfy the property . they have send first 53 . but when again such case happened they send the second element . plz clarify .

---

@Arjun sir iam also having the same doubt.. i have drawn 4 possible trees  and 2 of them are in options..Now which one should we consider in the exam..Need your advice

---

brother if you are following right biasing so in whole tree you follow that only same goes with left biasing , in above the 2nd and 3rd diagram of yours are incorrect , in 2nd diagram for BGHI you are following left biasing and for GLPU you are following right biasing and in 3rd diagram you are following righ biasing for BGHI and left biasing for HLPU.

Answer 3

option C

first of i will like to say why do we use a btree :to reduce the height of a tree to narrow down our search procedure ...so wont you tree to reduce the height if there is any possibility ..inserting G would cause the leaf node to split but we have a possibility to not increase the height by splitting the root .. the possibility is redistribution i.e the sibling of the leaf node we are spliiting is empty so why not use that empty slot to save a height increase

Comments

Ya, I too agree with option c). Don't understand why no one is considering this fact !! i.e redistribution and also min no of keys must be two in a node

---

if you read question carefully then you understand that minimum degree is 2 .And degree  or

order in B tree means maximum no of block pointer or child it can have and maximum keys is

 given by degree-1 or order-1 in a B treee..

Answer 4

Answer: C

After inserting G into the first child.

Option A: Involves splitting.

Option C: The second child has less than 2 keys and the first child is full. That means rotation can be done without affecting the root node. The rotation involves pushing I into the second child. Now the first child is BGH and the second child is IN.

Option C is more apt here.

Answer 5

Answer by images

Answer 6

b is the corect ans

when ever u instert an in ele g it is out of capacity so we push middle h into root then root also going out of capacity so me take middle ele and we form a root p

in option a first first 2 ele is pushed and in root 3rd ele is pushed