edited by
9,914 views
30 votes
30 votes

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?

  1. None of the above
edited by

7 Answers

Best answer
25 votes
25 votes

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

edited by
8 votes
8 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
3 votes
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
2 votes
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.
Answer:

Related questions

46 votes
46 votes
6 answers
1
42 votes
42 votes
3 answers
2
Kathleen asked Sep 17, 2014
14,796 views
Consider the following functional dependencies in a database.$$\begin{array}{|l|l|}\hline \text{Date_of_Birth } \to \text{Age} & \text{Age } \to \text{Eligibility} \\\hli...
42 votes
42 votes
4 answers
3
Kathleen asked Sep 16, 2014
8,885 views
Consider the following SQL querySelect distinct $a_1, a_2, …, a_n$from $r_1, r_2, …, r_m$where PFor an arbitrary predicate P, this query is equivalent to which of the...