Что такое саморегулируемое дерево?

Саморегулируемое дерево (Self-Balancing Tree)

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

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

Обычное двоичное дерево поиска (BST) может деградировать в связный список, если элементы добавляются в отсортированном порядке:

// Несбалансированное дерево (худший случай)
BinarySearchTree tree = new BinarySearchTree();
tree.insert(1);  // Корень
tree.insert(2);  // Правый потомок
tree.insert(3);  // Правый потомок 2-х
tree.insert(4);  // Правый потомок 3-х
// Результат: связный список, O(n) поиск вместо O(log n)

Визуализация:

    1
     \
      2
       \
        3
         \
          4

Поиск элемента 4 требует проверки всех узлов!

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

С саморегулированием такое дерево остаётся сбалансированным:

      2
     / \
    1   3
         \
          4

Основные типы саморегулируемых деревьев:

1. AVL дерево (Adelson-Velsky and Landis)

Строгая балансировка по высоте. Разница высот левого и правого поддеревьев ≤ 1.

public class AVLNode {
    int value;
    AVLNode left, right;
    int height; // Высота узла
    
    public AVLNode(int value) {
        this.value = value;
        this.height = 1;
    }
}

public class AVLTree {
    private AVLNode root;
    
    // Получить высоту узла
    private int getHeight(AVLNode node) {
        return node == null ? 0 : node.height;
    }
    
    // Получить коэффициент баланса
    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) {
        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)
        );
        
        // Проверяем баланс и выполняем ротации
        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 Tree)

Ослабленная балансировка с цветами узлов (красный/чёрный).

Свойства:

• Каждый узел красный или чёрный
• Корень чёрный
• Листья (NULL) чёрные
• Красный узел имеет только чёрных потомков
• Все пути от узла до листьев содержат одинаковое количество чёрных узлов

public class RedBlackNode {
    int value;
    RedBlackNode left, right, parent;
    boolean isRed; // true = красный, false = чёрный
    
    public RedBlackNode(int value) {
        this.value = value;
        this.isRed = true; // Новые узлы красные
    }
}

public class RedBlackTree {
    private RedBlackNode root;
    
    // Операции: ротации и переокраски
    private void rotateLeft(RedBlackNode node) {
        RedBlackNode rightChild = node.right;
        node.right = rightChild.left;
        
        if (rightChild.left != null) {
            rightChild.left.parent = node;
        }
        
        rightChild.parent = node.parent;
        if (node.parent == null) {
            root = rightChild;
        } else if (node == node.parent.left) {
            node.parent.left = rightChild;
        } else {
            node.parent.right = rightChild;
        }
        
        rightChild.left = node;
        node.parent = rightChild;
    }
    
    // Похожая реализация для rotateRight
}

3. B-дерево

Многоветвистое дерево, используется в базах данных и файловых системах.

Свойства:

• Каждый узел содержит 1 до m-1 ключей
• Каждый внутренний узел имеет от 2 до m потомков
• Все листья находятся на одном уровне

public class BNode {
    int[] keys;        // Ключи
    BNode[] children;  // Потомки
    int keyCount;      // Количество ключей
    boolean isLeaf;    // Это лист?
    
    public BNode(boolean isLeaf, int maxDegree) {
        this.isLeaf = isLeaf;
        this.keys = new int[2 * maxDegree - 1];
        this.children = new BNode[2 * maxDegree];
        this.keyCount = 0;
    }
}

Сравнение типов деревьев

Практическое использование в Java

TreeMap использует красно-чёрное дерево:

import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        // TreeMap автоматически сбалансирован
        TreeMap<Integer, String> map = new TreeMap<>();
        
        // Вставка O(log n)
        map.put(50, "Fifty");
        map.put(30, "Thirty");
        map.put(70, "Seventy");
        
        // Поиск O(log n)
        System.out.println(map.get(30));
        
        // Итерация в отсортированном порядке
        map.forEach((key, value) -> 
            System.out.println(key + ": " + value)
        );
    }
}

TreeSet тоже основан на красно-чёрном дереве:

import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        
        // Все операции выполняются за O(log n)
        set.add(5);
        set.add(3);
        set.add(7);
        set.add(1);
        
        // Элементы всегда отсортированы
        set.forEach(System.out::println); // 1, 3, 5, 7
        
        // Диапазонные операции
        System.out.println(set.subSet(3, 7)); // [3, 5]
    }
}

Когда использовать

• AVL: Когда поиск критичен, но вставки/удаления редки
• Красно-чёрное: Когда нужен баланс между поиском и модификацией
• B-дерево: В базах данных и файловых системах

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