Бинарное дерево

Бинарное дерево — структура, где у узла не больше двух дочерних узлов: левого и правого. Само по себе это определение не задаёт порядок значений. Порядок появляется у binary search tree (BST).

Термины

Термин	Значение
root	узел без родителя
leaf	узел без детей
subtree	узел вместе со всеми потомками
depth	число рёбер от root до узла
height	максимальное число рёбер от узла до leaf
balanced	высота контролируется относительно числа узлов

Пустое дерево и высота листа могут определяться по-разному (-1/0 или 0/1). В коде и на собеседовании нужно сначала назвать выбранное соглашение.

Инвариант BST

Для каждого узла все ключи слева меньше его ключа, все ключи справа — больше. Правило для дубликатов задаётся отдельно: запретить, хранить счётчик или стабильно направлять в одну сторону.

        8
      /   \
     3     12
    / \    /
   1   6  10

In-order обход этого BST даст 1, 3, 6, 8, 10, 12.

Поиск и вставка

final class IntNode {
    int key;
    IntNode left;
    IntNode right;
 
    IntNode(int key) {
        this.key = key;
    }
}
 
static boolean contains(IntNode node, int target) {
    while (node != null) {
        if (target == node.key) return true;
        node = target < node.key ? node.left : node.right;
    }
    return false;
}
 
static IntNode insert(IntNode node, int key) {
    if (node == null) return new IntNode(key);
    if (key < node.key) node.left = insert(node.left, key);
    else if (key > node.key) node.right = insert(node.right, key);
    return node;
}

Стоимость поиска, вставки и удаления — O(h), где h — высота. В сбалансированном дереве h = O(log n). Последовательная вставка отсортированных ключей в обычный BST создаёт цепочку высоты n, и операции становятся O(n). Самобалансирующийся вариант: Красно черное дерево.

Обходы

Обход	Порядок	Применение
pre-order	node, left, right	копирование структуры
in-order	left, node, right	сортированный порядок BST
post-order	left, right, node	обработка детей до родителя
breadth-first	по уровням	кратчайшая глубина, уровни

DFS выполняют рекурсией или явным stack, BFS — очередью. Время полного обхода O(n), память обычно O(h) для DFS и до O(w) для BFS, где w — ширина.

Удаление из BST

1. У leaf достаточно убрать ссылку родителя.
2. Узел с одним ребёнком заменяется ребёнком.
3. Узел с двумя детьми заменяется successor — минимумом правого поддерева — или predecessor, после чего удаляется перенесённый узел.

Важно обновить ссылку на root: удаляемый узел может быть корнем.

Связанные темы: Рекурсия, Big O, Comparator Java.

Вопросы для собеседования

1. Любое бинарное дерево является BST? Нет, BST добавляет инвариант порядка.
2. От чего зависит сложность поиска? От высоты h.
3. Как получить ключи BST по возрастанию? In-order обходом.
4. Что случится при вставке 1, 2, 3, 4 в обычный BST? Получится цепочка.
5. Как удалить узел с двумя детьми? Заменить successor/predecessor и удалить его из прежнего места.
6. Чем DFS отличается от BFS по памяти? DFS хранит путь, BFS — фронт уровня.
7. Где определить политику дубликатов? В контракте дерева и операции вставки.