Вырождение BST: когда дерево - это список

Если ты понимаешь, почему вставка отсортированных ключей вырождает BST в список высотой n, почему тогда операции становятся Θ(n), и что это мотивирует балансировку, листай до «Теперь сам».

Как думаешь, всегда ли BST даёт log n

Мы говорили: операции BST стоят O(h), а у сбалансированного дерева h = Θ(log n). Но приглядись к оговорке «сбалансированного». Что делает высоту маленькой? То, что дерево РАЗВЕТВЛЯЕТСЯ - на каждом уровне узлов вдвое больше, поэтому n узлов умещаются в log n уровней. А что если оно не ветвится? Обычный BST не следит за формой - он просто вставляет ключ туда, куда приводит спуск. Подберём вставки так, чтобы каждый новый ключ становился в одну и ту же сторону, - и ветвления не будет вовсе. Дерево вытянется в линию. Тогда h уже не log n, а полное n, и «дерево» превратится в самый обычный список - с его медленным поиском.

На что это похоже

Стопка бумаг, куда каждую новую кладут строго сверху, потому что она «больше» предыдущей. Формально это «отсортированная стопка», но чтобы найти нужный лист, ты перебираешь её сверху донизу - один за другим. Никакой экономии от порядка: стопка - это список. А ведь если бы ты раскладывал бумаги по папкам-разделителям (ветвление), нашёл бы нужную за пару шагов. Дерево поиска на отсортированном вводе - ровно такая стопка: порядок есть, а прыгать нельзя, потому что «развилки» все ведут в одну сторону. Балансировка - это и есть привычка раскладывать по разделителям, а не в одну стопку.

Механизм: как отсортированный ввод строит цепочку

Вставляем в пустое дерево 1, 2, 3, 4, 5 по возрастанию:

вставили 1 -> корень 1
вставили 2 -> 2 > 1, вправо от 1
вставили 3 -> 3 > 1 вправо, 3 > 2 вправо
вставили 4 -> вправо, вправо, вправо
вставили 5 -> вправо ×4

Каждый ключ больше всех предыдущих, поэтому спуск всегда сворачивает ВПРАВО и подвешивает узел в самый низ правой ветки. Левых поддеревьев не возникает вовсе. Получается цепочка: 1 → 2 → 3 → 4 → 5, высота h = n = 5. Теперь поиск 5 идёт через все пять узлов - Θ(n), ровно как перебор списка. То же с почти отсортированным вводом (высота близка к n) и с обратно отсортированным (цепочка влево).

Правило

Обычный BST НЕ гарантирует баланс. При вставке ключей в отсортированном (или обратно отсортированном) порядке каждый новый ключ уходит в одну сторону, дерево вырождается в ЦЕПОЧКУ высотой h = n, и все операции деградируют с Θ(log n) до Θ(n) - как у связного списка. Отсортированные и почти отсортированные данные встречаются постоянно, поэтому это не экзотика. Отсюда необходимость БАЛАНСИРОВКИ - механизма, который держит h = Θ(log n) при любом порядке вставок.

Разбор: почему именно отсортированный ввод - худший случай

Стоит понять, что вырождение - не случайная неудача, а закономерность формы. Высота мала, когда на каждом узле оба поддерева примерно равны (ветвление пополам, как в двоичном поиске). Высота велика, когда одно поддерево всё время пустое - тогда каждый узел добавляет к высоте единицу. Отсортированный ввод даёт ровно это: новый максимум цепляется к правому краю, левых поддеревьев не образуется - идеальный «однобокий» рост. Это тот же сюжет, что у быстрой сортировки с плохим опорным (раздел про сортировки): фиксированная стратегия + «удобно упорядоченный» вход = худший случай. И, как и там, беда в том, что такой вход РЕАЛЕН и даже типичен: данные часто приходят по времени, по возрастанию id, уже частично упорядоченными. Полагаться на «обычно данные перемешаны» нельзя.

Разбор: почему высота - это ровно цена, и что значит её удержать

Мы всё время говорим O(h) - подчеркнём, почему именно высота, а не число узлов, определяет скорость. Поиск, вставка, удаление, min/max - все идут по ОДНОМУ пути от корня вниз; длина самого длинного такого пути и есть высота. Значит скорость дерева = его высота, и весь вопрос проектирования дерева сводится к одному: КАК ДЕРЖАТЬ ВЫСОТУ МАЛЕНЬКОЙ. Идеал недостижим (после каждой вставки идеально перестраивать дерево дорого), но достаточно держать высоту в пределах O(log n) - тогда все операции O(log n). Именно это делают сбалансированные деревья (АВЛ, красно-чёрные - следующая глава): после каждой вставки/удаления они чуть-чуть перестраивают дерево локальными поворотами, не давая ему стать однобоким. Понимание «высота = цена» - ключ ко всему разделу: любое дерево поиска оценивают по тому, какую высоту оно гарантирует.

Что ломается без этого

Первая ошибка - использовать обычный BST для данных, приходящих по порядку (логи по времени, автоинкрементные id, отсортированный импорт): получишь цепочку и Θ(n) на операцию - хуже, чем просто массив. Вторая - тестировать BST только на СЛУЧАЙНЫХ данных: на них он в среднем Θ(log n) и выглядит хорошо, а на отсортированном входе разваливается; худший случай надо проверять специально. Третья - думать, что Θ(log n) - свойство самого BST: это свойство СБАЛАНСИРОВАННОГО дерева; обычный BST такой гарантии не даёт. Четвёртая - лечить вырождение «перемешаем данные перед вставкой»: иногда помогает (рандомизация, как у деревьев дальше), но в общем случае поток данных перемешать нельзя, и нужна структурная балансировка.

Зачем это в работе

Вырождение BST - причина, по которой в реальных библиотеках НЕ используют голый BST, а всегда берут сбалансированные деревья: std::map/std::set, TreeMap/TreeSet - красно-чёрные; индексы БД - B-деревья. Все они появились именно чтобы победить вырождение и гарантировать O(log n) в ХУДШЕМ случае, а не только в среднем. Понимать вырождение - значит, во-первых, не писать своё «дерево поиска» без балансировки для потоковых или отсортированных данных (классическая ошибка новичка, дающая внезапные тормоза на проде); во-вторых, ценить, за что именно платят сложностью АВЛ и красно-чёрных деревьев - за железную гарантию высоты. Это тот же мотив, что у медианы медиан против рандомизированного выбора: иногда нужна не «обычно быстро», а «быстро всегда». Следующая глава - как это устроено.

Теперь сам

В пустой BST вставляют 10, 20, 30, 40. Какой формы выйдет дерево, чему равна высота и сколько сравнений займёт поиск 40? Как бы изменилась картина, если бы дерево балансировалось?