Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



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




Читайте также:
  1. Агропромышленная интеграция и кооперация в сельскохозяйственном производстве (значение, понятие, виды)
  2. Б-деревья. Определение Алгоритмы поиска, включения и исключения. Необходимость их применения.
  3. Билет № 13 Загрузка компьютера: Тест начального включения – POST. Загрузка DOS
  4. Билет № 14 Загрузка компьютера: Тест начального включения – POST. Загрузка MS Windows 9.x
  5. Валютная политика: понятие, цели, формы и инструменты. Валютные ограничения по текущим и финансовым операциям.
  6. ВАЛЮТНОЕ РЕГУЛИРОВАНИЕ И КОНТРОЛЬ, ОСУЩЕСТВЛЯЕМЫЙ БАНКОМ ПО ЭКСПОРТНЫМ И ИМПОРТНЫМ ОПЕРАЦИЯМ.
  7. Включения записи в БД
  8. Вопрос 24 Учет расчетов с персоналом по прочим операциям
  9. Вопрос 60. Учет затрат по нормам. Порядок списанная и включения отклонений от норм в себестоимость отдельных изделий.
  10. Вопрос № 60 Топография толстой кишки. Колостомия. Операция наложения противоестественного заднего прохода по способу Майдля.

Рассмотрим случай постоянно растущего, но никогда не убывающего дерева. Хорошим примером этого является построение частотного словаря. В этой задаче задана последовательность слов и нужно установить число появления каждого слова. Это означает, что, начиная с пустого дерева, каждое слово, встречающееся в тексте, ищется в нем. Если это слово найдено, то счетчик появления данного слова увеличивается; если же слово не найдено, то в дерево включается новое слово со значением счетчика = 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 2 N). Таким образом, имеем:

O(N) £ ПФВС £ O(log 2 N).

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

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

 


Дата добавления: 2015-04-18; просмотров: 5; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2020 год. (0.005 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты