Ответ
Саморегулируемое дерево поиска (self-balancing binary search tree) — это бинарное дерево поиска (БДП), которое автоматически поддерживает свою высоту (глубину) близкой к логарифмической от числа узлов (O(log n)) после операций вставки или удаления.
Зачем это нужно? Обычное БДП может выродиться в связный список (высота O(n)) при последовательной вставке отсортированных данных, что сводит эффективность операций поиска, вставки и удаления к O(n). Балансировка гарантирует эффективность O(log n).
| Основные типы и их свойства: | Тип дерева | Правило балансировки | Сложность операций | Применение |
|---|---|---|---|---|
| AVL-дерево | Жёсткий баланс: разница высот левого и правого поддеревьев (balance factor) любого узла равна -1, 0 или 1. | O(log n) |
Там, где частые операции поиска критичны (словари, кэши). | |
| Красно-чёрное дерево | Более мягкие правила (цвет узлов, свойства путей). Допускает большую несбалансированность, чем AVL. | O(log n) |
Реализация TreeMap, TreeSet в Java, ассоциативные массивы. |
|
| Splay-дерево | Балансируется при доступе к узлу (перемещает его в корень). Амортизированная O(log n). |
Амортизированная O(log n) |
Кэши, сборщики мусора. |
Пример структуры узла для AVL-дерева на Java:
class AVLNode {
int key, height;
AVLNode left, right;
AVLNode(int key) {
this.key = key;
this.height = 1; // Высота нового листа = 1
}
// Метод для пересчёта высоты узла
void updateHeight() {
this.height = 1 + Math.max(
(left == null ? 0 : left.height),
(right == null ? 0 : right.height)
);
}
// Получение фактора баланса
int getBalanceFactor() {
return (left == null ? 0 : left.height) - (right == null ? 0 : right.height);
}
}Применение: Базы данных (индексы), файловые системы, реализация упорядоченных коллекций в стандартных библиотеках.