+17 votes
2.6k views

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

asked in DS
edited | 2.6k views
+1
Option B is correct.
0
main observation in this question is that , when we have four sorted key BGHI , we can choose G or H but what to choose is initially ambiguous but when either G or H goes to root , root will become GLPU or HLPU , now again we have 2 choices choosing L or P for split , but looking at options it is clear that P(3rd element in list) is selected for split which implies that initially H(3rd element in list BGHI ) should be selected for split
0
this question is not in gate overflow pdf ( vol 3 ). may be it will be added in future

## 6 Answers

+15 votes
Best answer

(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.

answered by Active (3.6k points)
edited
+2
A & B both can be the answer .

Why making H as a parent of BGI , it can also be G as parent of BHI .In the 2nd level it can be GLPU or HLPU , so P & L both having a chance to become root .According to the given option P is the root , GL & U as the immediate child fits corectly . How can we ensure option A is wrong otherwise ?
+1
Mansingh. If G or H goes up, the order is : GLPU or HLPU. Now in both options 1 and 2 it is given that P is the root. Now P is also the third element in the ordering, which means the 3rd element goes up and hence H being the 3rd element in BGHL will go up, making B the ans and not A.
0
why not option C??
instead of splitting we can redistribute the the nodes
+1
@mansingh it will be either left biasing or right biasing but not both at a time
0

@ryan sequeira

Why option (C) is not correct ?

+6 votes
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
answered by Boss (43.6k points)
+2

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

0
@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 .
+3 votes
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
answered by Boss (14.5k points)
0
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
+2 votes
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.
answered by Boss (33.8k points)
–1 vote
a) after insertion, leftmost node becomes BGHI,  node splitting takes place so G goes up, LPU becomes GLPU. further splitting moves P to top, producing the tree as given in option a.
answered by Loyal (8.2k points)
–2 votes
Answer is c.
answered by Active (3.3k points)
Answer:

+30 votes
5 answers
2
+25 votes
9 answers
4
+10 votes
2 answers
5
+33 votes
9 answers
7