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

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

Примеры: AVL-дерево, красно-черное дерево, Splay-дерево.

Пример AVL-дерева (Java):

class Node {
    int key, height;
    Node left, right;
    Node(int key) { this.key = key; height = 1; }
}

class AVLTree {
    Node root;
    int height(Node node) { return (node == null) ? 0 : node.height; }
    int balanceFactor(Node node) { return height(node.left) - height(node.right); }
    // Методы поворотов и балансировки опущены для краткости
}

Применение: Базы данных, файловые системы, реализация TreeMap/TreeSet в Java.