Деревья

Дерево — структура, где у каждого узла есть один родитель (кроме корня) и сколько угодно детей. Файловая система на компьютере — настоящее дерево: папки внутри папок, в самом верху — корень.

Бинарное дерево поиска (BST) — у каждого узла максимум два ребёнка, и есть правило порядка: всё, что меньше узла — слева, всё, что больше — справа.

class Node {
    int value;
    Node left, right;
    Node(int value) { this.value = value; }
}

Копнуть глубже

Поиск в BST — O(log n) в среднем, потому что на каждом шаге сравнения отбрасывается половина дерева — та же идея, что у бинарного поиска (см. тему «Бинарный поиск»):

boolean contains(Node node, int target) {
    if (node == null) return false;
    if (node.value == target) return true;
    return target < node.value
        ? contains(node.left, target)
        : contains(node.right, target);
}

Главная ловушка — несбалансированное дерево. Если вставлять отсортированные данные подряд (1, 2, 3, 4…), BST вырождается в обычный связный список — поиск падает до O(n). Решают это самобалансирующиеся деревья (как красно-чёрное дерево у TreeMap — см. тему «Устройство HashMap / TreeMap»), которые гарантируют O(log n) даже в худшем случае.

🎤 Закрыл тему, если можешь объяснить:

• что такое дерево и правило бинарного дерева поиска;
• почему поиск в BST O(log n) и когда он вырождается в O(n) (если дошёл до 2-го слоя).