Что такое поворот дерева?

Поворот дерева (Tree Rotation)

Поворот дерева (tree rotation) — это фундаментальная операция на сбалансированных деревьях поиска (balanced binary search trees), которая изменяет структуру дерева, сохраняя при этом свойство двоичного дерева поиска. Это локальная операция, которая реорганизует узлы дерева без изменения их логического порядка.

Зачем нужны повороты?

Поддержание баланса — после вставки или удаления элемента дерево может стать несбалансированным, что деградирует производительность

Гарантия производительности — сбалансированное дерево гарантирует O(log n) для search, insert, delete операций

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

Основные типы повротов

Левый поворот (Left Rotation)

Левый поворот применяется, когда правое поддерево слишком тяжёлое (много узлов справа):

До левого поворота:        После левого поворота:

    X                           Y
   / \                         / \
  A   Y          →            X   C
     / \                     / \
    B   C                   A   B

В левом повороте:

• Y становится новым корнем
• X становится левым ребёнком Y
• Левое поддерево Y (B) становится правым поддеревом X

Правый поворот (Right Rotation)

Правый поворот применяется, когда левое поддерево слишком тяжёлое:

До правого поворота:       После правого поворота:

      X                         Y
     / \                       / \
    Y   C      →              A   X
   / \                           / \
  A   B                         B   C

В правом повороте:

• Y становится новым корнем
• X становится правым ребёнком Y
• Правое поддерево Y (B) становится левым поддеревом X

Двойные повороты

Левый-Правый поворот (Left-Right Rotation)

Апplicируется, когда левое поддерево содержит правое поддерево

Шаг 1: Левый поворот на левом поддереве
Шаг 2: Правый поворот на корне

До:                 Шаг 1:              Шаг 2 (Итог):
    X                   X                   Z
   /                   /                   / \
  Y                   Z                   Y   X
   \                 /
    Z               Y

Правый-Левый поворот (Right-Left Rotation)

Апplicируется, когда правое поддерево содержит левое поддерево

Шаг 1: Правый поворот на правом поддереве
Шаг 2: Левый поворот на корне

До:                 Шаг 1:              Шаг 2 (Итог):
  X                   X                   Z
   \                   \                 / \
    Y                   Z               X   Y
   /                     \
  Z                       Y

Где используются повороты?

AVL дерево

AVL (Adelson-Velsky and Landis) дерево — это самобалансирующееся двоичное дерево поиска:

• Поддерживает баланс-фактор для каждого узла
• Balance factor = высота(левого поддерева) - высота(правого поддерева)
• Баланс-фактор должен быть -1, 0 или 1
• При нарушении баланса выполняет повороты

Пример AVL дерева (идеально сбалансировано):

       4 (bf=0)
      / \
     2   6  (bf=0)
    / \ / \
   1 3 5 7

Red-Black дерево

Red-Black дерево — это самобалансирующееся дерево с цветовой раскраской:

• Каждый узел окрашен в красный или чёрный цвет
• Свойства гарантируют почти сбалансированное дерево
• Использует повороты при вставке и удалении

B-дерево

B-дерево — это многопроходное дерево поиска:

• Используется в базах данных и файловых системах
• Имеет несколько ключей в одном узле
• Использует повороты для реализации слияния и разделения узлов

Практический пример: AVL дерево с вставкой

Вставляем значение 50 в AVL дерево:

До (несбалансировано):    После левого поворота:
      30                            40
     / \                           / \
    20 40                         30 50
         \                       /
         50                     20

Вставка 50 нарушила баланс узла 40 (bf=2)
Левый поворот восстановил баланс

Сложность операций при повороте

Временная сложность: O(1) — поворот это локальная операция

Пространственная сложность: O(1) — только несколько переназначений указателей

Количество поворотов:

• При вставке: максимум 2 поворота (одна вставка может потребовать один двойной поворот или 1 простой)
• При удалении: может потребоваться до O(log n) поворотов при удалении из AVL

Реализация левого поворота (псевдокод)

function leftRotate(X):
  Y = X.right                    // Y является правым ребёнком X
  X.right = Y.left              // B переходит в правое поддерево X
  Y.left = X                     // X становится левым ребёнком Y
  updateHeight(X)                // Обновляем высоту X
  updateHeight(Y)                // Обновляем высоту Y
  return Y                       // Y становится новым корнем

Значение повротов для системного аналитика

Понимание производительности БД — знание о балансировке деревьев помогает понять индексацию в БД

Выбор структур данных — для проектирования высоконагруженных систем важно понимать O(log n) vs O(n)

Оптимизация — понимание AVL/RB деревьев помогает выбрать правильную структуру для задачи

Масштабируемость — сбалансированные деревья критичны для больших наборов данных

Основа архитектуры — индексы в БД (как PostgreSQL, MySQL, MongoDB) используют B-деревья, основанные на эти принципах

Почему это важно?

Повороты деревьев — это фундаментальный механизм, обеспечивающий эффективность баз данных, файловых систем и поисковых систем. Без баланса деревьев, даже простые операции поиска на миллионах записей могли бы занимать секунды вместо миллисекунд.

Для системного аналитика, проектирующего высоконагруженные системы, понимание этих механизмов критично для правильной архитектуры и выбора технологий.