1 votes 1 votes 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 Vasu_gate2017 asked Nov 4, 2016 Vasu_gate2017 707 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply dd commented Nov 4, 2016 i edited by dd Nov 4, 2016 reply Follow Share ............. 0 votes 0 votes dd commented Nov 4, 2016 i edited by dd Nov 4, 2016 reply Follow Share 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$ 0 votes 0 votes dd commented Nov 4, 2016 reply Follow Share @Vasu_gate2017 please share your approach ! 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes @debashish deka.... I solved by drawing and observing pattern in b tree Vasu_gate2017 answered Nov 4, 2016 Vasu_gate2017 comment Share Follow See 1 comment See all 1 1 comment reply dd commented Nov 4, 2016 reply Follow Share ok ! brute force ! thanks ! 0 votes 0 votes Please log in or register to add a comment.