Balanced search tree (AVL, red-black)

Why it costs this much

Rotations keep the height at O(log n) after every insert and delete.

Code

import bisect
i = bisect.bisect_left(sorted_list, x)   # O(log n): binary search
sorted_list.insert(i, x)                 # O(n): shifts later items
# A balanced tree makes both steps O(log n) together.

Common pitfalls

More work to implement than a hash table, and lookups are O(log n), not O(1). Python's standard library has no balanced tree; bisect on a list costs O(n) per insert.

Operation by operation

Balanced BST search, insert, delete. Height is kept at O(log n) by rotations, as in AVL and red-black trees. Python has no built-in balanced tree. Java TreeMap and C++ std::map are red-black trees.