Ответ
Деревья — иерархические структуры данных. Основные виды различаются правилами организации узлов и балансировкой.
1. Базовые деревья
- Бинарное дерево (Binary Tree): У каждого узла не более двух потомков (левый и правый). Нет ограничений на порядок значений.
- Бинарное дерево поиска (Binary Search Tree, BST): Частный случай бинарного дерева. Для любого узла:
- Все значения в левом поддереве меньше значения узла.
- Все значения в правом поддереве больше значения узла.
- Обеспечивает поиск, вставку и удаление в среднем за O(log n), но может выродиться в список O(n).
class BSTNode {
int key;
BSTNode left, right;
// Поиск в BST
BSTNode search(BSTNode root, int key) {
if (root == null || root.key == key) return root;
if (key < root.key) return search(root.left, key);
else return search(root.right, key);
}
}
2. Сбалансированные деревья поиска
Самобалансируются после операций, гарантируя O(log n).
- AVL-дерево: Жестко сбалансировано. Разница высот левого и правого поддеревьев (balance factor) любого узла равна -1, 0 или 1. Частые перебалансировки делают его быстрым для поиска, но медленным для частых вставок/удалений.
- Красно-черное дерево: Более мягкие правила балансировки (цвет узлов). Требует меньше перестроений при модификации, чем AVL. Используется в
java.util.TreeMapиTreeSet.
3. Специализированные деревья
- B-дерево и B+-дерево: Узлы содержат множество ключей (порядок
m). Оптимизированы для хранения на диске (используются в файловых системах и СУБД), минимизируют количество обращений к блокам. - Куча (Heap): Полное бинарное дерево, удовлетворяющее свойству кучи (значение родителя >= или <= значений потомков). Не является деревом поиска. Основа для PriorityQueue и алгоритма Heapsort.
- Префиксное дерево (Trie): Хранит строки. Путь от корня до узла представляет префикс или целую строку. Эффективно для автодополнения и поиска по префиксу.
| Сводная таблица применения: | Структура | Основное применение |
|---|---|---|
| BST | База для понимания, простые случаи. | |
| AVL / Красно-черное | Ассоциативные массивы (TreeMap), где важен гарантированный логарифмический доступ. |
|
| B-дерево | Индексы в базах данных, файловые системы. | |
| Куча | Очередь с приоритетом, планировщики. | |
| Trie | Словари, автодополнение, хранение строковых ключей. |