A B-tree node has a fixed key capacity. Inserting one more key may overflow the node, in which case the median key is promoted to its parent and the keys on either side form two child nodes.
Design a BTreeNodeSplitter class:
BTreeNodeSplitter() creates a stateless splitter.int promotedKey(int[] keys, int newKey, int maxKeys) returns the key promoted after insertion, or -1 when the node still fits.
keys is sorted in ascending order and contains distinct values. newKey does not already occur in keys. Insert it into the sorted order. When the new size is greater than maxKeys, return the key at index size / 2 using integer division.
Example 1:
Input:
Output:
Explanation: Insertion produces [10,20,30,40]. Four keys overflow capacity 3, and the key at index 2 is 30.
Example 2:
Input:
Output:
Explanation: The node contains three keys after insertion, exactly its capacity, so no split occurs.
Constraints
0 <= keys.length <= 10^51 <= maxKeys <= 10^5keys.length <= maxKeys0 <= keys[i], newKey <= 10^9keys is strictly increasing, and newKey is not in keys.- At most
100 calls are made to promotedKey.
Promote a Key During a B-Tree Splitmedium