Exercise 1: 50 Keys in Random Order — Possible Solution
====================================================================

THE TEST
------------------------------
    random_keys = list(range(1, 51))
    random.shuffle(random_keys)

    root = BTreeNode(leaf=True)
    for k in random_keys:
        root = btree_insert(root, k, f"val{k}")

    missing = [k for k in random_keys if btree_search(root, k) != f"val{k}"]

RESULT
------------------------------
    missing == []

Every one of the 50 keys, inserted in a genuinely shuffled order (not
1, 2, 3, ... in sequence), is found correctly afterward.

WHY INSERTION ORDER DOESN'T AFFECT FINAL CORRECTNESS
------------------------------
insert_into_node's own leaf-insertion step always finds the correct
SORTED position for a new key, regardless of what order keys arrive
in:

    i = 0
    while i < len(node.keys) and key > node.keys[i]:
        i += 1
    node.keys.insert(i, key)
    node.values.insert(i, value)

This guarantees every node's own keys list stays sorted at all times,
after every single insert, independent of insertion order -- key 37
inserted before key 12 still ends up correctly positioned before key
12 in whichever leaf it belongs to, because the insertion position is
always computed relative to whatever keys are ALREADY there, not
relative to some assumed arrival order.

split_node's own logic is likewise order-independent: it always
promotes the MEDIAN of whatever keys currently happen to be in an
overflowing node, wherever they came from and in whatever order they
arrived -- it never assumes the node's own keys arrived in any
particular sequence, only that they're correctly sorted (which the
insertion step above already guarantees).

WHY THE SHAPE OF THE TREE CAN STILL DIFFER
------------------------------
Insertion order doesn't affect correctness, but it DOES affect exactly
which keys end up grouped together in which nodes, and exactly when
each split happens -- inserting 1..50 in strict ascending order tends
to produce a different (often less balanced, more "staircase"-shaped)
tree than inserting the same 50 keys in random order, since sequential
inserts repeatedly hit the same rightmost leaf. Both shapes are
equally valid, correctly-functioning B-trees -- "correct" here means
every key is findable and every node obeys the real key/child-count
invariants, not that there's only one possible tree shape for a given
set of keys.

WHY THIS WORKS AS AN ANSWER
------------------------------
This confirms the algorithm's own correctness guarantee doesn't depend
on any assumption about how data arrives -- a real, practical property,
since a real database table's own rows are inserted in whatever order
an application happens to insert them, with no guarantee of being
sorted, sequential, or predictable in any way.