Что такое поворот дерева и зачем он нужен?

Поворот дерева — это фундаментальная операция в структурах данных, используемая для поддержания баланса в бинарных деревьях поиска (BST). Когда мы добавляем или удаляем узлы в BST, дерево может стать несбалансированным, превратившись в вырожденный список, где операции поиска будут выполняться за O(n). Чтобы избежать этого, применяются самобалансирующиеся деревья, такие как AVL или красно-чёрные, которые используют повороты для корректировки высоты.

Как работает поворот

Поворот локально меняет связь между узлом и его потомком, сохраняя порядок обхода inorder (что гарантирует, что дерево остаётся BST). Существует два основных типа:

• Правый поворот (Right Rotation): Узел X становится правым потомком своего левого потомка Y. Y поднимается, а правое поддерево X перемещается как левое поддерево Y.
• Левый поворот (Left Rotation): Симметричная операция, где узел X становится левым потомком своего правого потомка Y.

Пример кода для правого поворота

Рассмотрим простую реализацию на Python для узла бинарного дерева:

class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

def right_rotate(y):
    """Выполняет правый поворот вокруг узла y."""
    x = y.left
    T2 = x.right
    
    # Выполняем поворот
    x.right = y
    y.left = T2
    
    # Обновляем высоты (важно для AVL)
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    
    return x  # Новый корень поддерева

def get_height(node):
    if not node:
        return 0
    return node.height

Где применяется

Повороты активно используются в:

• AVL-деревьях: После каждой вставки/удаления проверяется баланс-фактор (разница высот поддеревьев). Если он выходит за пределы [-1, 1], выполняются повороты (одинарные или двойные) для восстановления баланса.
• Красно-чёрных деревьях: Для сохранения свойств цвета и глубины.
• Декартовых деревьях (Treap): Для поддержания кучеобразного порядка.

Вывод: Поворот дерева — ключевой механизм для поддержания логарифмической высоты в сбалансированных BST, что критически важно для производительности в базах данных, файловых системах и реализациях ассоциативных массивов (например, в стандартных библиотеках C++ или Java). Применяйте его, когда нужны гарантированно быстрые операции поиска в динамически изменяющихся данных.