DATA·II Структуры данных Глава 17 из 65
Сад деревьев поиска
Сажаем ключи и смотрим, как растёт дерево поиска. Оно держит ключи по порядку и отвечает на вопросы «от и до», перед которыми хеш-таблица бессильна. Если сажать по порядку, вместо куста вырастает палка, и садовник учится подрезать ветки поворотами. Когда и как подрезать, в 1962 году придумали два московских математика.
Структуры данных
- 13 Сложность
- 14 Массивы
- 15 Стек и очередь
- 16 Хеш-таблицы
- 17 Деревья вы здесь
- 18 Кучи
- 19 Графы
Опирается на: 09 · Задача внутри задачи 12 · Остров кроликов и лис 13 · Сколько стоит программа
Что вы унесёте из главы
- сажать, искать и удалять ключи в двоичном дереве поиска и обходить его четырьмя способами
- почему дерево вырождается в палку и как повороты АВЛ-дерева держат высоту около log n
- отвечать на вопросы «все ключи от и до» и «следующий по порядку» — и узнавать деревья в файлах, HTML и JSON
Хеш-таблица из прошлой главы находит слово за одно действие, но не знает, какое слово идёт за ним по алфавиту, и на вопрос «все слова от „мир“ до „мирный“» отвечает перебором всего словаря. Порядок знает отсортированный список: в нём такие вопросы решает двоичный поиск, которым в главе 0 угадывали число за двадцать вопросов. У списка другая беда. Новое слово надо вставить в середину, а для этого сдвинуть весь хвост, как в главе 14. Модуль bisect находит место двоичным поиском и вставляет; сколько стоит сдвиг, покажет секундомер.
Вдвое больше чисел — вчетверо дольше: каждая вставка сдвигает в среднем половину списка, и в сумме выходит квадрат. Хеш-таблица вставляла бы быстро, но порядка она не помнит. Нам нужно и то и другое: чтобы ключи лежали по порядку, любой находился за несколько шагов, а новый вставал на место, ничего не сдвигая. Такую структуру выращивают, как растение, и эта глава — сад.
Семечко: узел с двумя ветками
Связный список из главы 14 был цепочкой узлов: у каждого — значение и ссылка на следующий. Дадим узлу две ссылки, левую и правую, и запретим ссылкам смыкаться в кольца и сходиться: на каждый узел, кроме верхнего, ведёт ровно одна ссылка. Получится дерево. Растёт оно, как принято у программистов, вниз. Верхний узел, у которого нет родителя, — корень. Узлы, у которых нет детей, — листья. Каждый узел вместе со всем, что растёт под ним, сам — дерево поменьше, его называют поддеревом или веткой. Такое определение через себя самого — та же рекурсия, что в папках главы 9, и потому почти всё с деревьями делается рекурсией.
Дерево, где у каждого узла не больше двух детей, называют двоичным. А чтобы в нём можно было искать, ключи раскладывают по одному правилу.
Двоичное дерево поиска: у каждого узла все ключи в левой ветке меньше его ключа, а все ключи в правой — больше.
Речь обо всех ключах ветки, не только о ближайшем ребёнке: правило касается каждого узла и всего, что под ним. Эта тонкость ещё всплывёт в задачах. Сам узел в Python — маленький класс, как в главе 12.
Посадка
Новый ключ ищет себе место от корня. Меньше корня — уходит в левую ветку, больше — в правую, и там сравнивается снова. Когда нужной ветки нет, место найдено: здесь и вырастет новый лист. Посадим героев «Войны и мира». Строки сравниваются по алфавиту, как в словаре, — это было в главе 6.
Двигайте ползунок под рисунком. Пьер пришёл первым и стал корнем навсегда. Наташа меньше Пьера — ушла налево. Андрей меньше Пьера и меньше Наташи — налево и ещё раз налево. Соня больше Пьера — направо. Каждый следующий спускается от корня, на каждом этаже выбирая одну из двух веток, и становится листом.
Присмотритесь к строке node.left = insert(node.left, key). Функция возвращает корень поддерева, и мы записываем его обратно в ветку. Если ветка была пустой, на её месте появится новый узел; если не была — вернётся тот же узел, и присваивание ничего не изменит. Забыть node.left = — самая частая ошибка: новый узел создаётся и тут же теряется. Посадите в сад свои ключи.
Как найти растение
Поиск идёт тем же путём, что посадка: сравнить с узлом, уйти в одну ветку, повторить. Кончается он либо на нужном ключе, либо в пустой ветке, и тогда ключа в дереве нет. Сравнений столько, сколько этажей пройдено. Число этажей на самом длинном пути от корня до листа называют высотой дерева: у одного узла она 1, у пустого дерева — 0. Высота — худший случай поиска.
Поиск здесь написан циклом, а не рекурсией: он идёт по одной ветке и не возвращается, так что стопка недоделанных дел ему не нужна. Запись a if условие else b выбирает одно из двух значений, это короткая форма if. Из девяти героев Марью искать дольше всех — шесть сравнений: она на шестом этаже. Наполеона, которого в дереве нет, — столько же: путь кончается под Марьей. В хорошем дереве высота растёт как логарифм числа ключей: в идеально ровном дереве высоты 20 помещается $2^{20} - 1$, больше миллиона узлов, и поиск любого стоит не больше двадцати сравнений. Бывают и плохие деревья, до них дойдём скоро.
Прогулка по саду
Чтобы напечатать или сосчитать все узлы, дерево надо обойти. В списке порядок обхода один, а в дереве у каждого узла три дела: он сам, левая ветка и правая. Порядок этих дел и даёт разные обходы. Прямой: сначала узел, потом левая ветка, потом правая. Симметричный: левая ветка, узел, правая. Обратный: обе ветки, потом узел. А обход в ширину идёт по этажам: корень, потом его дети, потом внуки — для него нужна очередь из главы 15.
Ради второй строки вывода дерево поиска и заводят. Симметричный обход выдаёт ключи по алфавиту: всё, что левее узла, меньше его и выходит раньше, всё, что правее, больше и выходит позже. Порядок, который хеш-таблица растеряла, здесь хранится в самой форме дерева, и если посадить ключи, а потом обойти дерево симметрично, получится сортировка.
Остальные обходы полезны в деревьях любого рода. Удобнее всего их сравнить на дереве, которое прячется в каждой формуле калькулятора из главы 15, — на арифметическом выражении. В выражении $(2 + 3) \cdot (7 - 4)$ последнее действие — умножение, оно в корне; его левая ветка — $2 + 3$, правая — $7 - 4$. Обведите такое дерево точкой по контуру, против часовой стрелки, начиная от корня.
Обратный обход выражения даёт 2 3 + 7 4 - * — обратную польскую запись, которую калькулятор HP-35 из главы 15 считает без скобок. Прямой даёт * + 2 3 - 7 4 — запись Лукасевича со знаком впереди. А симметричный — 2 + 3 * 7 - 4, привычную инфиксную запись, только без скобок. Смысл от этого изменился: дерево считает $5 \cdot 3 = 15$, а строка без скобок — $2 + 21 - 4 = 19$. Дерево помнит, что сначала складывают, строка этого уже не знает. Поэтому калькуляторы, компиляторы и сам Python, прочитав формулу или программу, первым делом строят из неё такое дерево. Мы займёмся этим в главе 50.
Срезать ветку
Удалять ключ труднее, чем сажать: дыру в середине дерева надо заделать так, чтобы правило поиска не нарушилось. Случаев три. Лист срезают, и всё. Узел с одной веткой заменяется этой веткой: она целиком лежит по ту же сторону от родителя, что и сам узел, так что правило не страдает. Остаётся узел с двумя ветками. Его место должен занять ключ, который больше всего в левой ветке и меньше всего в правой. Такой есть — это следующий по порядку ключ, преемник: самый левый узел правой ветки. У него нет левого ребёнка, иначе он не был бы самым левым, поэтому его самого срезать легко — это один из первых двух случаев.
Марья — лист, и она исчезает бесследно. У Андрея одна ветка, и Долохов поднимается на его место. У Наташи две ветки; её преемник по алфавиту — Николай, самый левый в её правой ветке. Николай переезжает на место Наташи, а его старый узел срезается. Этот способ описал Томас Хиббард в 1962 году — в статье, где одним из первых разобрал, как ведут себя деревья поиска, если ключи приходят в случайном порядке. В саду выше переключите режим на «Срезать» и попробуйте все три случая.
Палка вместо куста
Мы всё время говорили «в хорошем дереве». Каким оно вырастет, зависит только от порядка посадки. Посадите в саду ключи по возрастанию — кнопка «По порядку». Каждый новый ключ больше всех прежних, поэтому уходит направо, направо, направо. Вместо куста вырастает палка: связный список, положенный набок, где поиск стоит $n$ сравнений. А на Python бывает и хуже.
Сто тысяч ключей вперемешку дают высоту около сорока: больше, чем у идеального дерева (17), но тоже логарифм, только с множителем. Девятьсот ключей по порядку — высота 900. А две тысячи по порядку кончаются ошибкой RecursionError: рекурсивная посадка спускается по палке на две тысячи этажей и упирается в предел глубины из главы 9. Обидно, что упорядоченные данные встречаются сплошь и рядом: номера заказов растут, даты идут по порядку, файлы приходят уже отсортированными.
Эта болезнь вам уже встречалась. В главе 21 быстрая сортировка с опорным элементом — первым в списке — на отсортированном входе тоже ушла в рекурсию на тысячи уровней. Сходство не случайное: дерево поиска, выращенное из списка, и такая быстрая сортировка делают одни и те же сравнения. Первый ключ становится корнем и сравнивается со всеми остальными, как опорный элемент. Меньшие уходят налево, большие направо, и в каждой ветке её первый ключ снова становится опорным. Проверим счётчиком.
Числа совпадают до единицы при любом $n$. Значит, всё, что глава 21 знала о быстрой сортировке, верно и для дерева. На случайном порядке оба делают в среднем около $2 \ln n \approx 1{,}39 \log_2 n$ сравнений на ключ, если не считать слагаемых поменьше; на упорядоченном — квадрат. Сортировку тогда вылечил случайный опорный элемент. Дерево же не выбирает, в каком порядке к нему приходят ключи, и лечить придётся его форму.
Подрезка: повороты
Садовник не выкапывает куст, чтобы он рос ровнее: он подрезает ветки. Для дерева поиска есть такая операция — поворот. Возьмём узел $y$ с левым ребёнком $x$. Под ними три ветки: $A$ — левее $x$, $B$ — между $x$ и $y$, $C$ — правее $y$. Поворот направо поднимает $x$ на место $y$, а $y$ становится правым ребёнком $x$. Ветка $B$, которая была между ними, переходит к $y$ налево.
Правило поиска поворот не нарушает: симметричный обход до него и после даёт одну и ту же строку $A\ x\ B\ y\ C$. Меняется только форма, а с ней и высоты: если ветка $A$ была на этаж выше, чем $B$ и $C$, поворот поднимает её на этаж и опускает $C$ — и всё дерево становится на этаж ниже. На Python поворот — три присваивания.
Один поворот помогает, когда высокая ветка растёт «наружу» — у левого ребёнка слева. Если же она растёт «внутрь» — у левого ребёнка справа, — поворот лишь перекладывает перекос на другую сторону. Тогда делают два поворота: сначала налево вокруг ребёнка, чтобы выпрямить зигзаг, потом направо вокруг самого узла. Остаётся решить, когда подрезать. Это решили в Москве в 1962 году.
Москва, 1962. Садовники из ИТЭФ
Правило Адельсон-Вельского и Ландиса такое: у каждого узла высоты левой и правой ветки различаются не больше чем на единицу. Дерево, где оно выполнено, называют АВЛ-деревом. Каждый узел помнит высоту своей ветки. После посадки мы возвращаемся от нового листа к корню — рекурсия делает это сама, на обратном пути — и в каждом узле обновляем высоту и проверяем правило. Если разница стала два, подрезаем одним поворотом или двумя.
Тысяча ключей по порядку, которые дерево без подрезки превращало в палку, а рекурсию — в аварию, дают высоту 10. Это лучшее, что вообще возможно: в десяти этажах помещается не больше $2^{10} - 1 = 1023$ узлов. На случайных ключах АВЛ-дерево лишь на пару этажей выше идеального. Включите в саду выше «Садовника» и посадите ключи по порядку — повороты будут видны: узел, где нарушилось правило, вспыхнет, и куст повернётся.
Сколько этажей
Последняя колонка вывода — предел высоты, и его можно доказать. В доказательстве вдруг появляются числа Фибоначчи из главы 9.
АВЛ-дерево из $n$ узлов имеет высоту не больше $\log_\varphi (n + 1) \approx 1{,}44 \log_2 (n+1)$, где $\varphi = \frac{1 + \sqrt5}{2} \approx 1{,}618$ — золотое сечение.
Спросим наоборот: какое наименьшее число узлов $N(h)$ может быть в АВЛ-дереве высоты $h$? Пустое дерево — $N(0) = 0$, один узел — $N(1) = 1$. У самого худого дерева высоты $h$ корень, одна ветка высоты $h - 1$, а другая — настолько низкая, насколько разрешает правило, то есть высоты $h - 2$, и обе ветки сами самые худые. Значит, $N(h) = N(h-1) + N(h-2) + 1$.
Прибавим к обеим частям единицу: $N(h) + 1 = \big(N(h-1) + 1\big) + \big(N(h-2) + 1\big)$. Это правило чисел Фибоначчи, и с начальными значениями $N(0) + 1 = 1 = F_2$, $N(1) + 1 = 2 = F_3$ получаем $N(h) + 1 = F_{h+2}$. Индукцией легко проверить, что $F_k \ge \varphi^{k-2}$: для $F_2 = 1$ и $F_3 = 2$ это верно, а дальше $F_k = F_{k-1} + F_{k-2} \ge \varphi^{k-3} + \varphi^{k-4} = \varphi^{k-4}(\varphi + 1) = \varphi^{k-2}$, потому что $\varphi + 1 = \varphi^2$.
Выходит, в любом АВЛ-дереве высоты $h$ не меньше $N(h)$ узлов: $n + 1 \ge N(h) + 1 = F_{h+2} \ge \varphi^h$. Логарифмируя, $h \le \log_\varphi (n+1) = \frac{\log_2 (n+1)}{\log_2 \varphi} \approx 1{,}44 \log_2 (n+1)$.
Самые худые АВЛ-деревья так и называют — деревьями Фибоначчи. Для миллиона ключей теорема обещает не больше 28 этажей, то есть не больше 28 сравнений на поиск — при любом порядке посадки. Подрезка тоже дёшева: поворот меняет три ссылки, а обновлять высоты нужно только на пути от листа к корню, это $O(\log n)$ узлов. Получается то, чего мы хотели в начале главы: поиск, вставка и удаление за $O(\log n)$ в худшем случае, и ключи всегда по порядку.
Ответ хеш-таблице
Вернёмся к вопросам, на которых сломалась хеш-таблица. Посадим в АВЛ-дерево все слова «Войны и мира» — повторы дерево пропускает — и спросим, какие слова лежат между «мир» и «мирный» и какое слово идёт по алфавиту сразу за «наташа». Функция between — это симметричный обход, который не заходит в ветки, где нужных ключей заведомо нет: если узел меньше нижней границы, вся его левая ветка ещё меньше, и туда идти незачем.
Ответы те же, что дал словарь в конце прошлой главы, а работы — несравнимо меньше. Пятьдесят тысяч слов выросли в дерево высотой 19. Чтобы найти двенадцать слов от «мир» до «мирный», дерево осмотрело 26 узлов, а словарь — все 51 787. Следующее слово за «наташа» нашлось одним спуском от корня. В общем случае такой запрос стоит $O(\log n + k)$, где $k$ — сколько ключей попало в ответ: спуск к началу диапазона и шаги по самим ответам. Так база данных отвечает на «все заказы за март» или «все товары дешевле тысячи», не читая всю таблицу.
Деревья за забором
Деревья поиска — один вид в большом саду. Деревья вообще, где у узла сколько угодно детей, попадаются программисту на каждом шагу. Самое знакомое из них — папки. В главе 9 мы обходили папку-словарь рекурсией; функция os.walk делает то же самое с настоящими папками на диске. Обойдём на сервере курса папку, где лежат библиотеки Python: стандартная и установленные пакеты — те же matplotlib и numpy, которыми рисуются графики в ячейках.
os.walk на каждом шаге отдаёт три вещи: путь к папке, список вложенных папок и список файлов в ней, и сама спускается во все вложенные. Переменная os.__file__ — путь к файлу модуля os, а os.path.dirname отрезает от пути имя файла и оставляет папку. На сервере курса, когда писалась глава, выходило больше шестисот папок и шести тысяч файлов, сложенных в восемь этажей. Корень этого дерева — папка библиотек, листья — файлы.
Второе дерево — страница, которую вы читаете. Браузер разбирает её HTML в дерево элементов: в корне html, под ним head и body, под ними разделы, абзацы, ячейки с кодом, внутри абзацев — ссылки и формулы. Каждый тег, открытый внутри другого, — его ребёнок. В дереве этой страницы больше четырёх тысяч узлов и около тридцати этажей, и глубже всего вложены формулы: дробь или корень, нарисованные на странице, — это десятки элементов один в другом. Третье дерево — JSON из главы 8: словари и списки, вложенные друг в друга, где листья — числа и строки. Все три можно полистать ниже.
У этих деревьев нет правила поиска — в папке файлы лежат в каком угодно порядке, — но обходы те же. Размер папки считают обратным обходом: сначала размеры вложенных, потом сумма. Оглавление печатают прямым: сначала имя папки, потом содержимое. А когда браузер ищет на странице элемент по CSS-селектору, он обходит дерево страницы.
Задачи
Пять задач: от разминки до двух ловушек. Во всех узел — класс Node с полями key, left и right, как в главе; тесты строят деревья сами и вызывают ваши функции. Некоторые деревья в тестах большие, некоторые — палки.
Напишите insert(root, key): посадить key в дерево поиска с корнем root и вернуть корень (у пустого дерева root равен None). Если такой ключ уже есть, дерево не меняется. Заготовка почти верна, но тесты её не пропускают. Найдите ошибку.
Посадите в заготовку три ключа и нарисуйте дерево через show_tree из cs.viz. Куда пропал второй ключ?
Когда ветка пустая, insert(root.left, key) создаёт новый узел и возвращает его — но результат никуда не записан. Нужно root.left = insert(root.left, key).
От этой ошибки предупреждал раздел о посадке: новый узел создан, но ни один старый на него не ссылается, и он пропадает. В языках, где нет сборщика мусора, такой узел ещё и остаётся занимать память — утечка. Можно сажать и циклом, без рекурсии, как в ячейке о двойниках: тогда дереву не страшна и палка в тысячи этажей.
Напишите height(root) — высоту двоичного дерева: число узлов на самом длинном пути от корня вниз. У пустого дерева (None) высота 0, у одного узла — 1. Дерево не обязано быть деревом поиска.
Высота дерева — это единица (сам корень) плюс высота более высокой из двух веток.
Не забудьте базовый случай: пустая ветка даёт 0. Тогда у листа выйдет $1 + \max(0, 0) = 1$.
Это обратный обход: сначала высоты обеих веток, потом ответ для узла. Высоту палки в тысячи этажей рекурсия не переживёт — тогда считают по этажам обходом в ширину: очередь узлов текущего этажа, и на каждом шаге — следующий этаж, пока он не опустеет. Число шагов и есть высота.
Напишите inorder(root) — список ключей двоичного дерева в симметричном порядке: левая ветка, узел, правая ветка. Для дерева поиска это ключи по возрастанию. Подвох: в тестах есть деревья-палки в десятки тысяч этажей, а рекурсия в Python упирается в предел около тысячи. Обойдите дерево без рекурсии.
В главе 15 мы переписали рекурсию на свой стек: стопка недоделанных дел в обычном списке. Какие дела откладывает рекурсивный walk? «Записать узел и потом заняться его правой веткой».
Спускайтесь налево, складывая все пройденные узлы в стек. Когда налево идти некуда, снимите верхний узел со стека, запишите его ключ и перейдите в его правую ветку — и снова налево до упора.
Каждый узел один раз попадает в стек и один раз из него выходит, так что время — $O(n)$, а стек растёт не глубже высоты дерева. Только живёт он в обычном списке, и предел у него — память, а не тысяча кадров. Так, без рекурсии, обходят деревья в библиотеках, которым нельзя падать на чужих данных.
Напишите is_bst(root): верно ли, что двоичное дерево — дерево поиска, то есть у каждого узла все ключи левой ветки меньше его ключа, а все ключи правой — больше. Одинаковых ключей в дереве поиска не бывает. Пустое дерево — дерево поиска. Заготовка сравнивает каждый узел только с его детьми и ошибается. Найдите дерево, на котором она врёт, и исправьте.
Возьмите корень 10, слева от него 5, а у пятёрки справа — 12. Каждый узел со своими детьми в порядке. А дерево — нет: 12 лежит в левой ветке десятки.
Передавайте вниз границы: какие ключи вообще допустимы в этой ветке. У корня границ нет. Уходя налево от узла с ключом $k$, верхняя граница становится $k$; уходя направо — нижняя.
Другой путь — симметричный обход: дерево поиска тогда и только тогда, когда он даёт строго возрастающую последовательность.
Каждый узел проверяется один раз, время $O(n)$. Границы передаются вниз и сужаются: ключ где-то в глубине левой ветки обязан быть меньше не только своего родителя, но и всех предков, от которых путь к нему уходил налево. Заготовка проверяла правило у соседей, где это легко, хотя сформулировано оно для целых веток. Ошибка частая, и встречается она далеко не только в деревьях.
Напишите keys_between(root, lo, hi) — список ключей дерева поиска от lo до hi включительно, по возрастанию. Если lo > hi, ответ пустой. Тесты сажают двести тысяч ключей и задают тысячи узких вопросов, так что обходить всё дерево на каждый вопрос не успеете: заходите только в ветки, где ответ может быть.
Если ключ узла меньше lo, в его левой ветке всё ещё меньше — туда идти незачем. Если больше hi, незачем идти направо.
Это функция between из раздела «Ответ хеш-таблице». Порядок вызовов — левая ветка, сам узел, правая — тот же, что у симметричного обхода, поэтому ответ сразу выходит отсортированным.
Два условия превращают обход всего дерева в спуск к началу диапазона и проход по ответам: $O(h + k)$, где $h$ — высота, а $k$ — число найденных ключей. На сбалансированном дереве из двухсот тысяч ключей узкий вопрос стоит десятки шагов вместо двухсот тысяч. При lo > hi функция сама вернёт пустой список: ни один ключ не пройдёт проверку.
Куда дальше
Дерево поиска держит всё по порядку. Но бывает, что весь порядок не нужен — нужен только первый. В приёмный покой больницы привозят больных; лечить надо самого тяжёлого, а не того, кто приехал первым. Очередь из главы 15 отдаёт первого пришедшего. АВЛ-дерево отдало бы самого тяжёлого — это самый правый узел — за $O(\log n)$, но ради одного вопроса оно хранит полный порядок, держит по две ссылки на узел и крутит повороты. Хорошо бы обойтись обычным массивом, без ссылок и поворотов, и всё равно быстро выдавать самого тяжёлого, пока больные всё прибывают. Такая структура есть. Она тоже дерево, только спрятанное внутри списка, и о ней следующая глава.