Деревья являются одной из старейших и наиболее часто используемых структур данных в программировании. В самых общих чертах деревья - это просто неориентированные графы, называемые свободными деревьями. Однако наибольшее распространение получили бинарные деревья поиска. Бинарные деревья поиска упрочились в употреблении так сильно, что если кто-то говорит о деревьях, то подразумевается обычно бинарное дерево поиска, поэтому далее, когда я пишу "дерево", я подразумеваю "бинарное дерево поиска". Если я пишу "бинарное дерево поиска", я подразумеваю "бинарное дерево поиска", что может приводить к путанице. Эта статья описывает базовые концепции деревьев, иногда очень детально.
Я постараюсь приложить все усилия, чтобы уделить внимание важным и практическим аспектам (сопровождая пояснения реальным работающим кодом), не вдаваясь в теорию. У меня нет желания писать ещё одну сухую книгу о деревьях, и поэтому в центре моего внимания находится то, что вы сможете использовать в реальном мире, не имея докторской степени. Если вы ищете леммы и доказательства, то эта статья не для вас. Я недостаточно компетентен и незаинтересован заполнять статью страницу за страницей математической каббалистикой. Если же вы хотите узнать, что за звери эти бинарные деревья поиска или просто не до конца понимаете что-то, вы пришли по верному адресу. Если вы уже использовали деревья в реальном коде или просто в примерах, эта статья позволит вам углубить знания и, возможно, познакомит с вариациями в работе с деревьями.
Я программист, а не учёный. Я зарабатываю на жизнь написанием кода, а не теориями. Поэтому у меня есть строгое мнение о бесполезности теории. Уверен, знание теории придаёт вам учёный вид, но иногда теория недоступна среднестатистическому Ивану, не играя к тому же особой роли на практике. Я хочу, чтобы моя статья была полезна как можно большему числу людей, поэтому я пишу для таких людей, как я сам - для людей, которые не забивают голову бесполезной теорией, если только это действительно необходимо для принятия каких-то важных решений по коду. Пишу я тоже, как программист, с каламбурами, непривычными шутками и различными социальными отклонениями. Это повод добавить немного текста в статью и разбавить текст юмором :-)
Прежде, чем мы приступим, несколько замечаний по коду. Весь код написан на C, потому что используя C я могу описать суть пояснений в тексте без вовлечения фреймворков. C++ или Java тоже были бы неплохим выбором, потому что они хорошо разрекламированы и в наши дни они лучше, чем Jolt!-кола, но при использовании этих языков пришлось бы писать классы в хорошем стиле, который принят для этих языков, что могло бы добавить много ненужной возни. Так как я пишу о деревьях, а не о том, как написать хороший класс для работы с деревом, я предпочитаю C, чтобы иметь возможность избавиться от ненужных деталей и фреймворка. Кроме того, C - база для общераспространённых языков. По своему синтаксису Java и C++ восходят к C, поэтому компетентному программисту не составит труда "перевести" код.
Я не "отупляю" свой код, потому что уверен - бесполезные примеры, написанные так, чтобы их смог понять любой, но в ущерб функциональности глупы и не помогают в конечном счёте никому. Я ожидаю от вас хорошего знания C, но тем не менее по ходу дела я буду объяснять моменты, которые недостаточно ясны. Код написан, как если бы он предназначался для готовой к использованию полноценной библиотеки с мыслью о том, чтобы его можно было использовать на самом деле! Я видел массу руководств, в которых код был написан с явными синтактическими и логическими ошибками, упрощающими допущениями, непрактичными конструкциями и проч.. Всё это делало такой код бесполезным где-либо, помимо самого руководства, в котором он приведён. С этой статьёй иначе - вам не только разрешается использовать приведённый здесь код, но даже более того - я настоятельно советую его использовать!
Вся эта статья является общественным достоянием (public domain). Это значит, что вы можете цитировать текст, не беспокоясь о соблюдении копирайтов, копировать всё содержимое статьи и размещать его где-то ещё и даже копировать код в свою библиотеку, которую вы намереваетесь продавать - всё это без необходимости какого-либо разрешения со стороны автора! Естественно, первоисточник может обновляться и быть более актуальным, но я не накладываю никаких ограничений на использование материалов. Вы можете также взять мой код и выдать его за свой, но это подпортит вашу карму. Я верю, что вы достаточно честны, чтобы упомянуть меня там, где такие упоминания необходимы. Написание руководств - тяжёлая работа, также, как и написание кода
Итак, мы теперь друзья, так? Вы - программисты или хотите стать программистом, так что, наверняка вы сталкивались с необходимостью хранения кучи данных. Это может быть гистограмма уникальных слов в файле, сортировка огромной кучи IP-адресов, с которых были установлены соединения на сокете или просто база данных адресов электронной почты. Вероятно, вы использовали связный список или (Ха!) массив. Ни то, ни другое не подходит для нужд, описанных выше. То, что нам нужно - это структура данных, которая хранит данные в отсортированном виде без необходимости совершать дополнительные телодвижения с простыми операциями вставки и удаления, а также эффективным поиском. Ни связный список, ни массивы не обладают такими свойствами, а потому они являются плохими решениями.
Мы знаем, что бинарный поиск эффективен, потому что он делит последовательности, в которых производится поиск, на две половины на каждой итерации. Единственный недостаток - данные должны быть отсортированы. Давайте попытаемся сделать нечто безумное и составить список из элементов так, как эти элементы перебирались бы при бинарном поиске каждого из них. Т.е., в начале этой структуры данных был бы элемент из середины. Если мы поворачиваем направо от этого элемента, мы видим средний элемент из левого подмножества. В общем, мы берём линейный список и превращаем его в явно выраженную структуру бинарного поиска:
Последовательность [0][1][2][3][4][5][6][7][8][9]
приобретает следующий вид
Такова идея, скрытая за деревом. Такая структура называется деревом из-за ветвей, как у настоящего дерева. Возможно, эту структуру стоило бы назвать корнем бинарного поиска, т.к. это было бы проще увязать с иллюстрацией, походящей скорее на корневую систему, но к сожалению в информатике уже укоренилось название "дерево", так что переименование наверно было бы плохой мыслью.
Если вы начнёте поиск элемента с самого верхнего узла, называемого корнем (путаница!), вы можете продолжать поиск заданного элемента, сравнивая его с вершиной на предмет того, меньше ли искомое значение, чем то, что содержится в вершине или же больше. Скажем, нам нужно найти элемент со значением 3. 3 меньше 5, поэтому мы двигаемся влево и теперь у нас вершина со значением 2. 3 больше 2, поэтому мы смещаемся вправо и теперь у нас вершиной становится узел 4, мы смещаемся влево от вершины и вот наше 3. 3 равно 3, вот мы и нашли наш элемент. Следуя этому образцу, вы можете найти любой элемент в дереве.
Хорошо, а что с неудачным поиском? Что, если искомого элемента нет в дереве? Очень просто! Проделайте поиск, как описано выше и если вы выйдете за нижнюю часть дерева, то поиск можно считать безуспешным. Ну, может это не так и просто, ведь мы не знаем, когда мы выйдем за нижнюю часть дерева. На самом деле, в дереве есть специальные узлы, называемые листьями (листовые узлы). Они не содержат данных и если мы достигаем такого листа, значит наш поиск зашёл в тупик. Для обозначения листьев я буду использовать символ тильды - ~, а дерево будет выглядеть так:
Из диаграммы легко увидеть, что при достижении листа поиск заканчивается. На будущее давайте определимся с терминологией. Вершина дерева называется корнем. Однако, учитывая то, что деревья могут определяться рекурсивно, каждый узел дерева может быть назван корнем (корень поддерева). Если узел является корнем поддерева, у него есть родительский узел, который ссылается на него. Так узел 2 является родительским узлом (родителем) узла 1, а 5 - родительский узел узла 2. Если смотреть с другой стороны, 2 является дочерним узлом узла 5, а 1 - дочерний узел (потомок) узла 2. В отношении деревьев принята аналогия с семейным древом, поэтому не удивляйтесь, если при обсуждении деревьев натолкнётесь на упоминания о дедах, прадедах и прочем таком.
Узлы, имеющие 2 потомка, называются внутренними, а узлы с 1 или меньшим числом дочерних узлов называются внешними. Лист - это лист. Высота дерева (или поддерева - ведь деревья рекурсивны) - это число узлов от корня до листа, исключая сам корень. На рисунке выше высота восьмёрки - 2, потому что самый длинный путь к листу имеет 2 узла - 7 и 6. Иногда вам также может встречаться случай, когда корень дерева также включается в высоту и тогда в нашем случае высота была бы 3. Оба способа верны до тех пор, пока их применение правильно.
Хорошо, поиск в таком дереве эффективен. А что с простотой вставки и удаления узлов? На первый взгляд, это непросто. Вставка в дерево нового узла проста и эффективна, если посмотреть на это с точки зрения безуспешного поиска. Если вы ищете новый элемент, который, как вы знаете, отсутствует в дереве, вы можете заменить лист на новый узел с тем значением, которое вы безуспешно искали. С помощью сравнений "меньше" или "больше" вы можете обрабатывать и дубликаты данных. Оба способа работают и ваши дубликаты будут выстраиваться в линию вниз по пути.
Удаление сложнее (но не настолько, как многие думают), однако мы оставим это на потом и рассмотрим в деталях чуть позже. Что у нас с сортировкой данных? Так как каждый левый дочерний узел меньше или равен по значению своему родителю, данные хранятся в отсортированном виде. Иногда использовать такое положение вещей эффективно не так легко, потому что следующая по порядку запись данных может не быть в прилегающем узле. Допустим, узлы 2 и 3 разделены узлом 4, а 4 и 5 - узлом 2. В дальнейшем мы рассмотрим способы извлечения пользы из такого расположения узлов, а пока всё, что вам нужно запомнить - данные в дереве уже действительно отсортированы!
Итак, деревья удовлятворяют всем нашим требованиям. Они предоставляют эффективную операцию поиска, данные в деревьях по умолчанию отсортированы, вставка новых записей проста и, если сейчас вы поверите мне на слово, удаление ненамного сложнее. Мы уже знаем, чего хотим. Давайте воплотим это в коде. Первое, что нам понадобится, это структура узла. Также было бы удобно работать с деревом, как с цельной сущностью, поэтому мы создадим структуру, которая просто будет содержать указатель на корень:
1 struct node {
2 int data;
3 struct node *link[2];
4 };
5
6 struct tree {
7 struct node *root;
8 };Итак, у нас структура, ссылающаяся на себя. Если вы знакомы с тем, как работают связные списки, для вас понимание этой структуры не будет проблемой. Структура может содержать указатель на саму себя, так что, чтобы связать два экземпляра структуры, полю, указывающему на другой экземпляр, присваивается значение адреса этого другого экземпляра. Единственным моментом, вводящим в заблуждение, может оказаться массив ссылок. Я мог бы использовать два поля-указателя, но как вы вскоре увидите сами, операции на бинарном дереве поиска симметричны. Используя массив ссылок и булев индекс при доступе к его элементам мы можем избежать ненужных повторений кода лишь слегка уложнив его. Как только вы пообвыкнетесь с этой идиомой, она, возможно, покажется вам удобнее, чем обычная идиома левых и правых указателей. Для индикации листьев мы просто используем NULL, т.к. это общепринятая практика и она легка в использовании.
Наконец, с этими познаниями мы можем приступить к сути этой статьи. Начнём с поиска, ведь вы уже знаете, как он работает.
Мы уже знаем, что поиск начинается с корня и дальше двигается либо влево, либо вправо в зависимости от того, каков результат сравнения значения из корня с искомым (сейчас мы пока не будем трогать деревья, которые допускают дубликаты). Далее мы переходим к правому или левому дочернему узлу корня и делаем то же, что проделали с корнем. В принципе, мы работаем с каждым поддеревом так, как если бы оно было уникальным деревом и на каждой итерации это повторяется. Всё это можно проделать рекурсивно. Код прост и почти устрашающ:
1 int find_r (struct node *root, int data)
2 {
3 if (root == NULL)
4 return 0;
5 else if (root->data == data)
6 return 1;
7 else {
8 int dir = root->data < data;
9 return find_r (root->link [dir], data);
10 }
11 }
12
13 int find (struct tree *tree, int data)
14 {
15 return find_r (tree->root, data);
16 }Базовыми случаями для рекурсии являются удачный и безуспешный поиск. Если корень равен указателю на NULL, мы достигли листа и можем возвратить код ошибки. Если данные из корня содержат значение, совпадающее с искомым, мы можем возвратить код успешного завершения. Иначе мы сравниваем искомое значение со значением из корня и в зависимости от результата переходим к его левому, если искомое значение меньше, чем значение корня, или правому дочернему узлу, если искомое больше. Код возврата при рекурсии всё время "отодвигается", так что find() возвращает то, что получает. 0 означает, что данные не найдены, а 1 - что поиск завершён успехом. Функция find() определена для удобства. Теперь пользователь может написать find (tree, data) и работать с деревом, как с чёрным ящиком вместо явного вызова find_r (tree->root, data).
Хорошо, я не могу представить себе, что этот код застопорит вас, а если это всё же случилось, возможно, вы ещё не готовы к знакомству с бинарными деревьями поиска. Однако фокус с флагом dir иногда вводит в заблуждение, поэтому я кратко поясню, как это работает. Мы знаем, что link [0] - это левое поддерево, а link [1] - правое поддерево, для перехода влево нам нужно убедиться, что сравнение даёт 0 в результате, а для перехода вправо - 1. Проблема. Ведь наиболее явный способ сравнения data < root->data даёт нам 1 и, следовательно, неправильное направление для дальнейшего движения, потому что нам нужно будет перейти влево. Поэтому, чтобы наша идиома с массивом работала, мы переворачиваем условие так root->data < data. При этом, если data меньше root->data, результат сравнения - 0 и мы получаем нужное направление.
Хотя при работе с деревьями рекурсия упрощает некоторые вещи, многие предпочитают нерекурсивные решения по множеству веских причин. Поиск в дереве без рекурсии ещё проще, чем рекурсивный. Он предотвращает вероятность переполнения стека, выполняется быстрее и требует меньше памяти:
1 int find (struct tree *tree, int data)
2 {
3 struct node *it = tree->root;
4
5 while (it != NULL) {
6 if (it->data == data)
7 return 1;
8 else {
9 int dir = it->data < data;
10 it = it->link [dir];
11 }
12 }
13
14 return 0;
15 }Пара замечаний по поводу дубликатов. Описанные алгоритмы подолжают поиск до первого совпадения и не позволят вам находить и перечислять дубликаты. Работа с дубликатами несколько сложнее. Если вам необходимо вести подсчёт дубликатов, возможно имеет смысл возвращать указатель на данные, сохраняя также указатель на узел, содержащий совпадение с тем, чтобы после вы смогли возобновить поиск там, где остановились в прошлый раз. Таким образом вы сможете найти последующие совпадения после первого. Многие деревья не допускают дубликатов. В этой статье мы в основном также исходим из этого. Это легче и для меня, так как мне не нужно писать дополнительный код для обработки дубликатов :-)
Многие вещи, которые вы хотели бы сделать с помощью деревьев, вовлекают операцию поиска. Поэтому деревья столь эффективны. В идеале, поиск будет делить диапазон поиска надвое на каждой последующей итерации. Было бы неплохо использовать это обстоятельство и при реализации других операций. Например, вставка нового узла - это вариация алгоритма поиска с безуспешным результатом. Вы ищете значение, которого нет в дереве, достигаете листа и заменяете первый лист на новый узел с нужным значением:
Код, выполняющий эти действия, представляет собой простую вариацию алгоритма поиска, однако рекурсивный код извлекает некоторую выгоду из рекурсии для упрощения внесения обновлений. Вот рекурсивный код (make_node() просто создаёт новый узел, присваивает ему данные и инициализирует ссылки NULL-значениями):
1 struct node *insert_r (struct node *root, int data)
2 {
3 if (root == NULL)
4 root = make_node (data);
5 else if (root->data == data)
6 return root;
7 else {
8 int dir = root->data < data;
9 root->link [dir] = insert_r (root->link [dir], data);
10 }
11
12 return root;
13 }
14
15 int insert (struct tree *tree, int data)
16 {
17 tree->root = insert_r (tree->root, data);
18 return 1;
19 }Единственное отличие между insert_r() и find_r() состоит в возвращаемых ими значениях в двух основных случаях. Однако на первый взгляд может быть не совсем ясно, как работает рекурсивное обновление. Когда наша рекурсия сворачивается и мы поднимаемся вверх по дереву, мы присваиваем указателю на следующий узел то значение, которое возвращает insert_r(). Так мы обеспечиваем, что изменения в нижней части дерева дойдут и до верхних уровней. Кстати, распространённая ошибка - не забывайте сбрасывать родительский узел изменённого узла, чтобы ваши изменения вступили в силу.
Мы добавляем новые узлы, замещая листья внизу дерева, так что наше дерево растёт вниз. Это опять вызывает путаницу и снова на ум приходит мысль о "деревьях", как о "корнях". Давайте добавим в новое дерево несколько узлов, чтобы посмотреть, как это всё работает:
Как и функция find(), insert() может быть реализована без рекурсии - так же, как рекурсивные и нерекурсивные функции поиска. Нерекурсивная вставка имеет некоторые преимущества по сравнению с рекурсивной. При работе на больших деревьях вам не нужно беспокоиться от достижении некого предела рекурсии. Обычный цикл быстрее, чем вызов функции и памяти для хранения локальных переменных также требуется меньше. Иногда рекурсивные алгоритмы являются лучшим выбором из-за их простоты, но на мой взгляд многие нерекурсивные алгоритмы на деревьях не намного сложнее рекурсивных. Вообще, затрата усилий на создание нерекурсивного алгортма оправдывает себя.
Единственная разница между нерекурсивным поиском и нерекурсивной вставкой в том, что алгоритм вставки должен быть осторожным, чтобы не попасть на лист. Ввиду того, что листовой узел - это NULL-указатель, мы не сможем определить, с какого узла мы пришли и не сможем добавить ссылку на новый узел. Это не даёт осуществить саму вставку, потому что мы не сможем внести наши изменения в дерево. Поэтому рабочий цикл на каждой итерации сначала проверяет следующую ссылку прежде чем двигаться дальше. И если следующий узел - листовой, цикл разрывается, а новый узел записывается в переменную, содержавшую ссылку на лист. Так как у нас нет ссылки, которая указывала бы на корень дерева, мы рассматриваем это, как особый случай. Есть разные способы обработки случая пустого дерева, но я думаю, самый ясный способ такой:
1 int insert (struct tree *tree, int data)
2 {
3 if (tree->root == NULL)
4 tree->root = make_node (data);
5 else {
6 struct node *it = tree->root;
7 int dir;
8
9 for ( ; ; ) {
10 dir = it->data < data;
11
12 if (it->data == data)
13 return 0;
14 else if (it->link [dir] == NULL)
15 break;
16
17 it = it->link [dir];
18 }
19
20 it->link [dir] = make_node (data);
21 }
22
23 return 1;
24 }Так как условие, при соблюдении которого цикл разрывается, находится между кодом, выбирающим направление и кодом передвижения в этом направлении, мы используем бесконечный цикл. Конечно, можно построить и "нормальный" цикл, но я не думаю, что такие методы здесь уместны, а кроме того, коль скоро я автор статьи, моё мнение и решает :-) Обратите внимание, что в любой из этих реализаций вы можете разрешить дубликаты данных, если уберёте проверку на равенство. Всё будет работать и дальше, а дубликаты будут складываться один под другим.
Та простота, с которой мы вставляли новые узлы, могла вызвать у вас необоснованное чувство безопасности. Хотя, если всё, что вам нужно, так это добавлять узлы и искать, всё в порядке. Но многие из нас на определённом этапе приходят к необходимости удалять из дерева существующие узлы. Это не так просто, как вставка узлов, т.к. у нас нет выбора, откуда удалять узел. Если это внешний узел, то всё почти так же просто, как и со вставкой. Но если удаляемый узел - внутренний, всё немного сложнее.
Всё, что нужно сделать для удаления внешнего узла - заменить его на его нелистового потомка или на лист, если у данного узла нет иных потомков, кроме листовых узлов. Есть три простых случая удаления внешнего узла. Если у нашей жертвы есть левый дочерний узел, мы заменяем удаляемый узел, который является внешним, левым потомком, потому как его правый потомок с уверенностью окажется листом. Если у удаляемого узла есть правый дочерний узел, то случай симметричен узлу с левым потомком. Если у узла нет дочерних узлов - выберите любой, т.к. они оба будут листьями. И не забудьте обновить ссылку родительского узла, чтобы она указывала на новый дочерний узел. Это удалит узел из дерева:
Здесь главное проследить, чтобы ссылка родительского узла была обновлена и указывала на узел с или лист. Если это не будет сделано, то узел х не будет успешно удалён из дерева, а последующее освобождение памяти приведёт к неприятностям. К счастью, пока у нас есть доступ к родительскому узлу, все три случая суммируются в одном блоке кода. Вероятно, это самый ужасный случай, о каком я могу подумать применительно к деревьям, потому что здесь необходимо проверять, какой из дочерних узлов х не пустой (NULL) и каким узлом по отношению к р является х таким вот образом:
1 p->link [p->link [1] == x] = x->link [x->link [0] == NULL];
Здорово, правда? Это похоже на удаление записи из связного списка. Ма замещаем ссылку на следующий узел узла р аналогичной ссылкой узла х, таким образом удаляя х из цепи и после этого можем со спокойной душой освободить память, занимаемую х. Оставшаяся часть - сравнение x->link [0] и NULL даёт нам 1, если левая ссылка пустая (NULL) - второй случай и мы будем использовать правую ссылку для замены узла х. Если правая ссылка также пустая, у х не было потомков (третий случай). Если проверка даёт 0, левая ссылка не пуста (первый случай). Сравнение указателя на х и правой ссылки узла р выполняет ту же работу, но иным способом. Если х - узел, на который указывает правая ссылка узла р, мы получаем 1. В противном случае результатом сравнения будет 0 и т.к. х не является листом, мы можем быть уверены, что х - левый дочерний узел р. Все действия выполняются в одной строке (особый случай - удаление корня дерева, - будет рассмотрен немного позже). Это простой случай удаления. Когда мы удаляем узел с двумя потомками, дело обстоит чуть сложнее.
Давайте удалим из этого дерева узел 5, просто представив, что это не корень :-) Мы не можем просто так заменить его одним из дочерних узлов, потому как это вызовет определённые неудобства. Самое заметное - что делать с одним из дочерних узлов, который окажется сам по себе? Хорошо, ну а как на счёт присоединения левого поддерева узла 5 в качестве левой ссылки узла 7 и заменой 5 на 8?
Проделав такое, мы соблюдаем правило, что левые узлы содержат меньшие значения, а правые - большие, но такая хирургия несколько нетривиальна. Мы можем сделать лучше с меньшим усилием, не подвергая структуру дерева таким сильным изменениям. Как на счёт простой замены 5 на 4 или 7, вместо беготни по поддеревьям? Данные узлы являются порядковым предшественником и преемником, соответственно. Вся работа сводится к тому, чтобы найти один из этих узлов, потому что всё, что в большинстве деревьев нужно сделать после - скопировать данные одного узла в другой, затем удалить порядкового предшественника или преемника, которым мы заменили удаляемый узел. В этой статье мы будем в этих целях использовать преемника, но на самом деле, это не имеет особой разницы (Здесь возможна терминологическая неточность в переводе. В этом месте оригинал гласит следующее: These are the inorder predecessor and successor, respectively. All of the work is in finding one of those nodes, because then all you need to do in most trees is copy the data of one to the other, then remove the predecessor or successor that you replaced it with. Речь идёт о числах. Т.е., число, по порядку предшествующее 5 - т.е., 4 и следующее за ним из множества тех, что есть в дереве - 7. Я сходу не нашёл удачного эквивалента, потому что спешил, но в целях ясности решил оставить это замечание - перев.)
Прелесть этого приёма (удаление копированием) в том, что мы можем взять сложный случай, когда у удаляемого узла два потомка и свести его к случаю удаления узла с одним потомком. Как это работает? А если у старшего узла два потомка?
Младший узел никогда не имеет правого потомка, а старший - левого. Поэтому мы можем быть уверены в том, у старшего узла по меньшей один потомок, а его левая ссылка указывает на лист. Следуя этому, мы можем легко найти старший узел для заданного узла, если у нас есть доступ к его правому поддереву. Простой переход на правую ветку и нисхождение по левой стороне поддерева приведёт нас к старшему узлу. Схожим образом мы можем найти и младший узел, перейдя на левую ветку узла и пройдя по левому поддереву с правой стороны.
Теперь мы можем найти старший узел, следуя вниз по поддереву. Но что, если мы хотим найти старший узел для 4? Это сложнее, но мы не столкнёмся с такой ситуацией в базовом алгоритме удаления, так что можем пока оставить это в стороне. У нас достаточно условий для удаления узла из дерева. Сначала мы находим узел, который нужно удалить - так же, как и в алгоритме вставки, но в случае с удалением мы сохраняем указатель на родительский узел при спуске вниз. Когда мы достигаем нужного узла (если мы достигли листа, то просто возвращаем ошибку), мы смотрим, сколько у него потомков и применяем к нему тот или иной способ удаления в зависимости от того, простой у нас или сложный случай. Вот наш код:
1 int remove (struct tree *tree, int data)
2 {
3 if (tree->root != NULL) {
4 struct node *p = NULL, *succ;
5 struct node *it = tree->root;
6 int dir;
7
8 for ( ; ; ) {
9 if (it == NULL)
10 return 0;
11 else if (it->data == data)
12 break;
13
14 dir = it->data < data;
15 p = it;
16 it = it->link [dir];
17 }
18
19 if (it->link [0] != NULL && it->link [1] != NULL) {
20 p = it;
21 succ = it->link [1];
22
23 while (succ->link [0] != NULL) {
24 p = succ;
25 succ = succ->link [0];
26 }
27
28 it->data = succ->data;
29 p->link [p->link [1] == succ] = succ->link [1];
30
31 free (succ);
32 }
33 else {
34 dir = it->link [0] == NULL;
35
36 if (p == NULL)
37 tree->root = it->link [dir];
38 else
39 p->link [p->link [1] == it] = it->link [dir];
40
41 free (it);
42 }
43 }
44
45 return 1;
46 }Поиск узла почти идентичен тому, что используется в нерекурсивном алгоритме вставки, за тем лишь исключением, что здесь мы не разбиваем код определения направления и, собственно, переходов. Мы также присваиваем р значение it, прежде чем it будет присвоено содержимое it->dir (Вообще-то, должно быть it->link [dir]. Тут у автора статьи явная опечатка - перев.). Этим шагом мы сохраняем указатель на родительский узел и если р равен NULL, поиск завершён, а мы должны обработать особый случай - удаление корня дерева.
Давайте посмотрим на обработку двух случаев после окончания поиска. В первом случае, если у узла два потомка, нам нужно найти старший узел для него. Как вы уже знаете, чтобы сделать это, мы просто сдвигаемся на правую ветку и идём по левой стороне, пока не находим лист. Во время этой операции мы сохраняем ссылку на родительский узел текущего узла поддерева, так что в конце нисхождения succ будет содержать старший узел, а р - указатель на его родителя. Мы копируем данные из старшего узла в узел, который собираемся удалить, но фактически удаляется сам старший узел. Обратите внимание, что в этом случае мы работаем всегда с succ->link [1], потому что мы знаем: левая ссылка указывает на лист. Обратная проверка p->link [1] == succ в принципе даст тот же результат - 0, если на succ - указывает левая ссылка узла р и 1 - если правая. Теперь освобождаем память удалённого узла и дело сделано.
Во втором случае у удаляемого узла только один потомок, узел - внешний. Это простой случай, ведь нам не надо искать старший узел. Мы просто вырезаем узел, берём ту сторону, которая не указывает на лист и присоединяем поддерево к узлу р, как замену узла, на который указывает it. Если р равно NULL, мы пытаемся удалить корень дерева. Здесь может возникнуть проблема, потому что изменения, которые мы вносим, должны быть отражены в tree->root или они не будут сохранены, поэтому мы рассматриваем такую ситуацию, как особый случай. Такого особого случая не возникает, если узел, который мы удаляем, имеет двух потомков, потому что даже если такой узел окажется корнем дерева, мы просто перезапишем его данные, не удаляя сам узел.
Такой метод относительно короткий и простой, хоть и несколько наивный. Мы решаем проблему в лоб, хотя могли бы сработать хитрее. Отметьте, как оба случая на самом деле завершают удаление внешнего узла, хотя это всё ещё разные случаи, потому что в одном из них нам необходимо найти старший узел. Давайте попробуем сделать иначе. Вместо останова при нахождении внешнего узла мы просто сохраним указатель на него и продолжим движение вниз к внешнему узлу. Когда мы достигаем "дна", мы копируем данные текущего узла в ранее сохранённый узел и удаляем текущий:
1 int remove (struct tree *tree, int data)
2 {
3 if (tree->root != NULL) {
4 struct node head = { 0 };
5 struct node *it = &head;
6 struct node *p, *f = NULL;
7 int dir = 1;
8
9 it->link [1] = tree->root;
10
11 while (it->link [dir] != NULL) {
12 p = it;
13 it = it->link [dir];
14 dir = it->data <= data;
15
16 if (it->data == data)
17 f = it;
18 }
19
20 if (f != NULL) {
21 f->data = it->data;
22 p->link [p->link [1] == it] = it->link [it->link [0] == NULL];
23 free (it);
24 }
25
26 tree->root = head.link [1];
27 }
28
29 return 1;
30 }Эта функция вводит два приёма с целью избежания особых случаев. Первое - корень-пустышка, так что у корня дерева всегда есть родительский узел. Второе - сохранение ссылки на найденный и подлежащий удалению узел с тем, чтобы мы смогли скопировать данные, когда доберёмся до внешнего узла. Таким образом мы избавились от особого случая с удалением корня и поиском старшего узла. Теперь код стал короче и красивее. Заметьте, мы проверяем является ли значение it->data меньше или оно равно data, потому что мы хотим продолжит нисхождение в том числе после нахождения совпадения и нам нужно перейти на правую сторону, чтобы найти старший узел для этой записи.
Мы можем удалить узел и рекурсивно, но алгоритм такого удаления не очень гладкий. Приведённая ниже функция использует тот же подход, что и умная функция выше. Найдя узел, который мы хотим удалить, мы ищем для него старший узел и копируем данные. Мы заменяем данные узла, который искали данными из старшего узла (проверяя на условие меньше или равно,- после копирования данных старшего узла будет совпадение). Рекурсия продолжает раскручиваться, пока мы не достигнем старшего узла и на этом этапе мы совершаем простую операцию удаления. А затем, когда рекурсия пошла вспять, мы фиксируем все наши изменения:
1 struct node *remove_r (struct node *root, int data)
2 {
3 if (root != NULL) {
4 int dir;
5
6 if (root->data == data) {
7 if (root->link [0] != NULL && root->link [1] != NULL) {
8 struct node *succ = root->link [1];
9
10 while (succ->link [0] != NULL)
11 succ = succ->link [0];
12
13 data = succ->data;
14 root->data = data;
15 }
16 else {
17 struct node *save = root;
18
19 root = root->link [root->link [0] == NULL];
20 free (save);
21
22 return root;
23 }
24 }
25
26 dir = root->data <= data;
27 root->link [dir] = remove_r (root->link [dir], data);
28 }
29
30 return root;
31 }
32
33 int remove (struct tree *tree, int data)
34 {
35 tree->root = remove_r (tree->root, data);
36 return 1;
37 }Уничтожение дерева [наверх]
В какой-то момент вас достанут деревья и вы захотите избавиться от них. Но вы не хотите утечек памяти, поэтому вам нужно удалить каждый узел и освободить занимаемую память. Конечно, вы можете достичь цели многократным вызовом remove(), но это не то. Лучшее решение - обойти каждый узел дерева и удалить их все одним залпом. Пока не касаясь деталей обхода скажем, что это может быть сделано обходом в обратном порядке, а рекурсивный алгоритм тривиален:
1 void destroy_r (struct node *root)
2 {
3 if (root != NULL) {
4 destroy_r (root->link [0]);
5 destroy_r (root->link [1]);
6 free (root);
7 }
8 }
9
10 void destroy (struct tree *tree)
11 {
12 destroy_r (tree->root);
13 }Можно проделать то же и без рекурсии. Но вообще говоря, нерекурсивный обход дерева в обратном направлении не очень лёгкий. Однако, вам не обязательно обходить дерево в обратном направлении, чтобы удалить его. Вы можете изменить структуру дерева так, как было бы удобно для ваших нужд :-) Если у нас есть дерево, в котором каждый левый потомок - лист, такое дерево очень легко обойти и удалить каждый узел: просто сохраняем правую ссылку, удаляем узел, переходим по сохранённой ссылке:
Используемый трюк позволяет любое дерево привести к подобной структуре. Достичь такой структуру нам позволит операция под названием вращение. Вращение может быть вправо или влево. Левый поворот превращает правого потомка узла в его родителя, а сам узел становится левым дочерним узлов. Правый поворот симметрично обратен левому:
Заметьте, как узел 2 двигается из левого поддерева в правое. Узлы, изменившиеся при вращении - 1 и 3. Левая ссылка узла 3 становится правой ссылкой узла 1, а правая ссылка узла 1 указывает на узел 3. Левый поворот на втором дереве превратит его в исходное - первое дерево. Т.е., вращение симметрично. Таким образом, если мы удаляем узел без левой ссылки, то мы совершаем вращение направо; когда левая ссылка указывает на узел, мы можем гарантировать, что будет обойдён каждый узел и каждый узел будет удалён. Код, который всё это делает, на удивление короткий:
1 void destroy (struct tree *tree)
2 {
3 struct node *it = tree->root;
4 struct node *save;
5
6 while (it != NULL) {
7 if (it->link [0] != NULL) {
8 /* Right rotation */
9 save = it->link [0];
10 it->link [0] = save->link [1];
11 save->link [1] = it;
12 }
13 else {
14 save = it->link [1];
15 free (it);
16 }
17
18 it = save;
19 }
20 }Ну что ж, если вы ещё не заметили, то мы закончили с основами и дальше нас ждёт средняя ступень. Я разделил статью таким образом, чтобы лёгкий материал находился в начале, потому что мне сказали, что моё предыдущее руководство по бинарным деревьям поиска было сложным. С этого момента подразумевается, что вы хорошо усвоили основу и знаете, что делаете. В следующем разделе мы рассмотрим обход дерева. Эта тема может показаться замороченной, но я постараюсь изложить её доступно. После обхода дерева мы обсудим родительские указатели и резьбу, которые уже можно считать продвинутой ступенью. И, наконец, некоторые замечания по поводу призводительности и намёки, что ещё может последовать за основами.
Теперь, когда у нас есть код для построения бинарных деревьев, мы можем вытворять с ними разные вещи. Полезные. Весёлые вещи. Естественно, вы можете использовать уже ранее описанную функцию поиска для того, чтобы определить, есть ли в дереве некое значение, но было бы неплохо проверять функцию вставки на предмет корректности её работы. Было бы также здорово иметь возможность выполнить некую операцию на всех узлах дерева, например, выводить на экран их содержимое. И это приводит нас к обходу дерева.
Наверно, вы подумали, что обход каждого узла в дереве прост и состоит из одного-двух случаев, которые необходимо обрабатывать. Верно? Нет! На самом деле, есть n! (факториал от n) разных путей обойти дерево, состоящее из n узлов, но большая часть таких маршрутов бесполезна. Из всего многообразия разных способов обхода бинарного дерева мы рассмотрим только две категории: обход в ширину - на примере обхода по уровням и обход в глубину - на примере обхода в прямом, симметричном и обратном порядке. Мы также рассмотрим более гибкий пошаговый обход, который вы можете найти в любой хорошей библиотеке для работы с деревьями.
Обход в глубину начинается с движения вправо или влево, насколько это возможно и продвигается до восхождения. Далее, переходя по ссылке вверх, обход снова движется направо или налево. Процесс провторяется, пока все узлы не будут посещены. Как и ожидалось, обход в глубину может быть написан рекурсивно, потому что маршрут движения построен на принципе стека. Конечно, возникает вопрос, а когда узел может считаться посещённым? Так как мы можем двигаться лишь в одном из двух направлений, нетрудно выяснить, что существует всего 6 путей обхода и посещения узлов при обходе в глубину. У нас есть три операции: "перейти влево", "перейти вправо", "посетить":
- посетить, перейти влево, перейти вправо
- посетить, перейти вправо, перейти влево
- перейти влево, посетить, перейти вправо
- перейти вправо, посетить, перейти влево
- перейти влево, перейти вправо, посетить
- перейти вправо, перейти влево, посетить
Из этих 6 вариаций 3 используются наиболее часто и имеют свои собственные стандартные названия: 1 - обход в пямом порядке, т.к. сперва посещается узел; 3 - симметричный обход, т.к. узлы обходятся в порядке сортировки их значений; и, наконец, 5 - обход в обратном порядке, потому что узел посещается после того, как совершены оба движения. Каждый из этих методов может быть реализован ввиде короткого и красивого рекурсивного алгоритма:
1 void preorder_r (struct node *root)
2 {
3 if (root != NULL) {
4 printf ("%d\n", root->data);
5 preorder_r (root->link [0]);
6 preorder_r (root->link [1]);
7 }
8 }
9
10 void preorder (struct tree *tree)
11 {
12 preorder_r (tree->root);
13 }
14
15 void inorder_r (struct node *root)
16 {
17 if (root != NULL) {
18 inorder_r (root->link [0]);
19 printf ("%d\n", root->data);
20 inorder_r (root->link [1]);
21 }
22 }
23
24 void inorder (struct tree *tree)
25 {
26 inorder_r (tree->root);
27 }
28
29 void postorder_r (struct node *root)
30 {
31 if (root != NULL) {
32 postorder_r (root->link [0]);
33 postorder_r (root->link [1]);
34 printf ("%d\n", root->data);
35 }
36 }
37
38 void postorder (struct tree *tree)
39 {
40 postorder_r (tree->root);
41 }Давайте рассмотрим пример. Проследим за результатами каждого из способов обхода на дереве, что представлено ниже. Алгоритм обхода в прямом порядке сначала посещает узел, а потом продвигается. Узлы будут обойдены в таком порядке: 5, 3, 2, 7, 6, 8. Алгоритм симметричного обхода сдвигается в самую левую позицию, прежде чем посетить узел и даст такую последовательность: 2, 3, 5, 6, 7, 8. Обход в обратном порядке приведёт нас к последовательности 2, 3, 6, 8, 7, 5.
Итак, мы можем вывести на экран все узлы дерева. Но давайте сделаем что-нибудь весёлое, просто, чтобы разбавить монотонное повествование. Вместо получения значений узлов давайте посмотрим на структуру дерева. Это можно легко сделать с помощью алгоритма симметричного обхода, который даст вам дерево, повёрнутое на 90 градусов против часовой стрелки:
1 void structure_r (struct node *root, int level)
2 {
3 int i;
4
5 if (root == NULL) {
6 for (i = 0; i < level; i++)
7 putchar ('\t');
8 puts ("~");
9 }
10 else {
11 structure_r (root->link [1], level + 1);
12
13 for (i = 0; i < level; i++)
14 putchar ('\t');
15 printf ("%d\n", root->data);
16
17 structure_r (root->link [0], level + 1);
18 }
19 }
20
21 void structure (struct tree *tree)
22 {
23 structure_r (tree->root, 0);
24 }Заметьте, что в принципе, код очень похож на функцию inorder() за исключением того, что помимо вывода значений узлов, мы ещё добавляем символы табуляции, число которых соответствует уровню узла в дереве. Мы также обозначаем на нашей импровизированной схеме листья, чтобы вы были уверенны в правильном построении дерева. Хотя рекурсивные алгоритмы и похожи на детские игрушки, они могут быть весьма мощным инструментом, если использовать их творчески. Подумайте, что ещё можно с ними сотворить :-)
Несмотря на эти чудесные решения, реализация нерекурсивных алгоритмов обхода может оказаться полезной. Такие алгоритмы сложнее в реализации из-за двойных рекурсивных вызовов. Если вы из тех, кто любит забегать вперёд, чтобы испытать или обхитрить учителя (позор!), вы могли отметить сходство обхода в прямом порядке и обхода по уровням, если очередь будет заменена на стек. Если нет, не волнуйтесь. Хотите верьте, хотите нет, но это всё, что необходимо сделать для создания алгоритма итеративного обхода в прямом порядке:
1 void preorder (struct tree *tree)
2 {
3 struct node *it = tree->root;
4 struct node *up [50];
5 int top = 0;
6
7 if (it == NULL)
8 return;
9
10 up [top++] = it;
11
12 while (top != 0) {
13 it = up [--top];
14
15 printf ("%d\n", it->data);
16
17 if (it->link [1] != NULL)
18 up [top++] = it->link [1];
19 if (it->link [0] != NULL)
20 up [top++] = it->link [0];
21 }
22 }Симметричный обход сложнее. Нам надо переходить влево, не теряя из виду правые ссылки или родительские узлы. Это подразумевает как минимум несколько циклов - один для сохранения обратных ссылок, один для посещения сохранённых ссылок и другой для работы с последовательными ветками. К счасть, хоть логика и кажется сложной, код на удивление прост:
1 void inorder (struct tree *tree)
2 {
3 struct node *it = tree->root;
4 struct node *up [50];
5 int top = 0;
6
7 while (it != NULL) {
8 while (it != NULL) {
9 if (it->link[1] != NULL)
10 up [top++] = it->link [1];
11
12 up [top++] = it;
13 it = it->link [0];
14 }
15
16 it = up [--top];
17
18 while (top != 0 && it->link [1] == NULL) {
19 printf ("%d\n", it->data);
20 it = up [--top];
21 }
22
23 printf ("%d\n", it->data);
24
25 if (top == 0)
26 break;
27
28 it = up [--top];
29 }
30 }Внешний цикл работает, пока указатель не равен NULL. Это может быть в случае, если дерево пустое или в стеке больше нет узлов. Вы увидите, что последняя строка внешнего цикла аккуратна с присвоением значения NULL, если стек пуст, так что алгоритм, собственно, завершается. Первый внутренний цикл имеет дело с сохранением правых ссылок родительских узлов при спуске вниз по левым ссылкам. Второй внутренний цикл посещает родительские узлы. Ну и наконец последний printf() показывает нам правые ссылки. Диаграмма выполнения построена на том же дереве, что и рекурсивный симметричный обход.
save 7, stack = { 7 }
save 5, stack = { 5, 7 }
save 3, stack = { 3, 5, 7 }
save 2, stack = { 2, 3, 5, 7 }
visit 2, stack = { 3, 5, 7 }
visit 3, stack = { 5, 7 }
visit 5, stack = { 7 }
pop 7, stack = {}
save 8, stack = { 8 }
save 7, stack = { 7, 8 }
save 6, stack = { 6, 7, 8 }
visit 6, stack = { 7, 8 }
visit 7, stack = { 8 }
pop 8, stack = {}
save 8, stack = { 8 }
visit 8, stack = {}Самый сложный случай - нерекурсивный обход в глубину в обратном порядке. Сложность состоит в необходимости придумать способ, как посетить узлы на низком уровне, сохраняя родителей и посещая их своевременно. Я неизбежно прихожу к использованию стека и вспомогательных счётчиков, причём 0 означает "сохранить левую ссылку", 1 - "сохранить правую ссылку", а 2 - "посетить вершину стека". Решение удобно, потому что оно хорошо вписывается в мою схему использовать булевы значения при вычислении условий для определения направления - правое или левое:
1 void postorder (struct tree *tree)
2 {
3 struct {
4 struct node *p;
5 int n;
6 } up [50], it;
7 int top = 0, dir;
8
9 up [top].p = tree->root;
10 up [top++].n = 0;
11
12 while (top != 0) {
13 it = up [--top];
14
15 if (it.n != 2) {
16 dir = it.n++;
17 up [top++] = it;
18
19 if (it.p->link [dir] != NULL) {
20 up [top].p = it.p->link [dir];
21 up [top++].n = 0;
22 }
23 }
24 else
25 printf ("%d\n", it.p->data);
26 }
27 }Код короткий, но крайне непрозрачный. Диаграмма ниже может очень сильно помочь в попытке понять, что на самом деле делает алгоритм. Клянусь, всё не так сложно, как выглядит!
push 5:0, stack = { 5:0 }
increment, stack = { 5:1 }
push 3:0, stack = { 3:0, 5:1 }
increment, stack = { 3:1, 5:1 }
push 2:0, stack = { 2:0, 3:1, 5:1 }
increment, stack = { 2:1, 3:1, 5:1 }
increment, stack = { 2:2, 3:1, 5:1 }
visit 2:2, stack = { 3:1, 5:1 }
increment, stack = { 3:2, 5:1 }
visit 3:2, stack = { 5:1 }
increment, stack = { 5:2 }
push 7:0, stack = { 7:0, 5:2 }
increment, stack = { 7:1, 5:2 }
push 6:0, stack = { 6:0, 7:1, 5:2 }
increment, stack = { 6:1, 7:1, 5:2 }
increment, stack = { 6:2, 7:1, 5:2 }
visit 6:2, stack = { 7:1, 5:2 }
increment, stack = { 7:2, 5:2 }
push 8:0, stack = { 8:0, 7:2, 5:2 }
increment, stack = { 8:1, 7:2, 5:2 }
increment, stack = { 8:2, 7:2, 5:2 }
visit 8:2, stack = { 7:2, 5:2 }
visit 7:2, stack = { 5:2 }
visit 5:2, stack = {}Для алгоритма левостороннего обхода дерево представляет собой стек уровней, при этом каждый уровень состоит из узлов, находящихся на одной высоте. Такой алгоритм движется по всем узлам уровня прежде чем перейти на следующий уровень. Наиболее общая реализация начинает обход с вершины (корня) и обходит каждый уровень слева направо. Например, в следующем дереве левосторонний обход посетит узлы в такой последовательности: 5, 3, 7, 2, 6, 8. Заметьте, что это не единственный способ проделать левостронний обход. Это просто наиболее распространённая реализация такого обхода. Мы используем этот способ только в качестве иллюстрации.
Левосторонний обход, вероятно, один из немногих алгоритмов на бинарных деревьях поиска, который не может быть реализован рекурсивно без блуждания всеми самыми неудобными и трудными путями. Те, кто уже хорошо знаком с рекурсией, знают, что рекурсию можно подменить использованием стека. Левосторонний обход, однако, требует очереди, поэтому рекурсия здесь не очень практична.
В теории сам по себе алгоритм крайне прост и он следует той же логике, что и алгоритм обхода в прямом порядке, за исключением того, что здесь используется очередь. Правая и левая ссылки каждого узла добавляются в очередь, затем посещается сама запись (посещение - это просто выполнение какой-либо операции на узле, например, вывод на экран его данных). Следующий узел, который должен быть посещён, находится взятием из очереди первого элемента. Ниже приводится диаграмма левостороннего обхода на дереве, показанном выше:
save 5, queue = { 5 }
visit 5, queue = {}
save 3, queue = { 3 }
save 7, queue = { 7, 3 }
visit 3, queue = { 7 }
save 2, queue = { 2, 7 }
visit 7, queue = { 2 }
save 6, queue = { 6, 2 }
save 8, queue = { 8, 6, 2 }
visit 2, queue = { 8, 6 }
visit 6, queue = { 8 }
visit 8, queue = {}Как только вы поймёте, что происходит, алгоритм станет для вас коротким и красивым. В принципе, это обход в прямом порядке с очередью вместо стека. Я использовал простой массив, как основу для вращающейся очереди с индексом для первого и последнего элемента. В целом, если отвлечься от деталей, функция действительно простая:
1 void levelorder (struct tree *tree)
2 {
3 struct node *it = tree->root;
4 struct node *q [50];
5 int front = 0, back = 0;
6
7 if (it == NULL)
8 return;
9
10 q [front++] = it;
11
12 while (front != back) {
13 it = q [back++];
14
15 printf ("%d\n", it->data);
16
17 if (it->link [0] != NULL)
18 q [front++] = it->link [0];
19 if (it->link [1] != NULL)
20 q [front++] = it->link [1];
21 }
22 }Так как эта статься посвящена не очередям, а деревьям, я не буду пояснять, как работает наша очередь и вы можете просто поверить, что она работает. Или же вы можете протестировать мой код, чтобы убедиться, что я не пытаюсь отвлечь ваше внимание. Тем более, что я тоже допускаю ошибки, поэтому никогда не повредит проверить дважды :-)
Все эти обходы хороши для того, что они делают, но обычно не очень хороши для того, чего хотим мы. По крайней мере, они не делают того, что хочу я. А я хочу вот чего:
1 int *x = first (tree);
2
3 while (x != NULL) {
4 printf ("%d\n", *x);
5 x = next (tree);
6 }Это сложно проделать с рекурсивными и нерекурсивными алгоритмами, которые мы рассмотрели, потому что где-то надо сохранять состояние и последний шаг, сделанный алгоритмом. Самый простой выход из этой ситуации - хранить информацию о состоянии обхода в отдельной структуре обхода, которая бы содержала необходимую информацию. Так как нам нужно сохранять узла, идущие дальше по дереву, нам нужен стек, как например в алгоритме обхода в глубину. Нам нужно отслеживать, какой у нас текущий узел. Мы будем использовать такую структуру (размер стека произволен, но он должен быть не меньше, чем высота предполагаемого дерева):
1 struct traversal {
2 struct node *up [50]; /* Stack */
3 struct node *it; /* Current node */
4 int top; /* Top of stack */
5 };Т.к. самый распространённый алгоритм обхода - симметричный, мы будем использовать его. Это никоим образом не единственный алгоритм, который можно осуществлять пошагово, но доступ к данным у порядоченном виде пожалуй делает его самым полезным, тем более, что добавление операций продвижения вперёд и назад при использовании этого алгоритма доволно просто. Чтобы начать симметричный обход, нам сперва надо найти узел с наименьшим значением или самый дальний левый узел. Напишем простую функцию first(), которая будет инициализировать структуру traversal и установит в качестве текущего узла самый младший узел, сохраняя путь к нему:
1 int *first (struct traversal *trav, struct tree *tree)
2 {
3 trav->it = tree->root;
4 trav->top = 0;
5
6 if (trav->it != NULL) {
7 while (trav->it->link [0] != NULL) {
8 trav->up [trav->top++] = trav->it;
9 trav->it = trav->it->link [0];
10 }
11 }
12
13 if (trav->it != NULL)
14 return &trav->it->data;
15 else
16 return NULL;
17 }Обратите внимание - возвращается не само значение, указатель на него. Это упрощает проверку границ, ведь когда обход закончен, мы может возвратить указатель на NULL. Это хорошо вписывается в мои желания, которые я упомянул выше. first() - простая функция и мы можем превратить её в last(), заменив 0 на 1, чтобы изменить направление движения на правое вместо левого.
Теперь сложная часть. Пошаговый обход нам нужно проводить начиная с самого младшего узла. Код относительно простой. Если текущий код имеет правую ссылку, мы находим порядкового преемника (старший узел, чьё значение больше текущего) ниже по дереву и обновляем стек соответственно. Если у текущего узла нет правой ссылки, мы ищем старший узел выше по дереву. При этом из стека извлекаются узлы, пока мы не посетим узел по правой ссылке. Если стек пуст, мы завершаем обход и устанавливаем указатель на текущий узел в NULL.
1 int *next (struct traversal *trav)
2 {
3 if (trav->it->link [1] != NULL) {
4 trav->up [trav->top++] = trav->it;
5 trav->it = trav->it->link [1];
6
7 while (trav->it->link [0] != NULL) {
8 trav->up [trav->top++] = trav->it;
9 trav->it = trav->it->link [0];
10 }
11 }
12 else {
13 struct node *last;
14
15 do {
16 if (trav->top == 0) {
17 trav->it = NULL;
18 break;
19 }
20
21 last = trav->it;
22 trav->it = trav->up [--trav->top];
23 } while (last == trav->it->link [1]);
24 }
25
26 if (trav->it != NULL)
27 return &trav->it->data;
28 else
29 return NULL;
30 }Теперь-то я могу делать всё, что захочу, минимально изменив код, а всё, что нам для этого понадобилось, это немного помыслить пошаговый обход, переписав код нерекурсивного обхода. Вы рады, что я сделал это для вас? :-)
1 struct traversal it;
2 int *x = first (&it, tree);
3
4 while (x != NULL) {
5 printf ("%d\n", *x);
6 x = next (&it);
7 }Вот и всё. Пошаговый обход оказался ненамного сложнее нерекурсивного обхода, да к тому же он настолько гибче, что это даже не смешно. Вы можете сделать и другие типы обхода пошаговыми, но как я сказал ранее, симметричный обход самый распространённый. Поразвлекайтесь с нерекурсивными обходами и посмотрите, как сделать их пошаговыми. Если сможете это сделать, я могу сказать спокойно, что вы понимаете концепцию :-)
Родительские указатели [наверх]
Самая большая проблема возникает при работе с бинарными деревьями, когда вам нужно сделать что-то, требующее подъёма вверх по дереву, например, чтобы совершить обход (или балансировку). Нам нужно использовать либо явный стек, в котором будет храниться путь, или неявный в виде рекурсии. Но иногда есть смысл поступить умнее. Используя для этих целей рекурсию мы можем упереться в некий предел, а определить этот предел приемлемым способом, который был бы легко адаптируемым, нельзя. Используя явный стек, мы задавали произвольную глубину стека, т.к. мы использовали не расширяющийся стек.
Теперь вы можете использовать какую-либо хорошую библиотеку для работы со стеком или придумать некий иной механизм, который позволил бы двигаться в обратном направлении вверх по дереву. Как оказывается, последнее решение более распространено, чем первое и почти все распространённые реализации используют дополнительные ссылки, указывающие на родителя, для каждого узла. Эти ссылки называются родительскими указателями:
1 struct node {
2 int data;
3 struct node *up;
4 struct node *link [2];
5 };
6
7 struct tree {
8 struct node *root;
9 };Вставка узла в дерево с родительскими указателями довольно проста. Нужно добавить совсем немного кода, чтобы адаптировать нашу функцию вставки для корректной работы с родительскими указателями. Однако необходимо позаботиться о назначении листу родительского указателя на корень, так, чтобы мы могли проверить его. Всё это выполняется функцией make_node(), которая выделяет память под новый узел, присваивает данные и устанавливает все ссылки в NULL.
1 int insert (struct tree *tree, int data)
2 {
3 if (tree->root == NULL)
4 tree->root = make_node (data);
5 else {
6 struct node *it = tree->root;
7 int dir;
8
9 for ( ; ; ) {
10 dir = it->data < data;
11
12 if (it->data == data)
13 return 0;
14 else if (it->link [dir] == NULL)
15 break;
16
17 it = it->link [dir];
18 }
19
20 it->link [dir] = make_node (data);
21 it->link [dir]->up = it;
22 }
23
24 return 1;
25 }Родителем нового узла является узел, адрес которого содержит it, здесь у нас нет проблем с установкой ссылок. До тех пор, пока вы можете получить доступ к родительскому узлу, родительские указатели тривиальны. Хотя, конечно, это усложняет рекурсивные решения по сравнению с вариантами без родительских указателей.
Удаление узла из дерева с родительскими указателями также немного сложнее. Нам нужна дополнительная переменная для хранения адреса родительского узла. Особое внимание надо обратить на обновление родительских ссылок узла, ведь возможно, что заменяющий узел будет листовым! Это может произойти с корнем дерева и далее вниз по дереву, поэтому такие ситуации мы рассматриваем, как особые случаи:
1 int remove (struct tree *tree, int data)
2 {
3 if (tree->root != NULL) {
4 struct node head = { 0 };
5 struct node *it = &head;
6 struct node *f = NULL;
7 int dir = 1;
8
9 it->link [1] = tree->root;
10 tree->root->up = &head;
11
12 while (it->link [dir] != NULL) {
13 it = it->link [dir];
14 dir = it->data <= data;
15
16 if (it->data == data)
17 f = it;
18 }
19
20 if (f != NULL) {
21 int dir = it->link [0] == NULL;
22
23 f->data = it->data;
24 it->up->link [it->up->link [1] == it] =
25 it->link [dir];
26
27 if (it->link [dir] != NULL)
28 it->link [dir]->up = it->up;
29
30 free (it);
31 }
32
33 tree->root = head.link [1];
34 if (tree->root != NULL)
35 tree->root->up = NULL;
36 }
37
38 return 1;
39 }Наконец, мы подошли к обходу. Ради этого и затевалась вся игра с родительскими указателями. Теперь для перехода к старшему узлу вверх по дереву нам не нужен хитрый стек, достаточно пройти по родительским указателям. struct traversal и first() почти не изменились и всё отличие состоит в том, что здесь не используется стек:
1 struct traversal {
2 struct node *it;
3 };
4
5 int *first (struct traversal *trav, struct tree *tree)
6 {
7 trav->it = tree->root;
8
9 if (trav->it != NULL) {
10 while (trav->it->link [0] != NULL)
11 trav->it = trav->it->link [0];
12 }
13
14 if (trav->it != NULL)
15 return &trav->it->data;
16 else
17 return NULL;
18 }Функция next() содержит больше отличий. Здесь мы, отказавшись от стека, в зависимости от необходимости можем двигаться вверх, используя родительские указатели, просто следуя по ссылкам, содержащимся в них. В принципе, логика осталась такой же и изменения минимальны. Неплохая цена за отказ от стека, не так ли?
1 int *next (struct traversal *trav)
2 {
3 if (trav->it->link [1] != NULL) {
4 trav->it = trav->it->link [1];
5
6 while (trav->it->link [0] != NULL)
7 trav->it = trav->it->link [0];
8 }
9 else {
10 for ( ; ; ) {
11 if (trav->it->up == NULL || trav->it == trav->it->up->link [0])
12 {
13 trav->it = trav->it->up;
14 break;
15 }
16
17 trav->it = trav->it->up;
18 }
19 }
20
21 if (trav->it != NULL)
22 return &trav->it->data;
23 else
24 return NULL;
25 }Правовинтовые деревья [наверх]
Родительские указатели во многих ситуациях полезны, но они требуют внесения некоторой избыточности, которая не везде и не всегда может оказаться приемлемой. Ввиду этой проблемы было придумано очень умное решение, где листья дерева могут использоваться определённым образом, указывая не на NULL, а на старшие и младшие узлы внешних узлов. Это называется винтовым деревом (или резьбовым). Теперь у нас нет избыточности дополнительных указателей, а вместо этого мы добавляем флаг, который определяет, какую ссылку содержит узел - реальную или резьбовую. Зачем флаг? Мы попали бы в бесконечный цикл, если бы не смогли отличить резьбовую ссылку от обычной. На каждую ссылку в дереве нам нужен флаг. Полные резьбовые деревья требуют 2 флагов (Здесь ваш покорный слуга вновь столкнулся с терминолическими проблемами и, в частности, с отсутствием однозначного соответствия английским терминам в русскоязычной литературе. Поневоле создаётся впечатление, что эти разновидности деревьев либо называют исключительно по-английски, либо... Их вообще никак не называют. Посему, я взял в качестве русского эквивалента термина threaded binary search tree выражение "резьбовое бинарное дерево поиска". Продолжая аналогию с резьбой, right threaded BST я назвал правовинтовым деревом. Просто имейте ввиду, что когда речь идёт о резьбе, или правовинтовых деревьях, подразмевается по существу одно и то же - резьбовые деревья - перев.) Наиболее распространённое решение использует только связь через правые ссылки, оставляя левые ссылки такими же, как в обычном дереве:
1 struct node {
2 int data;
3 int thread;
4 struct node *link [2];
5 };
6
7 struct tree {
8 struct node *root;
9 };Следующая диаграмма построена с применением упомянутой структуры. Каждая правая ссылка, которая указывала бы на лист, теперь указывает на старший узел, в то время, как левая ссылка указывает на обычный лист. Обратите внимание, что теперь мы можем напрямую пройти от узла 4 к узлу 6 вместо того, чтобы прокладывать себе путь через узел 3 при использовании родительских указателей или стека. Это первое преимущество резьбовых деревьев и вскоре вы увидите, что такие пути значительно упрощают пошаговые обходы. Также обратите внимание, как поиск узла 5 обошёл бы по кругу узлы 6 - 3 - 4, возратившись обратно к узлу 6. Вообще говоря, это нежелательно, потому мы используем флаг.
Резьбовые деревья не очень распространены, и наиболее распространённые их реализации допускают использование только левых ссылок, позволяя совершать симметричный обход, посещающий узлы в отсортированном по возрастанию порядке. Для обхода в убывающем порядке нам нужно использовать одно из других решений (родительские указатели, рекурсия или стек). Такие деревья называются правовинтовыми, потому что используется объединение в цепь по правой стороне. Код для работы с такими деревьями более сложен, чем в случае с родительскими указателями. Алгоритм поиска должен быть изменён для работы с резьбой (потоком - нитью). Если мы достигаем нити, это всё равно, как если бы мы достигли листа. Так мы избегаем не очень приятной проблемы с вечным циклом:
1 int find (struct tree *tree, int data)
2 {
3 struct node *it = tree->root;
4 int dir;
5
6 for ( ; ; ) {
7 dir = it->data < data;
8
9 if (it->data == data)
10 return 1;
11 else if (dir == 1 && it->thread == 1)
12 break;
13 else if (it->link [dir] == NULL)
14 break;
15
16 it = it->link [dir];
17 }
18
19 return 0;
20 }Т.к. симметрия нашего дерева нарушена, теперь нам необходимо учитывать разницу между движением влево (где мы можем найти лист, но не нить) и вправо (где мы можем найти нить, но не лист). При вставке поиск ведётся так же, но непосредственно при добавлении узла алгоритм должен учитывать ассимметрию. Если узел добавляется к правой ссылке, он должен принять от своего родителя нить. Если к левой ссылке, то нить передаётся родительскому узлу. Рассмотрим вставку узла 5 в резьбовое дерево, приведённое выше. 5 будет добавлено, как правая ссылка узла 4. Но правая ссылка узла 4 - нить. Чтобы обеспечить правильное построение резьбового дерева, нам нужно сместить нить вниз так, чтобы правая ссылка узла 5 указывала на узел 6. С другой стороны, если бы мы вставляли 0, то новый узел был бы присоединён к левой ссылке узла 2. Однако нам бы всё же пришлось установить правую нить узла 0 так, чтобы она ссылалась на старший узел - 2:
До тех пор, пока вы придерживаетесь этих правил для операции вставки, построение резьбового дерева - лёгкая работа, т.к. изменения, которые нужно вносить в дерево, носят локальный характер и вам не приходится обрабатывать всю структуру. Код, который это делает, не особо сложен, но он может вводить в заблуждение, если вы незнакомы с резьбовыми деревьями. В частности, кое-что этот код делает иначе для правых и левых ссылок. make_node() всё так же захватывает память, присваивает данные, устанавливает ссылки в NULL, но для резьбового дерева эта функция также устанавливает флаг в 1, потому что новый узел всегда будет внешним и без потомков. Заметьте, что самый правый узел в дереве имеет нить, ведущую к листу. Это может повлиять на другие операции на дереве. Вот и сам код:
1 int insert (struct tree *tree, int data)
2 {
3 if (tree->root == NULL)
4 tree->root = make_node (data);
5 else {
6 struct node *it = tree->root, *q;
7 int dir;
8
9 for ( ; ; ) {
10 dir = it->data < data;
11
12 if (it->data == data)
13 return 0;
14 else if (dir == 1 && it->thread == 1)
15 break;
16 else if (it->link [dir] == NULL)
17 break;
18
19 it = it->link [dir];
20 }
21
22 q = make_node (data);
23
24 if (dir == 1) {
25 q->link [1] = it->link [1];
26 it->thread = 0;
27 }
28 else
29 q->link [1] = it;
30
31 it->link [dir] = q;
32 }
33
34 return 1;
35 }Вместо непосредственного присвоения нового узла напрямую родителю, мы сохраняем его во временной переменной. Таким образом текущая нить родительского узла не теряется, если новый узел должен стать правой ссылкой родителя и процесс добавления нового узла в резьбовое дерево вовсе не так сложен, если вы понимаете идею :-)
Удаление узла из резьбового дерева следует тому же шаблону, но здесь у нас есть 4 случая изъятия узла из дерева. Если узел, который мы хотим удалить, не имеет потомков и является левым потомком своего родителя, мы можем просто изменить левую ссылку родителя, чтобы она указывала на лист. Если наш узел - правый и не имеет дочерних узлов, нам нужно установить правую ссылку его родителя в то же значение, которое содержит правая ссылка нашего удаляемого узла, чтобы сохранить нить.
Если узел, который мы хотим удалить, имеет потомков (это внешний узел, поэтому у него будет только один дочерний узел) и этот потомок - правый узел, мы просто заменяем удаляемый узел этим потомком, т.к. изменений в пути нити вносить не нужно. С другой стороны, если потомок слева, нам нужно передать нить удаляемого узла дочернему узлу, прежде чем мы заменим удаляемый узел его потомком. Здесь есть небольшая хитрость, но она стоит того, чтобы применить её в пошаговом обходе:
Код для выполнения удаления не очень сложен, но сперва он может показаться запутанным. Как обычно, мы используем элегантное удаление заменой узла, потому что оно короче и красивее. Красота - это хорошо. Я очень-очень серьёзно подхожу к моему коду с эстетических позиций. Конечно, это не значит, что я так же очень-очень серьёзно не подхожу к правильности кода ;-)
1 int remove (struct tree *tree, int data)
2 {
3 if (tree->root != NULL) {
4 struct node head = { 0 };
5 struct node *it = &head;
6 struct node *q, *p, *f = NULL;
7 int dir = 1;
8
9 it->link [1] = tree->root;
10
11 while (it->link [dir] != NULL) {
12 if (dir == 1 && it->thread == 1)
13 break;
14
15 p = it;
16 it = it->link [dir];
17 dir = it->data <= data;
18
19 if (it->data == data)
20 f = it;
21 }
22
23 if (f != NULL) {
24 q = it->link [it->link [0] == NULL];
25 dir = p->link [1] == it;
26 f->data = it->data;
27
28 if (p == q)
29 p->link [0] = NULL;
30 else if (it->link [0] == NULL && it->thread) {
31 p->thread = 1;
32 p->link [1] = it->link [1];
33 }
34 else if (it->link[0] == NULL)
35 p->link [dir] = q;
36 else {
37 q->thread = it->thread;
38 q->link [1] = it->link [1];
39 p->link [dir] = q;
40 }
41
42 free (it);
43 }
44
45 tree->root = head.link [1];
46 }
47
48 return 1;
49 }Хорошо, но как эти условия соответствуют рассмотренным выше случаям? p - это родитель, а q - дочерний узел, которым мы заменяем родителя. Если p == q, то q - правый узел it и его нить к p. Это соответствует случаю, где мы на диаграмме удаляем узел 0. Если левая ссылка узла, который мы хотим удалить - лист, а правая - нить, то это соответствует тому случаю, когда мы удаляли узел 5. Если левая ссылка удаляемого узла равна NULL, а правая ссылка - не нить, то у нас случай с удалением узла 4. Ну и наконец последнее - случай с удалением узла 2 на диаграмме. Если вы хорошо понимаете, что происходит в каждом случае, то с пониманием кода у вас проблем возникнуть не должно.
Пошаговый обход очень упростился, потому что нам не нужно искать старший узел. Всё что нам нужно, так это пройти по ссылке. Вот и всё волшебство, которое было нам необходимо для движения вверх по дереву. Но это до тех пор, пока мы не дошли до правой стороны. Представленный алгоритм и является сакральной сутью симметричного обхода (ну, за исключением того, что иметь возможность двигаться в обоих направлениях в полностью резьбовом дереве было бы круче). Позор, что мы так долго шли к построению дерева, которое позволяет это:
1 struct traversal {
2 struct node *it;
3 };
4
5 int *first (struct traversal *trav, struct tree *tree)
6 {
7 trav->it = tree->root;
8
9 if (trav->it != NULL) {
10 while (trav->it->link [0] != NULL)
11 trav->it = trav->it->link [0];
12 }
13
14 if (trav->it != NULL)
15 return &trav->it->data;
16 else
17 return NULL;
18 }
19
20 int *next (struct traversal *trav)
21 {
22 if (trav->it->thread == 0) {
23 trav->it = trav->it->link [1];
24
25 if (trav->it != NULL) {
26 while (trav->it->link [0] != NULL)
27 trav->it = trav->it->link[0];
28 }
29 }
30 else
31 trav->it = trav->it->link [1];
32
33 if (trav->it != NULL)
34 return &trav->it->data;
35 else
36 return NULL;
37 }Родительские указатели более распространены, чем резьбовые деревья просто потому, что на указателях проще представить, что происходит. Правовинтовые деревья - самая распространённая разновидность резьбовых деревьев, но вы можете реализовать и симметричновинтовое дерево, которое похоже на рассмотренные выше, но позволяет иметь нити для двух направлений. Логика этих деревьев достаточно схожа с рассмотренной нами. Мы рассмотрели только довольно общий вариант, чтобы свести к минимуму затраты на лечение моего туннельного синдрома, который я получу от написания этих статей ;-)
Производительность [наверх]
Немного полезной теории касательно деревьев. Вам нужно знать, насколько хороши деревья на практике и для этого лучше обратиться к анализу, проведённому людьми, которые умнее, чем я. Если операции удаления и вставки случайны, то средняя эффективность дерева O(log N), или логарифм по основанию 2, или число степеней 2, чтобы добраться до N. И на самом деле, это хорошо, кстати. Если эффективность поиска O(log N), то на каждом последующем шаге поиска диапазон вариантов уменьшается где-то наполовину. Поэтому поиск в дереве очень быстрый, если операции вставки и удаления случайны.
Заметьте, я говорю "если вставка и удаление случайны". Таким образом я прикрываюсь от нападок тех дотошных личностей, которые готовы были бы меня сжечь на костре инквизиции, если бы я высказал своё мнение, как абсолютное. На самом деле для бинарных деревьев поиска есть действительно ужасный случай, когда каждый узел дерева - внешний. Самый простой способ получить такое дерево - вставка упорядоченной по возрастанию последовательности:
Вместо структуры с эффективностью O(log N) мы, в принципе, получили связный список, а производительность упала до O(N). Такой случай называют вырожденным деревом и он проявляется при крайне неблагоприятных последовательностях операций вставки и удаления, которые невозможно предсказать. Это не способствует надёжности деревьев. Дерево, которое пытается противостоять таким случаям, исправляя ситуацию, называется сбалансированным. Все деревья, рассмотренные в этой статье, несбалансированные, поэтому всё, что в ваших силах - убедиться, что вставка и удаления будут производиться случайно. Это уменьшит вероятность вырождения дерева.
Есть разные способы гарантировать близкую к оптимальной производительность либо при каждой операции, либо после последовательности таких операций, но эти способы могут быть очень сложными. Я написал руководства по наиболее распространённым таким способам, поэтому здесь я не буду снова повторять самого себя. Можно также полностью перебалансировать дерево. Например, копировать все узлы дерева в массив, затем выполнять по массиву что-то, вроде бинарного поиска, рекурсивно выбирая средний узел и вставляя его в новое дерево. В результате мы получим хорошо сбалансированное дерево. После такой перебалансировки вырожденное дерево, подобное тому, что приведено выше, примет такой вид:
Ещё лучше, что эту схему легко представить и реализовать, но она неэффективна. Другое способ - изменять структуру на самую худшую, как показано ниже (только временно, разумеется!), а затем выполнить операцию, называемую поворотом через каждый узел. Реализацию я оставлю вам (гуглите DSW, если хотите), а сам процесс будет выглядеть так:
Глобальная перебалансировка дерева довольно затратная операция, потому что её эффективность по крайней мере O(N), так что, если вы хотите обеспечивать структуру дерева таким способом, откладывайте перебалансировку как можно дольше :-) В случаях, когда вероятность вырождения дерева высока, используются разные схемы балансировки (такие, как AVL или красно-чёрные деревья), которые обеспечивают баланс за счёт локальных изменений. Это лучший выход, потому что сложность массовой перебалансировки всего дерева распределяется между отдельными операциями. Такой подход эффективнее, чем одна неэффективная массовая операция.
Окончательный вывод: эффективность бинарных деревьев поиска в среднем для дерева из N узлов составляет O(log N) и O(N) в худшем случае, что делает несбалансированное дерево не таким полезным, сбалансированное со средней гарантированной эффективностью O(log N). Но если известно, что данные на входе поступают в случайном порядке, небалансируемое дерево легче в реализации и поддержании..
Уф! Кто знал, что бинарные деревья поиска такие разносторонние? Я знал, а теперь знаете и вы. Темы, касающиеся деревьев, весьма многочисленны. Я бы мог забить статьями об этом всю квоту на хостинге. Однако, большая часть этого всего не имеет практической пользы в реальной жизни, либо интересно только интеллектуалам, которые сами не пишут реального кода. Я охватил те темы, которые позволят вам заработать ваши <название местной валюты> и те, которые в состоянии реализовать обычный человек. Как это часто бывает со структурами данных, вы можете усложнить их, насколько угодно и некоторые из балансирующихся деревья именно это и делают.
Это руководство (надеюсь!) прояснило для вас, что такое бинарное дерево поиска и как реализовать такое дерево. Мы не просто прошлись по основам, но рассмотрели различные элегантные и эффективные вариации алгоритмов и трюки, призванные улучшить гибкость базовых бинарных деревьев поиска за счёт сокращения сложности обходов. И наконец, мы немного прошлись по теории (совсем немного) в той части, что касается производительности, познакомившись не только с преимуществами деревьев, но и с их недостатками.
Оригинал этой статьи вы можете найти здесь: eternallyconfuzzled.com.
