Что означает нормализация бинарного дерева поиска (BST)?

Нормализация BST — это процесс преобразования дерева в сбалансированную форму для гарантирования логарифмической сложности основных операций (поиск, вставка, удаление). Без балансировки дерево может выродиться в связный список со сложностью O(n).

Основные подходы к нормализации (балансировке):

1. Автоматически балансирующиеся деревья: Алгоритмы, которые поддерживают баланс после каждой модификации.

   • AVL-дерево: Строго сбалансировано (разница высот поддеревьев ≤ 1). Обеспечивает быстрый поиск, но требует частых поворотов при вставке/удалении.
   • Красно-чёрное дерево: Менее строгий баланс (длина самого длинного пути не более чем в 2 раза превышает самый короткий). Требует меньше перестроений, чем AVL, поэтому часто используется в стандартных библиотеках (например, std::map в C++).

2. Повороты (rotations): Базовые операции для восстановления баланса.

   // Пример малого левого поворота (для правого случая дисбаланса)
   func rotateLeft(_ y: Node?) -> Node? {
       guard let x = y?.right else { return y }
       y?.right = x.left
       x.left = y
       // Обновление высот/баланс-факторов
       return x // Новый корень поддерева
   }

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