Студопедия

КАТЕГОРИИ:

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



Применение бинарных деревьев в алгоритмах поиска.

Читайте также:
  1. II. ХИМИЯ НЕОРГАНИЧЕСКИХ СОЕДИНЕНИЙ, БИОЛОГИЧЕСКАЯ РОЛЬ, ПРИМЕНЕНИЕ В ВЕТЕРИНАРИИ
  2. SWOT - анализ и его применение в маркетинговых исследованиях.
  3. Агрегатный индекс как форма общего индекса. Выбор весов при построении общих индексов. Индексы цен Г. Пааше и Э. Ласпейреса, их практическое применение.
  4. Административная ответственность – это применение уполномоч органом или должност лицом админ наказания к лицу,совершившему админ правонаруш.
  5. Аллергические пробы, их сущности, применение.
  6. Ароматические углеводороды. Структурная формула бензола (по Кекуле). Химические свойства бензола. Получение и применение бензола и его гомологов.
  7. Асбоцементные изделия. Свойства, разновидности, применение.
  8. Ацетилен – представитель углеводородов с тройной связью в молекуле. Свойства, получение и применение ацетилена.
  9. Б-12. Видеозапись как средство фиксации криминалистически значимой информации. Применение видеозаписи при производстве следственных действий.
  10. Б9.6 Работы с применением автомобилей, грузоподъемных машин.

В односвязном списке невозможно использовать бинарные методы, они могут использоваться только в последовательной памяти. Однако, если использовать бинарные деревья, то в такой связной структуре можно получить алгоритм поиска со сложностью O(log 2 N). Такое дерево реализуется следующим образом: для любого узла дерева с ключом Ti все ключи в левом поддереве должны быть меньше Ti, а в правом – больше Ti. В дереве поиска можно найти место каждого ключа, двигаясь, начиная от корня и переходя на левое или правое поддерево, в зависимости от значения его ключа. Из n элементов можно организовать бинарное дерево (идеально сбалансированное) с высотой не более чем log 2 N, которое определяет количество операций сравнения при поиске.

Function Search (x: integer; t: ElPtr): ElPtr;

Ti L_Son R_Son
{поле Data заменим на поле Key}

var f: boolean;

begin

< Ti > Ti
f:=false;

while (t<>nil) and not f do

if x=t^. key then f:=true

else if x>t^. key then t:=t^. R_Son else t:=t^. L_Son;

Search:=t;

end;

Если получим, что значение функции = nil, то ключа со значением x в дереве не найдено.

 

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

 

 


Function Search (x: integer; t: ElPtr): ElPtr;

begin

S^.key:=x;

while t^.key<>x do

if x > t^.key then then t:=t^. R_Son else t:=t^. L_Son;

Search:=t;

end;


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


<== предыдущая лекция | следующая лекция ==>
Операция исключения из бинарного дерева. | СД типа граф.
lektsii.com - Лекции.Ком - 2014-2019 год. (0.011 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты