Что такое сбалансированное дерево?

Что такое сбалансированное дерево?

Сбалансированное дерево — это бинарное дерево поиска, в котором высоты левого и правого поддеревьев любого узла различаются не более чем на определённую величину (обычно на 1). Это гарантирует, что операции поиска, вставки и удаления выполняются за O(log n), а не за O(n).

Проблема несбалансированного дерева

Несбалансированное дерево (вырожденное):

Уже вставлены: 1, 2, 3, 4, 5

    1
     \
      2
       \
        3
         \
          4
           \
            5

Высота: 5 (как связный список!)
Поиск любого элемента: O(n)

Сбалансированное дерево (те же элементы):

        3
       / \
      2   4
     /     \
    1       5

Высота: 3 (log2(5) ≈ 2.3)
Поиск любого элемента: O(log n)

Основные типы сбалансированных деревьев

1. AVL-дерево

АВЛ-дерево поддерживает баланс так, чтобы для каждого узла высоты левого и правого поддеревьев отличались не более чем на 1:

struct AVLNode {
    int value;
    int height;  // Для отслеживания баланса
    AVLNode* left;
    AVLNode* right;
};

int getHeight(AVLNode* node) {
    return node ? node->height : 0;
}

int getBalance(AVLNode* node) {
    return node ? getHeight(node->left) - getHeight(node->right) : 0;
}

// Левый поворот при дисбалансе
AVLNode* rotateLeft(AVLNode* y) {
    AVLNode* x = y->right;
    AVLNode* T2 = x->left;
    
    x->left = y;
    y->right = T2;
    
    y->height = 1 + std::max(getHeight(y->left), getHeight(y->right));
    x->height = 1 + std::max(getHeight(x->left), getHeight(x->right));
    
    return x;
}

// Правый поворот
AVLNode* rotateRight(AVLNode* x) {
    AVLNode* y = x->left;
    AVLNode* T2 = y->right;
    
    y->right = x;
    x->left = T2;
    
    x->height = 1 + std::max(getHeight(x->left), getHeight(x->right));
    y->height = 1 + std::max(getHeight(y->left), getHeight(y->right));
    
    return y;
}

// Вставка с балансировкой
AVLNode* insert(AVLNode* node, int value) {
    // Стандартная вставка BST
    if (!node) {
        return new AVLNode{value, 1, nullptr, nullptr};
    }
    
    if (value < node->value) {
        node->left = insert(node->left, value);
    } else if (value > node->value) {
        node->right = insert(node->right, value);
    } else {
        return node;  // Дубликаты не допускаются
    }
    
    // Обновляем высоту
    node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));
    
    // Получаем баланс-фактор
    int balance = getBalance(node);
    
    // Левый случай
    if (balance > 1 && value < node->left->value) {
        return rotateRight(node);
    }
    
    // Правый случай
    if (balance < -1 && value > node->right->value) {
        return rotateLeft(node);
    }
    
    // Левый-правый случай
    if (balance > 1 && value > node->left->value) {
        node->left = rotateLeft(node->left);
        return rotateRight(node);
    }
    
    // Правый-левый случай
    if (balance < -1 && value < node->right->value) {
        node->right = rotateRight(node->right);
        return rotateLeft(node);
    }
    
    return node;
}

2. Red-Black дерево

Red-Black дерево использует цвет узла для поддержания баланса:

enum Color { RED, BLACK };

struct RBNode {
    int value;
    Color color;
    RBNode* left;
    RBNode* right;
    RBNode* parent;
};

// Свойства Red-Black дерева:
// 1. Корень чёрный
// 2. Все листья чёрные (nil листья)
// 3. Если узел красный, его дети чёрные
// 4. Все пути от узла до листьев содержат одинаковое число чёрных узлов

3. B-дерево

B-дерево используется в базах данных для эффективного доступа к диску:

B-дерево порядка 3:

          [30, 70]
         /    |    \
       /      |      \
   [10,20] [40,60] [80,90]

Сравнение балансировки

Практический пример: std::map в C++

std::map в C++ реализована как Red-Black дерево:

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> balancedTree;
    
    // Все операции автоматически поддерживают баланс
    balancedTree[1] = "one";
    balancedTree[2] = "two";
    balancedTree[3] = "three";
    balancedTree[4] = "four";
    balancedTree[5] = "five";
    
    // Поиск: гарантированно O(log n)
    auto it = balancedTree.find(3);
    
    // Удаление: гарантированно O(log n)
    balancedTree.erase(2);
    
    return 0;
}

Метрика баланса (Balance Factor)

Для каждого узла определяется balance factor:

BF = height(left subtree) - height(right subtree)

Для AVL-дерева: BF должен быть в диапазоне [-1, 0, 1]

Примеры:
Для узла с левым поддеревом высоты 3 и правым высоты 2:
BF = 3 - 2 = 1 (сбалансировано)

Для узла с левым поддеревом высоты 4 и правым высоты 2:
BF = 4 - 2 = 2 (дисбалансировано, нужна ротация!)

Операции поворота

Правый поворот (когда левое поддерево выше):

      z                y
     / \              / \
    y   T4   -->     x   z
   / \              / \ / \
  x   T3          T1 T2 T3 T4
 / \
T1 T2

Левый поворот (когда правое поддерево выше):

    x                z
   / \              / \
  T1  z     -->    x   y
     / \          / \ / \
    T2  y       T1 T2 T3 T4
       / \
      T3 T4

Практическое применение в Backend

1. Кэш с LRU eviction: Используются сбалансированные деревья для быстрого поиска и удаления элементов.

2. Базы данных: B-деревья в индексах обеспечивают быстрый доступ к данным на диске.

3. Файловые системы: Red-Black деревья в NTFS и ext4.

4. Приоритетные очереди: Сбалансированные деревья обеспечивают O(log n) для всех операций.

5. Балансировка нагрузки: Деревья помогают эффективно распределить нагрузку.

Вывод

Сбалансированные деревья — это критически важная структура данных для любого backend-разработчика, обеспечивающая гарантированную логарифмическую сложность вместо линейной, что критично для систем с большим объёмом данных.