Баланс-фактор

Баланс-фактор — это числовая характеристика узла в сбалансированном по высоте двоичном дереве поиска (АВЛ-дереве), определяющая разность высот его правого и левого поддеревьев. Используется для оценки степени сбалансированности дерева и принятия решений о необходимости выполнения операций вращения (балансировки) при вставке или удалении элементов.

Определение и математическая запись

Баланс-фактор (BF) для узла N вычисляется по формуле:

\[ BF(N) = h(\text{right}(N)) - h(\text{left}(N)) \]

где:

• \( h(\text{right}(N)) \) — высота правого поддерева узла \( N \);
• \( h(\text{left}(N)) \) — высота левого поддерева узла \( N \).

Высота пустого поддерева (null) принимается равной \(-1\) (или \(0\) в некоторых реализациях, что приводит к смещению шкалы). В классическом определении АВЛ-дерева допустимые значения баланс-фактора для любого узла равны \(-1\), \(0\) или \(1\). Если модуль баланс-фактора превышает 1, дерево считается несбалансированным и требует корректировки.

История и происхождение

Понятие баланс-фактора было введено советскими математиками Георгием Адельсоном-Вельским и Евгением Ландисом в 1962 году в работе «Один алгоритм организации информации» (опубликована в журнале «Доклады Академии наук СССР»). В этой статье впервые было описано сбалансированное по высоте дерево, названное впоследствии АВЛ-деревом (по первым буквам фамилий авторов). Баланс-фактор стал ключевым инструментом для формализации свойства сбалансированности и разработки алгоритмов балансировки.

Свойства и интерпретация

Баланс-фактор позволяет оценить, насколько левое и правое поддеревья узла отличаются по высоте.

• BF = 0: высоты левого и правого поддеревьев равны. Узел идеально сбалансирован.
• BF = 1: правое поддерево на один уровень выше левого. Допустимое отклонение.
• BF = -1: левое поддерево на один уровень выше правого. Допустимое отклонение.
• |BF| > 1: дерево в данном узле несбалансировано. Требуется операция вращения (одинарного или двойного).

Знак баланс-фактора указывает на «перекос»: положительное значение — перевес вправо, отрицательное — влево.

Алгоритмы поддержания баланс-фактора

Вычисление высоты узла

Высота узла \( h(N) \) рекурсивно определяется как максимальная высота его дочерних узлов плюс 1:

\[ h(N) = 1 + \max(h(\text{left}(N)), h(\text{right}(N))) \]

Для пустого узла \( h(\text{null}) = -1 \).

Обновление баланс-фактора после вставки

При вставке нового элемента в АВЛ-дерево баланс-факторы узлов на пути от корня к вставленному узлу могут измениться. После вставки выполняется обратный проход (backtracking) от нового узла к корню:

1. Для каждого узла на пути пересчитывается высота.
2. Вычисляется новый баланс-фактор.
3. Если |BF| > 1, выполняется соответствующее вращение (одинарное или двойное) для восстановления баланса.

Обновление баланс-фактора после удаления

Удаление узла также может нарушить баланс. Процесс аналогичен: после удаления пересчитываются высоты и баланс-факторы узлов на пути к корню, и при необходимости выполняются вращения. В отличие от вставки, после удаления может потребоваться несколько последовательных балансировок.

Типы вращений на основе баланс-фактора

В зависимости от значений баланс-фактора узла и его дочерних узлов выбирается тип вращения:

После выполнения вращения баланс-факторы узлов, участвовавших в операции, пересчитываются и, как правило, принимают значения 0, 1 или -1.

Применение

Баланс-фактор является фундаментальным понятием в теории структур данных и алгоритмов. Он используется:

• В АВЛ-деревьях — для обеспечения логарифмической сложности операций поиска, вставки и удаления (O(log n)).
• В других самобалансирующихся деревьях — например, в красно-черных деревьях используется аналогичное понятие «черной высоты», но баланс-фактор в явном виде не хранится.
• В обучении программированию — как классический пример применения инвариантов и рекурсивных алгоритмов.
• В системах управления базами данных — для построения индексов (B-деревья используют другие метрики, но принцип сбалансированности схож).

Реализация в программном коде

В большинстве реализаций АВЛ-дерева баланс-фактор не хранится как отдельное поле, а вычисляется на лету как разность высот дочерних узлов. Однако для ускорения операций его часто сохраняют в каждом узле и обновляют при каждом изменении дерева. Пример на псевдокоде:

`` struct Node { int key; Node left; Node right; int height; // высота узла int balanceFactor; // баланс-фактор (опционально) }; ``

Функция вычисления баланс-фактора:

`` int getBalanceFactor(Node* node) { if (node == nullptr) return 0; return height(node->right) - height(node->left); } ``

Критика и альтернативы

Хранение баланс-фактора в каждом узле увеличивает расход памяти (на одно целое число на узел). В некоторых реализациях отказываются от явного хранения баланс-фактора, вычисляя его при необходимости, что замедляет операции, но экономит память. Альтернативой АВЛ-деревьям с баланс-фактором являются красно-черные деревья, которые используют бинарный признак (цвет) и менее строгие условия балансировки, что приводит к меньшему числу вращений при вставке, но к большей высоте дерева в среднем.

Источники

• Адельсон-Вельский Г. М., Ландис Е. М. «Один алгоритм организации информации» // Доклады АН СССР, 1962, том 146, № 2, с. 263–266.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ» (Introduction to Algorithms), 3-е издание, глава 13 (Красно-черные деревья) и глава 14 (АВЛ-деревья).
• Кнут Д. Э. «Искусство программирования», том 3: «Сортировка и поиск», раздел 6.2.3 (Сбалансированные деревья).
• Вирт Н. «Алгоритмы и структуры данных», глава 4 (Сбалансированные деревья).