Инвариант бинарного дерева поиска

В BST 5(3,7) поиск 6 сравнивается с 5 и идёт вправо, затем с 7 и идёт влево к null: двух сравнений достаточно, чтобы доказать отсутствие ключа.

Инвариант охватывает целые поддеревья

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

Вставка повторяет неудачный поиск

Чтобы вставить ключ, спускайтесь по тем же сравнениям, пока нужная ссылка не станет пустой. Новый узел занимает это место. Стоимость поиска и вставки равна O(h), где h — текущая высота, потому что меняется только один путь.

Удаление разбирается на три структурных случая

1. Лист можно отсоединить от родителя.
2. Узел с одним ребёнком заменяется этим ребёнком.
3. Узлу с двумя детьми нужен ключ, сохраняющий обе области порядка. Обычно берут преемник — минимум правого поддерева — или симметричный предшественник, максимум левого. Затем удаляют перенесённый узел в более простом случае.

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

Почему «бинарное» не означает «логарифмическое»

Вырожденное дерево после вставок уже отсортированных ключей превращается в цепочку: высота и операции становятся O(n). Сбалансированные деревья ограничивают высоту O(log n) с помощью поворотов и дополнительных инвариантов. Этим объясняется существование AVL/Red-Black Tree и упорядоченных map/set, но обычный самописный BST такой гарантии не даёт.

BST выбирают, когда нужен динамический упорядоченный набор: минимум, максимум, следующий/предыдущий ключ или диапазонный обход. Для одного поиска по неизменяемому отсортированному массиву бинарный поиск проще и плотнее в памяти; для только точного членства хеш-множество обычно даёт более дешёвую ожидаемую операцию.

Как искать ключ в бинарном дереве поиска?

Найти узел с target в бинарном дереве поиска.

Обход всех узлов как в обычном дереве

Обойти DFS все узлы как в обычном бинарном дереве за O(n).

Почему полный DFS игнорирует порядок BST?

Полный обход игнорирует инвариант порядка.

Сравнение с узлом исключает целое поддерево

Если target меньше ключа узла, в правом поддереве его быть не может; при большем симметрично исключается левое.

В какой области может оставаться target?

Если target существует, он находится в поддереве current; каждый шаг сохраняет это утверждение и удаляет невозможную половину.

Спускаемся только в одну выбранную ветвь

Начать с корня. Пока current не null: при равенстве вернуть узел; при меньшем target перейти left, иначе right.

Поиск в BST на C++17 и Python 3

C++17

#include <cassert>
using namespace std;

struct Node {
    int value;
    Node* left;
    Node* right;
};

Node* search(Node* root, int target) {
    Node* current = root;
    while (current != nullptr) {
        if (current->value == target) return current;
        if (target < current->value) current = current->left;
        else current = current->right;
    }
    return nullptr;
}

int main() {
    Node left{3, nullptr, nullptr};
    Node right{7, nullptr, nullptr};
    Node root{5, &left, &right};
    assert(search(&root, 7) == &right);
    assert(search(&root, 6) == nullptr);
}

Python 3

class Node:
    def __init__(
        self,
        value: int,
        left: "Node | None" = None,
        right: "Node | None" = None,
    ) -> None:
        self.value = value
        self.left = left
        self.right = right


def search(root: Node | None, target: int) -> Node | None:
    current = root
    while current is not None:
        if current.value == target:
            return current
        if target < current.value:
            current = current.left
        else:
            current = current.right
    return None


root = Node(5, Node(3), Node(7))
assert search(root, 7) is root.right
assert search(root, 6) is None

Время определяется высотой, а не числом узлов напрямую

O(h) времени и O(1) памяти итеративно. В сбалансированном BST h=O(log n), в вырожденном h=O(n).

Пустое дерево, дубликаты и вырожденная форма

Пустое дерево; target в корне; отсутствующий ключ; вырожденное дерево; дубликаты требуют заранее выбранной политики.

Тесты на найденный лист и отсутствующий ключ

null; поиск корня; поиск листа; отсутствующее значение между ключами; цепочка.

Как узнать, что дан именно BST?

Структура поддерживает глобальный порядок «все ключи слева меньше, справа больше» после каждой операции.

Почему правило не работает в произвольном бинарном дереве?

Произвольное бинарное дерево не является BST; нельзя выбирать ветвь только по сравнению значений.

Мини-проверка: всегда ли поиск логарифмический?

Вопрос: гарантирует ли форма дерева логарифмический поиск? Ответ: нет; без балансировки высота может стать n.

Мини-проверка: зачем политика дубликатов?

Вопрос: почему политика дубликатов важна? Ответ: она определяет, в какой ветви искать равный ключ и сохраняется ли инвариант.

Проследите поиск отсутствующего ключа 6

Постройте BST вставками 5,3,7,6,8 и проследите поиск 6 и отсутствующего 4.

Найдите диапазон ключей в BST самостоятельно

Задача 1

Проверьте, является ли произвольное бинарное дерево строгим BST без дубликатов.

Порядок BST позволяет исключать одну ветвь целиком

BST — это прежде всего инвариант порядка; скорость поиска определяется высотой, а не словом «бинарное».