AVL и красно-чёрное дерево

Самобалансирующиеся деревья поддерживают высоту порядка O(log n) при любых вставках и удалениях, устраняя худший случай обычного BST.

AVL-дерево хранит баланс-фактор каждого узла и при отличии высот поддеревьев больше чем на 1 выполняет повороты; оно строго сбалансировано, поэтому поиск чуть быстрее. Красно-чёрное дерево ослабляет баланс через окраску узлов, делает меньше поворотов при изменениях и поэтому быстрее на вставках/удалениях — его используют в std::map и TreeMap.

Сложность: поиск, вставка, удаление — гарантированно O(log n). Память: O(n).

# В Python готового сбалансированного дерева в stdlib нет.
# Практичная замена: модуль sortedcontainers
from sortedcontainers import SortedList
sl = SortedList([5, 1, 8])
sl.add(3)              # O(log n)
print(sl)              # SortedList([1, 3, 5, 8])