Двоичное дерево поиска

Двоичное дерево поиска: как это работает?

Каждый узел делит своё поддерево надвое. Слева всё меньше, справа всё больше.

Поиск сравнивает цель с текущим узлом. Сравнение выбирает одного потомка и отбрасывает другого.

Вставка идёт тем же путём вниз. Новый узел становится потомком последнего достигнутого.

Правило касается целых поддеревьев, а не только прямых потомков. Левый внук всё равно обязан быть меньше корня.

Симметричный обход читает значения по возрастанию. Именно на это свойство опирается большинство задач.

Отсортированный вход строит одну длинную цепочку. Тогда операция стоит n, и лечит это балансировка.

Источники: Википедия: Двоичное дерево поиска

1. корень = 5Вставляем 5, 3, 8 и 4. Первое значение становится корнем.
2. 3 уходит влевоТройка меньше пятёрки. Она становится левым потомком.
3. 8 уходит вправоВосьмёрка больше пятёрки. Она становится правым потомком.
4. 4 идёт влево, потом вправоЧетвёрка меньше пятёрки, но больше тройки.
5. симметричный обход: 3, 4, 5, 8Чтение по порядку даёт отсортированные значения.

function insert(node, val) {
    if (!node) return { val, left: null, right: null };
    if (val < node.val) node.left = insert(node.left, val);
    else if (val > node.val) node.right = insert(node.right, val);
    return node;
}

interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}

function insert(node: TreeNode | null, val: number): TreeNode {
    if (!node) return { val, left: null, right: null };
    if (val < node.val) node.left = insert(node.left, val);
    else if (val > node.val) node.right = insert(node.right, val);
    return node;
}

def insert(node, val):
    if not node:
        return TreeNode(val)
    if val < node.val:
        node.left = insert(node.left, val)
    elif val > node.val:
        node.right = insert(node.right, val)
    return node

function insert(?TreeNode $node, int $val): TreeNode {
    if ($node === null) return new TreeNode($val);
    if ($val < $node->val) $node->left = insert($node->left, $val);
    elseif ($val > $node->val) $node->right = insert($node->right, $val);
    return $node;
}

    public static TreeNode insert(TreeNode node, int val) {
        if (node == null) {
            TreeNode fresh = new TreeNode();
            fresh.val = val;
            return fresh;
        }
        if (val < node.val) node.left = insert(node.left, val);
        else if (val > node.val) node.right = insert(node.right, val);
        return node;
    }

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    public static TreeNode Insert(TreeNode node, int val) {
        if (node == null) return new TreeNode { val = val };
        if (val < node.val) node.left = Insert(node.left, val);
        else if (val > node.val) node.right = Insert(node.right, val);
        return node;
    }

    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

Двоичное дерево поиска: разбор примера

Проверить, что дерево является деревом поиска

Определите, соблюдает ли двоичное дерево правило дерева поиска.

Все значения слева обязаны быть меньше, а все значения справа больше.

Сравнения узла с двумя его потомками недостаточно.

Вместо этого несите вниз нижнюю и верхнюю границу. Каждый шаг ужимает одну из них.

function isValidBST(root, low = -Infinity, high = Infinity) {
    if (!root) return true;

    // the bound comes from an ancestor, not from the parent alone
    if (root.val <= low || root.val >= high) return false;

    return isValidBST(root.left, low, root.val)
        && isValidBST(root.right, root.val, high);
}

Двоичное дерево поиска: когда применять?

Паттерн «Двоичное дерево поиска» нужен, когда в условии есть слова «двоичное дерево поиска: left < node < right в каждом узле», «вставка/удаление/поиск с сохранением порядка данных» или «проверить BST / k-й наименьший / симметричный обход даёт отсортированную последовательность». Решение на нём обычно укладывается в O(log n) avg.

• •двоичное дерево поиска: left < node < right в каждом узле
• •вставка/удаление/поиск с сохранением порядка данных
• •проверить BST / k-й наименьший / симметричный обход даёт отсортированную последовательность
• •ближайшее значение или запрос по диапазону на множестве, которое меняется со временем
• •массив заранее не дан, значения приходят по одному

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

Двоичное дерево поиска: с чем путают?

Паттерн «Двоичное дерево поиска» чаще всего путают с этими паттернами: Бинарный поиск (массив), Хеш-множество / словарь, Бинарная куча / очередь с приоритетом и Обход дерева.

• Бинарный поиск (массив) (Binary search (array)): Массив делится пополам по индексу, но вставка в него дорога. Дерево делится по указателю и вставку берёт.
• Хеш-множество / словарь (Hash set / map): Словарь быстрее для точного поиска. Дерево ещё отвечает про диапазоны и даёт порядок.
• Бинарная куча / очередь с приоритетом (Binary heap / priority queue): Куча обещает только минимум в корне. Дерево поиска упорядочивает каждую пару узлов.
• Обход дерева (Tree traversal): Та страница про обход всего дерева. Эта про правило упорядочивания.

Двоичное дерево поиска: частые ошибки

• Проверяют только прямых потомков

  Глубокий узел может нарушить правило относительно дальнего предка. Передавайте границы вниз.

• Считают дерево сбалансированным

  Отсортированные вставки строят цепочку, а не дерево. Тогда log n на деле равно n.

• Не решают, куда идут дубликаты

  Условие обязано сказать, в какую сторону идёт повтор. Выберите сторону и держитесь её.

• Небрежно удаляют узел с двумя потомками

  Узел с двумя потомками заменяют следующим по порядку узлом. Любой другой ломает упорядоченность.

Двоичное дерево поиска: задачи с собеседований

Паттерн «Двоичное дерево поиска» решает такие задачи с собеседований: Проверка дерева поиска, Поиск в дереве поиска, Вставка в дерево поиска, Удаление узла из дерева поиска, K-е наименьшее в дереве поиска, Наименьший общий предок в дереве поиска и Дерево поиска из отсортированного массива.

• Проверка дерева поиска: Несите вниз нижнюю и верхнюю границу.
• Поиск в дереве поиска: Одно сравнение отбрасывает половину дерева.
• Вставка в дерево поиска: Спуститесь вниз и подвесьте узел к последнему.
• Удаление узла из дерева поиска: Заменяйте его следующим по порядку узлом.
• K-е наименьшее в дереве поиска: Прервите симметричный обход после k узлов.
• Наименьший общий предок в дереве поиска: Первый узел, оказавшийся между двумя значениями.
• Дерево поиска из отсортированного массива: Средний элемент становится корнем, дальше рекурсия.

Двоичное дерево поиска: сложность по времени и памяти

У паттерна «Двоичное дерево поиска» целевая сложность O(log n) avg.

Сбалансированное дерево при n до 1e6 даёт O(log n) на операцию. Несбалансированное вырождается в O(n).