Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

ПРИНЦИП РАБОТЫ АЛГОРИТМА.




Заказать ✍️ написание работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Рассмотрим бинарное дерево представленное на рис. 6.28 (а), которое состоит только из двух узлов. Включение ключа 7 дает вначале несбалансированное дерево (т.е. линейный список). Его балансировка требует однократного правого (RR) поворота, давая в результате идеально сбалансированное дерево (b). Последующее включение узлов 2 и 1 дает несбалансированное поддерево с корнем 4. Это поддерево балансируется однократным левым (LL) поворотом (d). Далее включение ключа 3 сразу нарушает критерий сбалансированности в корневом узле 5.

Сбалансированность теперь восстанавливается с помощью более сложного двукратного поворота налево и направо (LR); результатом является дерево (e). Теперь при следующем включении потерять сбалансированность может лишь узел 5. Действительно, включение узла 6 должно привести к четвертому виду балансировки: двукратному повороту направо и налево (RL). Окончательное дерево показано на рис.6.35 (а-f).

Рис. 6.35 Последовательное включение узлов в сбалансированное дерево.

АЛГОРИТМ Insert_&_Balanse включения узла в сбалансированное дерево.

Дано: сбалансированное бинарное дерево с корнем ROOT.

Поля: LPTR, RPTR, KEY (ключ), BAL (показатель сбалансированности), DATA (информация).

Заданы переменные: ключ - х, информация - INF.

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

Переменная h используется как флаг, указывающий на то, что было произведено включение элемента. P - текущий указатель при перемещении по дереву, p1 и p2 - вспомогательные указатели. Count - счетчик вставленных элементов.

_Начало . Insert_&_Balanse: 1. Поиск места для вставки: _Если . x < KEY(p) _то .: _если . p=nil _то .: ВСТАВИТЬ_ЭЛЕМЕНТ и перейти к п. 3; _иначе .: p=LPTR(p) и перейти к п. 1; повторный вызов Insert_&_Balanse; _Если . x > KEY(p) _то .: _если . p=nil _то .: ВСТАВИТЬ_ЭЛЕМЕНТ и перейти к п. 5; _иначе .: p=RPTR(p) и перейти к п. 1; повторный вызов Insert_&_Balanse; 2. Совпадение: Напечатать "Элемент уже вставлен" и _конец .. 3. Изменение показателей сбалансированности: (производилась вставка в левое поддерево) _если . BAL(p)=1 _то .: BAL(p)=0; h=false; { перевеш.-> сбалансир.} перейти к п. 7 _если . BAL(p)=0 _то . BAL(p)=-1; { перевеш.-> критическ.} перейти к п. 7 4. Балансировка при возрастании левого поддерева: _если . p=ROOT _то . ROOT=LPTR(p); { перенос корневой вершины } p1=LPTR(); { вводим дополнительный указатель } _если . BAL(p1)=-1 _то .: { однокр. LL-поворот } LPTR(p)=RPTR(p1); RPTR(p1)=p; BAL(p)=0; p=p1; перейти к п. 7 _иначе .: { двукратн. LR-поворот } _если . p1=ROOT _то . ROOT=RPTR(p1); { перенос корневой вершины } p2:=RPTR(p1); RPTR(p1)=LPTR(p2); LPTR(p1)=p1; LPTR(p)=RPTR(p2); RPTR(p2)=p; (изменение показателей сбалансированности ) _если . BAL(p2)=-1 _то . BAL(p)=1 _иначе . BAL(p)=0; _если . BAL(p2)=1 _то . BAL(p1)=-1 _иначе . BAL(p1)=0; p=p2; BAL(p)=0; h=false; перейти к п. 7; 5. Изменение показателей сбалансированности: (производилась вставка в правое поддерево) _если . BAL(p)=-1 _то .: BAL(p)=0; h=false; { перевеш.-> сбалансир.} перейти к п. 7 _если . BAL(p)=0 _то BAL(p)=1; { перевеш.-> критическ.} перейти к п. 7 6. Балансировка при возрастании правого поддерева: _если . p=ROOT _то . ROOT=RPTR(p); { перенос корневой вершины } p1=RPTR(p); { вводим дополнительный указатель } _если . BAL(p1)=1 _то .: { однокр. RR-поворот } RPTR(p)=LPTR(p1); LPTR(p1)=p; BAL(p)=0; p=p1; перейти к п. 7 _иначе .: { двукратн. LR-поворот } _если . p1=ROOT _то . ROOT=LPTR(p1); { перенос корневой вершины } p2:=LPTR(p1); LPTR(p1)=RPTR(p2); RPTR(p1)=p1; RPTR(p)=LPTR(p2); LPTR(p2)=p; (изменение показателей сбалансированности ) _если . BAL(p2)=1 _то . BAL(p)=-1 _иначе . BAL(p)=0; _если . BAL(p2)=-1 _то . BAL(p1)=1 _иначе . BAL(p1)=0; p=p2; BAL(p)=0; h=false; 7. Выход. (Т.к. процедура осуществляет рекурсивный вызов самой себя в п.3, то здесь производится возврат в место предыдущего вызова. Последний выход осуществляется в вызывающую программу). _Конец . Insert_&_Balanse. 8. Алгоритм процедуры ВСТАВИТЬ_ЭЛЕМЕНТ: _Начало .: LPTR(p)=nil; RPT(p)=nil; BAL=0; { обнуление указателей } DATA=INF; KEY=x; { занесение информации } h=true; { установка флага вставки элемента } _если . count=0 { это первый элемент ? } _то . ROOT=p; count=count+1; _Конец ..

Описание работы:

· П.1 - осуществляется поиск места для вставки элемента. Производится последовательный рекурсивный вызов процедурой самой себя. При нахождении места для вставки к дереву добавляется новый элемент с помощью процедуры ВСТАВИТЬ_ЭЛЕМЕНТ.

· П.2 - Если такой элемент уже существует в дереве, то выводится сообщение об этом и выполнение процедуры завершается.

· П.3 (П.5) - производит изменение показателей сбалансированности после включения нового элемента в левое (правое для П.5) поддерево.

· П.4 (П.6) - производит балансировку дерева путем перестановки указателей - т.е. LL- и LR-повороты (RR- и RL-повороты в П.6)

· П.7 - с помощью рекурсивных вызовов в стеке запоминается весь путь до места создания новой вершины. В П.7 производится обратный обход дерева, корректировка всех изменившихся показателей сбалансированности (в П. 3 и 5) и при необходимости балансировка. Это позволяет производить правильную балансировку, даже если критическая вершина находится далеко то места вставки.

ТЕКСТ ПРОЦЕДУРЫ Insert_&_Balanse.

Процедура выполняет действия по вставка элемента в бинарное дерево с последующей балансировкой в соответствии с приведенным выше алгоритмом.


Воспользуйтесь поиском по сайту:



©2015- 2022 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7