Двоичные деревья поиска.

Деревья поиска – частный, но практически, пожалуй, наиболее важный вид двоичных деревьев. Будем считать, что каждая вершина имеет некое ключевое поле, позволяющее упорядочить множество вершин. Двоичное дерево называется деревом поиска или поисковым деревом, если для каждой вершины дерева все ключи в ее левом поддереве меньше ключа этой вершины, а все ключи в ее правом поддереве больше ключа вершины.

Пример дерева поиска с целыми ключами представлен на следующем рисунке.

Деревья поиска являются одной из наиболее эффективных структур построения упорядоченных данных. Как известно, в упорядоченном массиве очень эффективно реализуется поиск (дихотомия!), но очень тяжело выполнить добавление и удаление элементов. Наоборот, в упорядоченном списке легко реализуется добавление и удаление элементов, но не эффективна реализация поиска из-за необходимости последовательного просмотра всех элементов, начиная с первого. Деревья поиска позволяют объединить преимущества массивов и линейных списков: легко реализуется добавление и удаление элементов, а также эффективно выполняется поиск.

Эффективность процесса поиска в ДП определяется дихотомической структурой самого дерева. На каждом шаге поиска, начиная с корня, отбрасывается одно из поддеревьев - левое или правое. Двоичный поиск наиболее эффективен для идеально сбалансированных деревьев или близких к ним. В самом плохом случае число сравнений равно высоте дерева. При этом, как и в методе двоичного поиска в упорядоченном массиве, сравнительная эффективность поиска в ДП быстро увеличивается при увеличении числа вершин в этом дереве.

Например, если идеально сбалансированное ДП имеет 1000 вершин, то даже в наихудшем случае потребуется не более 10 сравнений (2 в степени 10 есть 1024), а если число вершин 1 миллион, то потребуется не более 20 сравнений.

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

Интересно заметить, что обход ДП в симметричном порядке позволяет получить исходный набор данных в соответствии с заданным упорядочиванием, а обход в обратно-симметричном порядке – в обратном порядке.

Алгоритм поиска в ДП очень прост:

Начиная с корневой вершины для каждого текущего поддерева надо выполнить следующие шаги:

· сравнить ключ вершины с заданным значением x

· если заданное значение меньше ключа вершины, перейти к левому потомку, иначе перейти к правому поддереву.

Поиск прекращается при выполнении одного из двух условий:

· либо если найден искомый элемент

· либо если надо продолжать поиск в пустом поддереве, что является признаком отсутствия искомого элемента

Интересно, что поиск очень легко можно реализовать простым циклом, без использования рекурсии:

pCurrent := pRoot; {начинаем поиск с корня дерева}

Stop := false;

While (pCurrent <> nil) and (not Stop) do

if x < pCurrent ^.inf then pCurrent := pCurrent^.left else

if x > pCurrent ^.infthen pCurrent := pCurrent^.right else Stop := true;