503 views

Order P=5 ( Max Child pointer )

If Keys are inserted in the sequence of 1,2,3,4,5...................Then which is the 1st key insertion that leads to level 4

(i) B Tree

(ii) Left Biased B+ Tree

(iii) Right Biased B+ Tree

edited by
.............
edited by

For B TREE:

Insertion sequence 1,2,3,4,5,6,....

For $P=5$ internal nodes will be filled with 2 keys and produce 3 pointers for the next level except the rightmost nodes which will be full with respect to the required criteria.

We have x levels and a new key K , is going to be inserted. Because of that a new level $(x+1)$ will be initiated. In this configuration following recurrence relation holds.

• No of child pointers from $n-1$ level to $n$ level is $\text{F(n)}= 2+3. \text{F(n-1)}$ for $n > 1$ with $\text{F(1) = 1}$
• No of keys in nth level = $\text{F(n)} * 2 + 2$

So,

• No of keys in 1th level = 4
• No of keys in 2th level = $\text{F(2)}*2+2 = 12$
• No of keys in 3th level = $\text{F(3)}*2+2 = 17*3+2 = 36$
• Till now $(4+12+36) = 52$ distinct keys inserted.
• $\Rightarrow$ next key $K = 53$

@debashish deka.... I solved by drawing and observing pattern in b tree

### 1 comment

ok ! brute force ! thanks !

1
136 views
1 vote