Red-black insert

Write the insert of a red-black tree (lesson 4). rb_insert(root, key) inserts the key into the tree whose root is root (None for an empty tree) and returns the new root. Each node has a field red: True for red, False for black. After every insert the tree must obey the four rules:

1. Every node is red or black.
2. The root is black.
3. A red node never has a red child.
4. Every path from a node down to a missing child passes the same number of black nodes.

The tests start from an empty tree (None), insert the keys one at a time with root = f(root, key), and then read your tree through .value, .left and .right. Keep those field names.

Different correct methods give different trees, so the tests do not check the exact shape. They check the four rules, that the keys are all there in order, and that the height is at most 2 log₂(n + 1). The left-leaning version from lesson 4 is accepted. All keys are different.

Limits

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