Бинарное дерево поиска

13.1.1 Структура бинарного дерева поиска и алгоритм поиска

В подразделе 10.7 бинарное дерево поиска представлено как структура, используемая в одном из возможных методов поиска. Перейдем к более детальному рассмотрению подобных деревьев.

Как следует из названия, бинарное дерево поиска (binary search tree) в первую очередь является бинарным деревом, как показано на рисунке 10.3. Такое дерево может быть представлено связанной структурой данных (естественное представление дерева, см. п. 9.4.1), в которой каждая вершина является записью. В дополнение к полю (или полям) ключа key и сопутствующих данных, каждая вершина содержит поля left, right и parent, которые являются указателями на левую и правую дочерние вершины и на родительскую вершину соответственно. Если дочерняя или родительская вершины отсутствуют, то соответствующее поле содержит значение Nil. Единственная вершина, у которой указатель parent равен Nil, – это корень дерева. Ключи в бинарном дереве хранятся в упорядоченном виде: для каждой текущей вершины ключ левой дочерней вершины меньше или равен ключу самой текущей вершины, а этот ключ, в свою очередь, меньше или равен ключу правой дочерней вершины.

Свойство бинарного дерева поиска позволяет вывести все ключи, находящиеся в дереве, в отсортированном порядке с помощью смешанного обхода (обхода in-order), излагаемого в п. 9.4.3.

Алгоритм поиска использует упорядоченность вершин дерева. Поиск выполняется следующим образом. Поиск начинается с корневой вершины, которая становится текущей. Затем аргумент поиска сравнивается с ключом текущей вершины. Если они равны, то поиск завершается результативно – текущая вершина является искомой вершиной. В противном случае, если аргумент поиска меньше ключа текущей вершины, то текущим становится левая дочерняя вершина. Если он больше, то текущей становится правая дочерняя вершина. Снова выполняется шаг сравнения. Со временем будет либо найден искомый элемент, либо встретится очередной указатель на дочерний элемент, который равен Nil, что свидетельствует об окончании поиска, который безуспешен.

Необходимо отметить одну особенность приведенного алгоритма в случае поиска по вторичному ключу. Если в дереве имеется несколько элементов с равными ключами, то не существует никаких гарантий, что будет найдена конкретная вершина с соответствующим ключом. Следовательно, дублирование ключей в дереве поиска не допускается. На практике различение ключей обеспечивается использованием, кроме главного ключа, дополнительного младшего ключа (или ключей). В результате определение дерева бинарного поиска будет формулироваться следующим образом: это дерево, в котором ключ левой дочерней вершины строго меньше ключа данной вершины, который, в свою очередь, строго меньше ключа правой дочерней вершины.

Алгоритм поиска в дереве бинарного поиска имитирует бинарный поиск в массиве. В каждой текущей вершине принимается решение об игнорировании вершин в одном из дочерних поддеревьев. Если дерево поиска сбалансировано (см. п. 9.4.2), алгоритм поиска является операцией типа О(log(N)), где N – число вершин в дереве.

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

На рисунке 13.1 показаны два бинарных дерева поиска. Дерево на рисунке 13.1б менее эффективно для поиска, поскольку его высота равна 4, в отличие от дерева на рисунке 13.1а, высота которого равна 2.

Рисунок 13.1 – Бинарные деревья поиска

13.1.2 Вставка элемента в бинарное дерево поиска

Вставить новую вершину в бинарное дерево поиска довольно просто. С помощью алгоритма поиска, изложенного ранее, отыскивается вершина с одной или двумя нулевыми ссылками left или (и) right. Если ключ вставляемого элемента меньше ключа вершины с нулевой ссылкой left, то эта ссылка направляется к новой вершине, если больше, то к новой вершине направляется ссылка right, если она была нулевой. В результате вставленный элемент оказывается листом (его обе ссылки left и right являются нулевыми). На рисунке 13.2 показан результат вставки в дерево бинарного поиска вершины с ключом 13.

Рисунок 13.2 – Вставка в дерево бинарного поиска элемента с ключом 13.
Светлые вершины располагаются на пути от корня к позиции вставки;

пунктиром указана связь, добавляемая при вставке новой вершины

Алгоритм вставки сопряжен с одной проблемой. Хотя алгоритм гарантирует создание допустимого дерева бинарного поиска, после выполнения алгоритма дерево может быть неоптимальным или неэффективным. Пусть в пустое дерево бинарного поиска вставляются элементы с ключами 2, 5, 7, 8. С ключом 2 все просто – он становится ключом корня. Вершины с остальными ключами добавляются в качестве правых дочерних вершин для предшествующих ключей. Результат представляет длинное вытянутое вырожденное дерево, показанное на рисунке 13.3.

Рисунок 13.3 – Вырожденное дерево бинарного поиска

Если бы можно было гарантировать случайный порядок вставки ключей и вершин, или если бы общее количество вершин было очень небольшим, описанный алгоритм вставки оказался бы приемлемым. Однако в общем случае подобную гарантию нельзя дать, поэтому необходимо использовать более сложный метод вставки, частью которого является стремление сбалансировать дерево бинарного поиска. Этот метод балансировки используется в красно-черных деревьях.

13.1.3 Удаление из бинарного дерева поиска

Процедура удаления заданной вершины z из бинарного дерева поиска рассматривает три возможные ситуации. Если у удаляемой вершины нет дочерних вершин, т. е. удаляемая вершина – лист, то у его родителя указатель на z получает значение Nil.

Если у удаляемой вершины z только одна дочерняя вершина, то с помощью «переброски» указателя от родителя вершины z к ее дочерней вершине, как это показано на рисунке 13.4.

Рисунок 13.4 – Удаление из дерева бинарного поиска элемента с ключом 18,
который имеет только одну дочернюю вершину.
Двойная стрелка указывает на результат выполнения удаления

Если у удаляемой вершины z имеется две дочерних вершины, то определяется следующая за ним вершина s, у которой нет левого сына. Затем все данные, кроме структурных ссылок, из вершины s копируются в поля удаляемого элемента, а вершина s удаляется путем создания новой связи между ее родителем и сыном. Эти преобразования иллюстрируются рисунком 13.5.

Рисунок 13.5 – Удаление из дерева бинарного поиска элемента с ключом 5,
который имеет две дочерних вершины.
Вершина 6 удаляется, ее данные копируются в слот вершины 5.

В литературных источниках показано, что бинарные деревья поиска высоты h обеспечивают выполнение базовых операций за время О(h). К базовым операциям в данном случае относятся операции поиска, вставки, удаления, определения максимального и минимального ключа и некоторые другие операции

Таким образом, операции выполняются тем быстрее, чем меньше высота дерева. Однако в наихудшем случае, когда при плохом расположении ключей вставляемых вершин дерево приближается к вырождению, эффективность бинарного дерева поиска ничуть не лучше, чем эффективность, которую обеспечивает линейный связный список.