Какие основные виды деревьев используются в алгоритмах и структурах данных?

«Какие основные виды деревьев используются в алгоритмах и структурах данных?» — вопрос из категории Алгоритмы и структуры данных, который задают на 10% собеседований Java Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Ответ

Деревья — иерархические структуры данных. Основные виды различаются правилами организации узлов и балансировкой.

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 Словари, автодополнение, хранение строковых ключей.