Insert 1,2,..,20 numbers to the empty B tree sequentially. Write a formula which calculates the number of elements in B tree root after every i-th insertion. The first part I did, but I'm having trouble in the second part.
Here's what I did.
Let N be the maximum number of elements in the root of the B-tree.
If i ≤ N, the formula is: R(i) = i.
If N < i ≤ 2N, the formula is: R(i) = N.
If 2N < i ≤ 3N, the formula is: R(i) = N + 1 and so on.
But by checking against the answer key, it seems I've done something wrong. Can you revise my solution and correct if it's wrong?
There are different insertion algorithms for B-trees, and the results you are looking for depend on them. I will here assume there is no pre-emptive splitting, and when a node is full there is no attempt to delay splitting by moving keys to sibling nodes.
Let's look at your statements:
If i ≤ N, the formula is:
R(i) = i.
Correct.
If N < i ≤ 2N, the formula is: R(i) = N.
Not correct. When 𝑁+1 is inserted, the root node splits into two nodes with each 𝑁/2 keys, and one value is pushed up to become the only key in a new root node. So at that time R(𝑁+1) = 1. For example, if 𝑁=4, then before inserting 5 we have:
root:
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
└───┴───┴───┴───┘
Then after adding 5, we get:
root:
┌───┬───┬───┬───┐
│ 3 │ - │ - │ - │
├───┼───┴───┴───┘
┌─────┘ └─────────┐
┌───┬─┴─┬───┬───┐ ┌───┬─┴─┬───┬───┐
│ 1 │ 2 │ - │ - │ │ 4 │ 5 │ - │ - │
└───┴───┴───┴───┘ └───┴───┴───┴───┘
If 2N < i ≤ 3N, the formula is:
R(i) = N + 1
That should have raised an alarm: a node could never have more than 𝑁 elements, so obviously 𝑁+1 is wrong.
After the tree has received its second level (so when 𝑁+1 has been inserted), there is a sequence where the left side leaf node is filled, splits into two, adding one key in the root, and again the left side leaf node is filled, ...etc. At a certain moment the root gets full and splits into two, to get a tree with 3 levels and only one key in the root.
You may want to draw this on paper and see the logic.