DS Структуры данных Структура данных
Двоичное дерево поиска
Также: Binary search tree · BST · дерево поиска · TreeMap · порядковая статистика · удаление Хиббарда
Ключи, разложенные по веткам: меньшие налево, большие направо. Поиск, вставка, ближайший ключ и k-й по порядку стоят столько сравнений, какова высота дерева. На случайном порядке вставки это логарифм, а каталог землетрясений, вставленный по времени, вырастает в палку высотой 19 073. И порядок по времени — не единственный способ испортить дерево реальными данными.
В каталоге USGS 19 073 землетрясения силой от 5 за 2015–2025 годы. Положим их в двоичное дерево поиска в том порядке, в каком они случались, с ключом — временем. Каждый новый толчок позже всех прежних и уходит от корня направо, направо и ещё раз направо: дерево вырастает в палку высотой 19 073. Поменяйте ключ на долготу — и из тех же событий, пришедших в том же порядке, вырастет куст высотой 36. Попробуйте силу и глубину: там подвох, которого на учебных примерах не видно.
На графике под силуэтом оси логарифмические по высоте. Зелёный пунктир — высота идеального дерева, ⌈log₂(n + 1)⌉: для всего каталога это 15. Серая точечная линия — сколько сравнений в среднем стоит поиск, если ключи пришли в случайном порядке; к 19 073 узлам это 17,9. Время вразброс ложится на неё: средняя глубина 17,31, высота 33. Время по порядку уходит вверх по диагонали: средняя глубина 9537, и чтобы найти сильнейшее землетрясение каталога, M8,8 у Камчатки 29 июля 2025 года, дереву нужно 17 977 сравнений: по одному с каждым более ранним толчком и последнее — с ним самим. Вставка всех событий стоила 181 880 128 сравнений.
Идея
Каждый узел хранит ключ, и в его левой ветке лежат только меньшие ключи, а в правой — только большие. Поиск сравнивает искомый ключ с корнем и уходит в одну ветку, отбрасывая другую целиком, — так же, как двоичный поиск отбрасывает половину массива. Вставка идёт тем же путём и вешает новый лист там, где ветки не оказалось. Любая операция стоит столько сравнений, какова высота дерева, а высоту задаёт порядок, в котором приходили ключи.
Отсортированный массив с двоичным поиском делает те же сравнения, но вставка в середину сдвигает хвост. Дерево поиска — двоичный поиск, застывший в ссылках: вместо «середины отрезка» у каждого узла есть готовые левая и правая половины, и новый ключ встаёт на место без всяких сдвигов. Как сажать, искать и срезать ключи, как обходить дерево и чем его подрезают повороты, подробно и с садом, где всё это можно потрогать, рассказано в главе курса о деревьях поиска. Здесь — о том, от чего зависит высота и как дерево ведёт себя на настоящих данных.
Высоту задаёт порядок
Если ключи приходят по возрастанию, каждый новый больше всех прежних, и дерево — палка: k-й ключ ложится на глубину k, вставка всех стоит n(n − 1)/2 сравнений. Для каталога это 19 073 · 19 072 / 2 = 181 880 128 — ровно то, что насчитала сцена. А если порядок случайный, дерево получается низким, и это можно доказать.
Пусть n разных ключей вставляют в пустое дерево поиска в случайном порядке: все n! порядков равновероятны. Тогда средняя по ключам ожидаемая глубина узла — то есть среднее число сравнений при успешном поиске — равна 2(1 + 1/n)Hn − 3, где Hn = 1 + 1/2 + … + 1/n ≈ ln n.
Пронумеруем ключи по возрастанию от 1 до n. Ключ i — предок ключа j ровно тогда, когда среди ключей с номерами от i до j включительно первым вставили i. Действительно, пока ни один из них не вставлен, все они спускаются по дереву одним путём: любой узел на пути меньше их всех или больше их всех. Первый вставленный из них встаёт на этот путь, и остальные проходят через него. Если первым был i, ключ j проходит через i, и i — его предок; если первым был кто-то третий, он разводит i и j по разным веткам, и предком друг другу они уже не станут.
При случайном порядке каждый из |i − j| + 1 ключей отрезка первый с одной и той же вероятностью, поэтому i — предок j с вероятностью 1/(|i − j| + 1). Глубина j — это единица плюс число предков, и её среднее равно 1 + (Hj − 1) + (Hn−j+1 − 1). Усредним по j, пользуясь тем, что H1 + … + Hn = (n + 1)Hn − n: получится 2(1 + 1/n)Hn − 3.
Это примерно 2 ln n ≈ 1,39 log₂ n сравнений — логарифм с небольшим множителем. Высота, то есть худший поиск, больше среднего, но тоже логарифм: с большой вероятностью около 4,311 ln n для очень больших n, это результат Люка Деврое 1986 года. На каталоге вразброс высота 33 при идеальных 15.
Первый абзац доказательства — та же картина, что у быстрой сортировки с опорным элементом из начала: первый вставленный ключ, как опорный, сравнивается со всеми остальными и делит их на две независимые части. Дерево, выращенное из последовательности, и такая сортировка делают одни и те же сравнения, и у обеих одинаково плохой вход — уже упорядоченный.
Подвох реальных данных
Учебная оговорка звучит так: «если ключи приходят в отсортированном порядке». На настоящих данных дерево портится и без этого. Переключите сцену на силу. Толчки приходят по времени, а сила от времени не зависит, и кажется, что порядок случайный. Но разных значений силы в каталоге всего 83, и у 4729 толчков она ровно 5,0. Равные ключи надо как-то различать, и естественный способ — по номеру в каталоге, то есть по времени. Внутри группы M5,0 ключи снова приходят по возрастанию, и 4729 толчков выстраиваются в цепочку: высота 4733.
С глубиной ещё нагляднее: высота 8350. У 8349 землетрясений каталога глубина ровно 10 километров. Это не геология: такое значение USGS ставит, когда данных не хватает, чтобы глубину вычислить, — чаще всего потому, что ближайшая сейсмостанция слишком далеко. Почти половина каталога оказалась одним ключом, а одинаковые ключи с возрастающей добавкой — это отсортированный вход в маскировке. Долгота такого не делает: высота 36 при идеальных 15, почти как у перемешанного времени.
Отсюда три практических правила. Подозревайте любые данные, которые растут сами: номера заказов, отметки времени, автоинкрементные ключи. Проверяйте, сколько разных значений у ключа на самом деле. И держите равные ключи в одном узле — списком или счётчиком, — а не цепочкой узлов.
Порядок как услуга: k-й, ранг, ближайший
Ради одного поиска по ключу дерево заводить незачем: хеш-таблица находит ключ за одну-две пробы. Дерево нужно, когда важен порядок. Ближайший ключ не больше заданного — floor — спускается от корня и запоминает последний узел, где ключ оказался не больше искомого. Все ключи из диапазона — обход, который не заходит в ветки за пределами диапазона: O(h + k) на k найденных. А если в каждом узле хранить размер его поддерева, дерево отвечает и на вопросы о номерах.
k-й по порядку (select): в корне смотрим на размер левого поддерева L. Если k ≤ L, искомый слева; если k = L + 1, это сам корень; иначе он справа, и там нужен (k − L − 1)-й. Ранг — сколько ключей меньше данного — тот же спуск наоборот: где путь поворачивает направо, к ответу прибавляется левое поддерево и сам узел. Размеры поправляются при каждой вставке и удалении на пути от корня, так что всё по-прежнему стоит O(h).
Здесь 21 землетрясение силой от 7,8 за 2015–2025 годы. Ключ — время, а вставляли их от сильного к слабому, как в листинге bst: первым встал камчатский толчок 2025 года, и, поскольку он почти самый поздний, всё дерево, кроме одного узла, ушло в его левую ветку. Высота 8 при идеальных 5. Переключите вставку на «по времени» — получится палка высотой 21. Кнопка «Удалить корень» показывает удаление по Хиббарду: у корня два ребёнка, и на его место встаёт преемник — самый левый узел правого поддерева, то есть следующий ключ по порядку.
Томас Хиббард в 1962 году доказал, что случайное удаление его способом из случайного дерева оставляет дерево случайным. В 1975 году Гэри Нотт обнаружил, что последующая вставка эту случайность разрушает. Дальше опыты Джеффри Эппинджера (1983) показали, что долгая череда случайных вставок и удалений уводит дерево от «случайной» формы, а Джозеф Калберсон и Иэн Манро в 1990 году доказали для одной модели таких обновлений, что средний поиск тогда стоит порядка √n. Обычно это объясняют асимметрией: удаление всегда берёт преемника справа, и левые ветки понемногу перевешивают. Сбалансированные деревья от этой болезни не страдают.
Код
Дерево поиска с размерами поддеревьев: поиск, вставка, select, rank, floor и удаление Хиббарда. В Go вставка идёт по указателю на ссылку: переменная link указывает на то поле, куда нужно записать новый узел, — на корень или на поле left или right родителя, и отдельного случая «дерево пустое» не нужно. Данные — те же 21 землетрясение из каталога.
21 quakes, inserted strongest first: height 8 the same quakes inserted in time order: height 21 select(11), the median by time: 2018-01-23 M7.9 rank(2020-01-01): 14 of them came before 2020 floor(2023-01-01), the last one before 2023: 2021-08-12 M8.1 after deleting the root: root 2025-09-18, 20 nodes, height 8
Теперь каталог, но за один 2025 год: на всех одиннадцати годах палка из 19 073 узлов стоит 182 миллиона сравнений, и Python на сервере сайта считал бы их слишком долго. Пять ключей, те же, что в сцене; переключите в ней «только 2025» — числа совпадут.
2128 earthquakes of 2025 a perfect tree: height 12; a random order: 13.49 on average key, in order of time height avg depth comparisons time 2128 1064.50 2,263,128 magnitude 550 160.38 339,171 depth 1030 263.15 557,845 longitude 26 14.86 29,488 time, shuffled 24 12.83 25,180
Сколько это стоит
| Операция | Время | Случайный порядок | Худший случай |
|---|---|---|---|
| поиск, вставка, удаление | O(h) | O(log n) | O(n) |
| минимум, максимум, floor, ceiling | O(h) | O(log n) | O(n) |
| k-й по порядку, ранг (с размерами) | O(h) | O(log n) | O(n) |
| все ключи из диапазона | O(h + k) | ||
| обход всех по порядку | O(n) |
Память — O(n), но с накладными расходами: две ссылки на каждый ключ, у дерева с размерами ещё и счётчик. Каждый шаг вниз — переход по ссылке в другое место памяти, и всё, что в статье о связном списке сказано про кэш, верно и здесь. Поэтому на небольших объёмах отсортированный массив с двоичным поиском и вставкой сдвигом хвоста часто быстрее дерева. Замер — вставка n ключей: дерево на случайных ключах, оно же на возрастающих и отсортированный массив.
Палка растёт линейно на ключ, квадратично на всё, и на десяти тысячах ключей в Go она в шестьдесят с лишним раз медленнее того же дерева на случайных ключах. Отсортированный массив тоже растёт линейно — на сдвиг хвоста, — но сдвиг — это одна быстрая копия памяти. В Go дерево всё равно выигрывает уже с трёх тысяч ключей, а в Python список с bisect быстрее дерева из объектов на всех размерах замера, до тридцати тысяч ключей. Популярная библиотека sortedcontainers из-за этого вовсе не строит деревьев: она держит отсортированный список кусками примерно по тысяче элементов и объясняет выбор тем, что дереву нужны лишние ссылки на каждый элемент, а плотный список лучше ложится в кэш.
Что делают с высотой на практике
Голое дерево поиска почти не используют там, где порядок ключей не под контролем. Три способа держать высоту логарифмической:
- Балансировать поворотами. АВЛ-дерево Георгия Адельсон-Вельского и Евгения Ландиса (1962) после каждой вставки проверяет, что высоты веток у узла различаются не больше чем на единицу, и чинит это поворотами; красно-чёрное дерево разрешает перекос чуть больше и поворачивает реже. На красно-чёрном дереве построен
TreeMapв Java. - Сделать порядок случайным самим. Декартово дерево даёт каждому ключу случайный приоритет и держит форму такой, какая была бы при случайном порядке вставки, — и тогда теорема выше работает при любом входе. Если все ключи известны заранее, их можно просто перемешать перед вставкой.
- Сделать дерево широким. B-дерево хранит в узле сотни ключей и остаётся идеально ровным по построению; на нём держатся индексы баз данных.
В стандартных библиотеках Python и Go упорядоченного дерева нет. Для упорядоченных данных там берут отсортированный массив с bisect или sort.Search, а когда вставок много — сторонние библиотеки или список с пропусками.
История
Двоичное дерево поиска около 1960 года придумали независимо несколько человек: в 1960 году о нём писали П. Ф. Уиндли в The Computer Journal и Эндрю Бут с Эндрю Колином. В 1962 году Томас Хиббард в Journal of the ACM разобрал, как ведут себя такие деревья, если ключи приходят в случайном порядке, и предложил удаление, которое теперь носит его имя. В том же году Адельсон-Вельский и Ландис опубликовали первое дерево, которое держит высоту логарифмической при любом порядке, — их история рассказана в главе курса.
Задачи
В первой задаче у индекса после сбоя поменялись местами два ключа, и найти их помогает обход, а не проверка каждого узла. Во второй нужно узнать высоту дерева из 200 тысяч ключей, не строя его: честная вставка на неудачном порядке стоит 2·10¹⁰ сравнений, а нужный ответ подсказывает связный список.
Два перепутанных ключа Высота без дереваДанные: Землетрясения: каталог USGS, общественное достояние