Студопедия

КАТЕГОРИИ:

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



Операция исключения из бинарного дерева.




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

При удалении узла дерево должно оставаться упорядоченным относительно ключа:

а) удаляется лист;

б) удаляется узел с одним потомком (потомок слева или справа);

в) удаляется узел с двумя потомками, но в левом потомке нет правого поддерева;

г) общий случай.

t
Рассмотрим случай б):

t
if g^.L_Son=nil then begin

K
K
g:=t;

t:=t^.R_Son;

g
g
dispose(g);

end;

if g^.R_Son=nil then begin

g:=t;

t:=t^.L_Son;

dispose(g);

end;

Случай а) является частным случаем этого алгоритма.

Случай в): r указывает на элемент, не имеющий правого поддерева.

g:=t;

t
g^.key:=r^.key;

g
К
g:=r;

r
r:=r^.L_Son;

dispose(g);

 
 

 


Мы ищем такой элемент, у которого отсутствует правое поддерево (на такой элемент указывает r). Последовательность операторов та же, т.е. удаляемый элемент нужно заменить самым правым элементом его левого поддерева. Такие элементы не могут иметь более одного потомка.
Случай г):

 

 


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

var g: ElPtr;

begin

if t=nil then {обработка исключительной ситуации, когда элемента с заданным ключом в дереве нет}

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

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

else begin

g:=t;

if g^.L_Son=nil then t:=g^.R_Son

else if g^.R_Son=nil then t:=g^.R_Son

else D(g^.L_Son); {найти r)

dispose(g);

end;

end;


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





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