Какие знаешь способы сбалансировать дерево?

Ответ

Сбалансирование деревьев — фундаментальная тема в структурах данных. Сбалансированное дерево гарантирует O(log n) операции вместо O(n) в худшем случае.

Понимание проблемы

Несбалансированное дерево (худший случай):

       1
        \
         2
          \
           3
            \
             4
              \
               5

Поиск занимает O(n) времени!

Сбалансированное дерево:

         3
       /   \
      2     4
     /       \
    1         5

Поиск занимает O(log n) времени.

Способ 1: AVL дерево (самобалансирующееся)

AVL — первое самобалансирующееся дерево поиска. Оно поддерживает баланс через высоту.

Свойство баланса: для любого узла разница между высотой левого и правого поддерева не больше 1.

class AVLNode {
    int value;
    AVLNode left;
    AVLNode right;
    int height;
    
    AVLNode(int value) {
        this.value = value;
        this.height = 1;
    }
}

class AVLTree {
    AVLNode root;
    
    // Получить высоту узла
    private int getHeight(AVLNode node) {
        return node == null ? 0 : node.height;
    }
    
    // Получить balance factor
    private int getBalance(AVLNode node) {
        return node == null ? 0 : getHeight(node.left) - getHeight(node.right);
    }
    
    // Правый поворот
    private AVLNode rotateRight(AVLNode y) {
        AVLNode x = y.left;
        AVLNode T2 = x.right;
        
        // Выполнить поворот
        x.right = y;
        y.left = T2;
        
        // Обновить высоты
        y.height = 1 + Math.max(getHeight(y.left), getHeight(y.right));
        x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));
        
        return x;
    }
    
    // Левый поворот
    private AVLNode rotateLeft(AVLNode x) {
        AVLNode y = x.right;
        AVLNode T2 = y.left;
        
        // Выполнить поворот
        y.left = x;
        x.right = T2;
        
        // Обновить высоты
        x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));
        y.height = 1 + Math.max(getHeight(y.left), getHeight(y.right));
        
        return y;
    }
    
    public void insert(int value) {
        root = insertNode(root, value);
    }
    
    private AVLNode insertNode(AVLNode node, int value) {
        // Обычная вставка BST
        if (node == null) {
            return new AVLNode(value);
        }
        
        if (value < node.value) {
            node.left = insertNode(node.left, value);
        } else if (value > node.value) {
            node.right = insertNode(node.right, value);
        } else {
            return node;  // дубликаты не добавляем
        }
        
        // Обновить высоту
        node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
        
        // Получить balance factor
        int balance = getBalance(node);
        
        // Left Heavy
        if (balance > 1) {
            // Left-Right case
            if (value > node.left.value) {
                node.left = rotateLeft(node.left);
            }
            // Left-Left case
            return rotateRight(node);
        }
        
        // Right Heavy
        if (balance < -1) {
            // Right-Left case
            if (value < node.right.value) {
                node.right = rotateRight(node.right);
            }
            // Right-Right case
            return rotateLeft(node);
        }
        
        return node;
    }
}

Характеристики AVL:

• Сложность: O(log n) вставка, удаление, поиск
• Жесткий баланс: разница высот ≤ 1
• Частые ротации: много ротаций при вставке/удалении
• Использование: в приложениях, где читают чаще, чем пишут

Способ 2: Red-Black дерево

Red-Black дерево более гибкое, чем AVL. Используется в TreeMap и TreeSet Java.

Свойства:

1. Каждый узел либо красный, либо черный
2. Корень всегда черный
3. Все листья (nil) черные
4. Красный узел имеет только черных детей
5. Все пути от узла до листьев имеют одинаковое число черных узлов

enum Color { RED, BLACK }

class RBNode {
    int value;
    Color color;
    RBNode left, right, parent;
    
    RBNode(int value) {
        this.value = value;
        this.color = Color.RED;  // новые узлы красные
    }
}

class RedBlackTree {
    RBNode root;
    RBNode nil = new RBNode(Integer.MIN_VALUE);  // sentinel узел
    
