Операция включения в СД типа бинарное дерево

Рассмотрим случай постоянно растущего, но никогда не убывающего дерева. Хорошим примером этого является построение частотного словаря. В этой задаче задана последовательность слов и нужно установить число появления каждого слова. Это означает, что, начиная с пустого дерева, каждое слово, встречающееся в тексте, ищется в нем. Если это слово найдено, то счетчик появления данного слова увеличивается; если же слово не найдено, то в дерево включается новое слово со значением счетчика = 1.

Type ElPtr = ^Element

Element = record

Key: integer;

n: integer;

L_Son, R_Son: ElPtr;

end;

Procedure Put (x: integer; var t: ElPtr);

begin

if t=nil then begin

New(t);

with t^ do begin

key:=x; n:=1; L_Son:=nil; R_Son:=nil;

end;

end

else if x> t^.key then Put(x, t^.R_Son)

else if x<t^.key then Put(x, t^.L_Son)

else t^.n:=t^.n+1;

end;

Хотя задача этого алгоритма – поиск с включением, но его можно использовать и для сортировки, т.к. он напоминает сортировку с включением. А так как вместо массива используется дерево, то пропадает необходимость перемещения элементов выше места включения. Для того, чтобы сортировка этого алгоритма была устойчивой, алгоритм должен выполняться одинаково как при t^.key=x, так и при t^.key>x.

	Пусть задана последовательность: 30, 1, 15, 17, 18, 50, 2, 60. После построения дерева осуществляется прохождение дерева в симметричном порядке: 1, 2, 15, 17, 18, 30, 50, 60.

Анализ алгоритма поиска. Если дерево вырождается в последовательность то сложность в таком случае O(N) (в худшем случае). В лучшем же случае, если дерево сбалансировано, то сложность будет O(log ₂ N). Таким образом, имеем:

O(N) £ П_ФВС £ O(log ₂ N).

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

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

Дата добавления: 2014-01-07