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

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

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

как Прологовские предложения могут выполнить такую же работу. Но, деревья

можно использовать и иначе.

В деревьях имеется возможность так хранить данные, что их можно быс-

то найти. Дерево построенное для такой цели называется поисковым деревом.

С точки зрения пользователя, сама структура дерева не несет информации,

дерево - это просто более быстрая альтернатива списку или массиву. Вспом-

ним, что при обходе обычного дерева, вы рассматриваете текущий узел, а

затем оба его поддерева. Чтобы найти определенное значение, вы должны

рассмотреть каждый узел всего дерева.

Время, затрачиваемое на поиск в обычном дереве из N элементов, в

среднем пропорционально N.

Бинарное поисковое дерево строится таким образом, что глядя на любой

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

Это делается заданием отношения порядка между значениями, таким как алфа-

витный или пронумерованрый порядок. Значения в левом поддереве предшест-

вуют значению в текущем узле и следуют после правого поддерева. На рисун-

ке 7.3 показан пример. Заметьте, что те же имена установленные в другом

порядке дадут другое дерево. Заметьте так же, что хотя в дереве десять

имен, любое из них можно найти максимум за пять шагов.

Grasso

/ \

/ \

/ \

/ \

/ \

Blackwell Rankin

/ \ / \

/ \ / \

/ \ / \

/ \ / \

Anthony Chisholm Mott Tubman

/ \

/ \

/ \

Loverlace OKeeffe

\

\

\

Stanton

Рисунок 7.3: Бинарное поисковое дерево

Как только вы посмотрите во время поиска на узел бинарного поисково-

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

и провести поиск очень быстро. Если теперь размер дерева увеличить вдвое,

то для поиска потребуется только один дополнительный шаг.

Время, требуемое для поиска значения на бинарном поисковом дереве, в

среднем пропорционально log2 N (а, в действительности, пропорционально

log N по любому основанию).

Чтобы построить дерево, нужно начать с пустого дерева и добавлять к

нему значения одно за другим. Процедура добавления значения такая же, как

при поиске: необходимо просто найти место, где оно должно находится и

вставить его туда. Этот алгоритм заключается в следующем:

1. Если текущее после узла - есть пустое дерево, то вставить в него

значение.

2. Иначе, сравнить значение, которое необходимо вставить со значени-

ем в текущем узле. Вставить значение в левое или правое поддерево, в

зависимости от результата сравнения.

В Прологе этому алгоритму нужно три предложения - по одному на каж-

дый случай. Первое предложение таково:

insert(NewItem, empty, tree(NewItem, empty, empty) :-!.

На естественный язык эта запись переводится так: " Результатом

вставки NewItem (нового значения) в empty (пустое дерево) будет дерево

tree(NewItem, empty, empty)." Восклицательный знак говорит, что если это

предложение можно успешно применить, то другие предложения проверять не

надо.

Второе и третье предложения осуществляют вставку в непустые деревья:

insert(NewItem, tree(Element, Left, Right),

tree(Element, NewLeft, Right) :-

NewItem < Element, !, insert(NewItem, Left, NewLeft).

insert(NewItem, tree(Element, Left, Right),

tree(Element, Left, NewRight) :-

insert(NewItem, Right, NewRight).

Если NewItem < Element, то вы вставляете его в левое поддерево, а

если иначе, то вставляете его в правое поддерево. Заметьте, что третье

предложение будет выполняться, если не подошло ни одно из первых двух.

Заметьте так же, как много работы надо проделать в начале предложения,

чтобы подобрать аргументы.