    private void rotateLeft(RBNode x) {
        RBNode y = x.right;
        x.right = y.left;
        if (y.left != nil) {
            y.left.parent = x;
        }
        y.parent = x.parent;
        
        if (x.parent == null) {
            root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
    }
    
    private void rotateRight(RBNode y) {
        RBNode x = y.left;
        y.left = x.right;
        if (x.right != nil) {
            x.right.parent = y;
        }
        x.parent = y.parent;
        
        if (y.parent == null) {
            root = x;
        } else if (y == y.parent.right) {
            y.parent.right = x;
        } else {
            y.parent.left = x;
        }
        x.right = y;
        y.parent = x;
    }
    
    public void insert(int value) {
        RBNode z = new RBNode(value);
        RBNode y = nil;
        RBNode x = root;
        
        while (x != nil) {
            y = x;
            if (z.value < x.value) {
                x = x.left;
            } else {
                x = x.right;
            }
        }
        
        z.parent = y;
        if (y == nil) {
            root = z;
        } else if (z.value < y.value) {
            y.left = z;
        } else {
            y.right = z;
        }
        
        z.left = nil;
        z.right = nil;
        z.color = Color.RED;
        fixInsert(z);
    }
    
    private void fixInsert(RBNode z) {
        while (z.parent != null && z.parent.color == Color.RED) {
            if (z.parent == z.parent.parent.left) {
                RBNode uncle = z.parent.parent.right;
                if (uncle.color == Color.RED) {
                    // Case 1: Uncle is red
                    z.parent.color = Color.BLACK;
                    uncle.color = Color.BLACK;
                    z.parent.parent.color = Color.RED;
                    z = z.parent.parent;
                } else {
                    // Case 2: Uncle is black
                    if (z == z.parent.right) {
                        z = z.parent;
                        rotateLeft(z);
                    }
                    z.parent.color = Color.BLACK;
                    z.parent.parent.color = Color.RED;
                    rotateRight(z.parent.parent);
                }
            } else {
                // Симметричный случай
                RBNode uncle = z.parent.parent.left;
                if (uncle.color == Color.RED) {
                    z.parent.color = Color.BLACK;
                    uncle.color = Color.BLACK;
                    z.parent.parent.color = Color.RED;
                    z = z.parent.parent;
                } else {
                    if (z == z.parent.left) {
                        z = z.parent;
                        rotateRight(z);
                    }
                    z.parent.color = Color.BLACK;
                    z.parent.parent.color = Color.RED;
                    rotateLeft(z.parent.parent);
                }
            }
        }
        root.color = Color.BLACK;
    }
}

Характеристики Red-Black:

• Сложность: O(log n) все операции
• Гибкий баланс: более расслабленные условия, чем AVL
• Меньше ротаций: более эффективно при частых вставках/удалениях
• Использование: TreeMap, TreeSet в Java

Способ 3: B-дерево

Для больших данных на диске (БД).

class BNode {
    List<Integer> keys;
    List<BNode> children;
    boolean isLeaf;
    int minDegree;
    
    BNode(int minDegree, boolean isLeaf) {
        this.minDegree = minDegree;
        this.isLeaf = isLeaf;
        this.keys = new ArrayList<>();
        this.children = new ArrayList<>();
    }
}

class BTree {
    BNode root;
    int minDegree;
    
    public BTree(int minDegree) {
        this.minDegree = minDegree;
        this.root = new BNode(minDegree, true);
    }
    
    // Вставка гарантирует, что узел никогда не переполняется
    public void insert(int value) {
        // реализация...
    }
}

Характеристики B-дерево:

• Порядок: множество ключей в одном узле
• Использование: БД, файловые системы
• Сложность: O(log n) все операции

Способ 4: Трехсторонняя балансировка (2-3 дерево)

Простейшее из самобалансирующихся деревьев.

• Все листья на одной глубине
• Узлы имеют 2 или 3 детей
• Все операции O(log n)

Способ 5: Ленивая балансировка (DSW алгоритм)

public void balanceTree() {
    // Шаг 1: Преобразовать в "vine" (цепь)
    createVine();
    
    // Шаг 2: Преобразовать vine в сбалансированное дерево
    createBalancedTree();
}

Сравнение подходов

Практические советы

1. Используй встроенные структуры: TreeMap, TreeSet (Red-Black)
2. AVL для частых поисков, Red-Black для вставок/удалений
3. B-деревья для работы с диском
4. Регулярно профилируй перед применением

// В Java используй стандартные структуры
NavigableMap<Integer, String> map = new TreeMap<>();
map.put(5, "five");
map.put(3, "three");
map.put(7, "seven");
// Автоматически сбалансирована (Red-Black дерево)

Главный вывод: выбирай подход в зависимости от паттерна доступа (поиск vs вставка) и требований к памяти.