1
$\begingroup$

I can calculate this by trying out manually inserting $n$ keys in $m$ order B Tree as follows:

  • Assume median to be selected for split be left biased. That is $m/2$. For example, if $m=4$, then a node [1,2,3,4] need to be split with 2 as a median and resulting in nodes [1] and [3,4]. So, we selected 2 as a median, whereas 3 could also be the candidate for the median and 2 is on left of 3, so "left biased". (I just made up the term "left biased median" for convenience, it might sound bad) Left biased median will leave more keys in right child than left child.
  • Insert elements in increasing order, which will further result in insertion in right children nodes, which were already more filled in comparison to left children due to left biased median.

For example, if $m=4$ and $n=10$, and we insert keys:1,2,3,4,5,6,7,8,9,10, then there will be 5 splits as follows:

Insert 1,2,3
=================
[1,2,3]


Insert 4
============
   [2]
   / \
[1]   [3,4]      (Split:[1,2,3,4]) 


Insert 5,6
===============
   [2,4]
   / | \
[1] [3] [5,6]      (Split:[3,4,5,6])


Insert 7,8
===============
    [2,4,6]
   / /   \ \
[1] [3] [5] [7,8]    (Split:[5,6,7,8])


Insert 9,10
===============
        [4]
       /   \        
     [2]   [6,8]
    /  |  /  |  \
 [1]  [3][5][7] [9,10]    (Split:[5,6,7,8],[2,4,6,8])


Total splits: 5

However, can we derive the closed formula (if not closed formula, then a summation series?) for this for given $m$ and $n$? It seems that splits are occurring on every two insertions, but how can we capture in formula, number of splits that occur for each such iterations?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.