AVL insert

Write the insert of an AVL tree (lesson 3). avl_insert(root, key) inserts the key into the tree whose root is root (None for an empty tree) and returns the new root. After every insert, every node must obey the AVL rule: its two subtrees differ in height by at most 1.

root = None
for key in [1, 2, 3]:
    root = avl_insert(root, key)
# root is 2, with children 1 and 3

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.

An AVL insert is fully determined by the keys and their order, so the tests check the exact shape of small trees, and the height and balance of big ones. All keys are different.

Limits

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