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

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

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

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

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

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

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

Отсортированный вход строит одну длинную цепочку. Тогда операция стоит 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;
}

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

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

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

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

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

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

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-й наименьший / симметричный обход даёт отсортированную последовательность
• •ближайшее значение или запрос по диапазону на множестве, которое меняется со временем
• •массив заранее не дан, значения приходят по одному

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

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

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

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

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

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

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

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

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

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

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

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

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

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

O(log n) avg

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