B-tree insert

Write the insert of a B-tree in which every node holds 1 to 3 keys (lesson 5, with t = 2). A node is a BNode with a sorted list keys and a list kids of children, empty for a leaf. btree_insert(root, key) inserts the key into the tree whose root is root (None for an empty tree) and returns the root. If the key is already in the tree, change nothing.

After every insert the tree must obey the rules:

• every node holds 1 to 3 keys, in increasing order;
• a node with k keys that is not a leaf has k + 1 children, and the keys of each child lie between the keys on either side of it;
• all leaves are at the same depth.

root = None
for key in [10, 20, 30, 40]:
    root = btree_insert(root, key)
# one possible answer: root.keys == [20],
# root.kids hold [10] and [30, 40]

Splitting on the way down (as in the lesson) and splitting on the way back up both give valid trees, so the tests check the rules, the keys and the height, not the exact shape.

Limits

• Up to 20,000 inserts; each one should take O(log n) time.