Обычное BST может деградировать в связный список (операции O(n)), если ключи приходят в отсортированном порядке. Самобалансирующиеся BST — такие как AVL и красно-чёрные деревья — автоматически выполняют ротации после вставок/удалений, чтобы поддерживать высоту ~log n, гарантируя операции .
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| Дерево AVL | Красно-чёрное дерево | |
|---|---|---|
| Строгость балансировки | строгая (сбалансировано по высоте) | слабее |
| Поиск | быстрее (короче) | немного медленнее |
| Вставка/удаление | больше ротаций | меньше ротаций |
| Лучше всего для | рабочих нагрузок с преобладанием чтения | рабочих нагрузок с преобладанием записи |
| Операция | Время |
|---|---|
| поиск | O(log n) |
| вставка | O(log n) |
| удаление | O(log n) |
Оба поддерживают баланс через ротации — локальные O(1) переструктуризации, которые сохраняют упорядочение BST при одновременном снижении высоты.
Сбалансированные деревья поддерживают упорядоченные отображения и множества в стандартных библиотеках (напр. Java TreeMap, C++ std::map используют красно-чёрные деревья), обеспечивая отсортированную итерацию плюс гарантированные логарифмические операции.
Они — ответ, когда нужны как упорядочение BST и гарантия производительности против враждебного ввода.