Конспект: двоичное дерево поиска

Понятия

Двоичное дерево поиска (BST) - узлы с ключом и двумя ссылками; ИНВАРИАНТ: в каждом узле всё левое поддерево меньше ключа, всё правое больше (свойство глобальное - для всего поддерева, не только для детей).

Поиск / вставка / min / max - спуск по одному пути от корня, отсекая на каждом узле целое поддерево. Цена O(h), где h - высота.

Удаление - три случая: ЛИСТ (отцепить), ОДИН ребёнок (подставить его), ДВА ребёнка (заменить ключ на ПРЕЕМНИКА = минимум правого поддерева, затем удалить преемник - у него нет левого ребёнка, лёгкий случай). Можно и через предшественника (максимум левого). Тоже O(h).

Обходы (Θ(n), узел посещается раз): - СИММЕТРИЧНЫЙ (левое-узел-правое) - для BST ключи по ВОЗРАСТАНИЮ; - ПРЯМОЙ (узел-левое-правое) - копия/сериализация сверху вниз; - ОБРАТНЫЙ (левое-правое-узел) - удаление, свёртка снизу вверх (размер, высота, сумма); - В ШИРИНУ (BFS) - по уровням через очередь.

Вырождение - обычный BST не гарантирует баланс; отсортированный ввод уводит каждый ключ в одну сторону, дерево становится ЦЕПОЧКОЙ высотой h = n, операции деградируют до Θ(n).

Что унести

Дерево поиска - динамическое упорядоченное множество: и быстрый поиск (как в массиве), и дешёвые вставка/удаление (как в списке), плюс порядок в любой момент (симметричный обход). Цена всего - ВЫСОТА.

Главная мысль раздела: скорость дерева = его высота, поэтому любое дерево поиска оценивают по тому, какую высоту оно гарантирует. Обычный BST не гарантирует ничего (вырождается на упорядоченных данных - логи, id, импорт), поэтому в проде используют СБАЛАНСИРОВАННЫЕ деревья (следующая глава). Симметричный обход - способ достать порядок наружу за один проход; место посещения узла (до/между/после детей) задаёт назначение обхода.

Ловушки джокера

Проверять инвариант только у детей. Свойство глобальное; ключ может быть ок с родителем, но нарушать порядок с дальним предком - поиск промахнётся.

При удалении с двумя детьми поднять произвольного ребёнка. Осиротеет второе поддерево. Нужен преемник (или предшественник) - подмена одного ключа.

Забыть убрать старый узел преемника после копирования ключа - ключ окажется дважды.

Ждать возрастания от любого обхода. Только симметричный и только на BST.

Удалять дерево прямым/симметричным обходом - освободишь узел раньше детей, утечка. Для удаления - обратный.

Голый BST на отсортированных/потоковых данных. Вырождение в цепочку, Θ(n) вместо Θ(log n). Бери сбалансированное дерево.

Ждать Θ(log n) от обычного BST. Это свойство СБАЛАНСИРОВАННОГО; цена - высота, а высота не гарантирована.

Проверь себя

В чём инвариант BST и почему он должен держаться во всём поддереве?

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

Какой обход даёт возрастание, какой - для копии, какой - для удаления?

Почему отсортированный ввод вырождает BST и во что превращается дерево?

Почему цена операций - это высота, а не число узлов?