скачать doc
2.3.Случайные бинарные деревья поиска
Рассмотрим процедуру добавления элемента в БДП. Дополним запись, представляющую узел дерева, полем Count, в котором будем фиксировать повторные попытки вставки элемента в дерево:
Node = record
Info: Elem;
Count: Word;
LSub, RSub: BTree
end {Node}
Процедура SearchAndInsert – поиска и вставки элемента x в дерево b – в случае успешного поиска увеличивает счетчик Count в найденном узле, а в случае неудачного поиска добавляет лист в подходящее (т. е. с сохранением инварианта БДП) место дерева поиска.
procedure SearchAndInsert (x: Elem; var b: BTree);
begin
if b = nil then
begin
New (b);
with b do
begin
Root := x; LSub := nil; RSub := nil
end {with}
end
else {b nil}
with b do
if x < Root then SearchAndInsert (x, LSub)
else if x > Root then SearchAndInsert (x, RSub)
else Count := Count + 1
{end with};
end {SearchAndInsert}
Пусть во входном файле f_input: file of Elem находится последовательность элементов, по которой функции SearchAndInsert строит БДП:
b := nil;
while not Eof (f_input) do
begin
Read (f_input, x);
SearchAndInsert (x, b)
end {while}
БДП, построенное таким способом, называется случайным БДП. Структура этого дерева полностью зависит от того («случайного») порядка, в котором элементы расположены во входной последовательности (во входном файле). В качестве простейшего примера рассмотрим последовательность из четырёх элементов a, b, c, d. Имеется 4! = 24 перестановки из четырёх элементов и, следовательно, 24 варианта входной последовательности. На р
исунке *** изображены все 24 дерева, построенные процедурой SearchAndInsert.
В каждом узле в качестве нижнего индекса указан порядковый номер вставки элемента (его номер во входной последовательности). Видно, что некоторые деревья фактически совпадают, отличаясь только порядком построения (индексами у элементов). Например, совпадают два дерева, соответствующие перестановкам acbd и acdb. Среди идеально сбалансированных деревьев совпадений больше. В частности одинаковые деревья получаются для каждой из следующих троек перестановок: 1) bacd, bcad и bcda; 2) badc, bdac и bdca; 3) cabd, cadb и cdab; 4) cbad, cbda и cdba. Всего в этом примере 12 идеально сбалансированных деревьев. В случаях полностью упорядоченных входных перестановок abcd и dcba деревья фактически вырождаются в линейные списки и имеют максимальную высоту.
Легко убедиться, что в рассмотренном примере имеется 14 структурно различных бинарных деревьев (например, соответствующих перестановкам abcd, abdc, acbd, adbc, adcb, bacd, badc, cabd, cbad, dabc, dacb, dbac, dcab, dcba). В общем случае число
структурно различных бинарных деревьев с n узлами удовлетворяет рекуррентному уравнению 
с начальными условиями
Это рекуррентное уравнение с точностью до обозначений совпадает с рекуррентным уравнением, получающимся при подсчёте числа расстановки скобок в произведении n сомножителей (см. Приложение). Оказывается [Конкретная математика или Романовский И.В.], что решением этого рекуррентного уравнения являются так называемые числа Каталана Сn, т. е. bn = Сn. В Приложении приведена общая формула для чисел Каталана, асимптотическое соотношение 
и несколько первых чисел Каталана, в том числе С4 = 14, что соответствует рассмотренному примеру.
Рассмотрим операцию поиска минимального элемента в БДП. Если в дереве b левое поддерево пусто, то минимальное значение находится в корне. Если же левое поддерево не пусто, то минимальное значение (см. рисунок) находится в самом левом элементе левого поддерева, который может быть найден после выполнения следующего цикла:
while b.LSub ≠ nil do b := b.LSub
Аналогичным образом находится максимальный (крайний правый) элемент БДП.
Удаление элемента из случайного БДП проще всего происходит, если этот элемент находится в листе дерева. Тогда этот лист непосредственно удаляется. Если же удаляемый элемент находится во внутреннем узле b, то в ситуации b.RSub ≠ nil находим минимальный элемент правого поддерева, рекурсивно удаляем его и заменяем им содержимое узла b. Этот процесс схематично показан на рисунке.
В ситуации b.RSub = nil (следовательно, b.LSub ≠ nil) находим максимальный элемент левого поддерева, рекурсивно удаляем его и заменяем им содержимое узла b.
Количество шагов рассмотренных операций вставки, удаления и нахождения минимального элемента в случайном БДП в худшем случае равно высоте дерева. Зависимость высоты случайного БДП от количества узлов дерева рассмотрена далее.