B-tree Node Split Decision

Problem

Decide whether a B-tree node must split after an insertion.

max_keys is the maximum number of keys a node may hold, keys is the current sorted key list, and insert_key is the new key. Merge the key into the sorted list; when the merged length exceeds max_keys the node splits and the promoted median sits at index len(merged) // 2.

Return the promoted index, or -1 when no split is needed.

Hint

The median index is the integer division of the merged length by two.

Test cases

case 1

in: [4,[1,2,3,4],5]

expected: 2

case 2

in: [4,[1,2,3],4]

expected: -1

case 3

in: [3,[1,3],2]

expected: -1

case 4

in: [3,[1,3,5],2]

expected: 2

case 5

in: [5,[],1]

expected: -1

Starter codePython

def btree_split_decision(max_keys, keys, insert_key):
    # Your code here
    pass

5 test cases · run your code against them in the editor