Информатика и выч. техника \ Структуры и алгоритмы обработки данных

Сбалансированные бинарные деревья. Включение вершины в сбалансированное дерево поиска, страница 2

3

в)               8                                     6

         4               10       Þ            4             8

   2            6                         2           5             10

5

г)                8                                    6

          4             10        Þ            4             8

    2           6                          2            7          10

7

Рисунок 3.

В первом случае проблема решается за счет превращения корня поддерева А в корень дерева с соответствующим изменением связей       (LL-поворот). Во втором случае используется структура дерева А, и в качестве корня дерева выбирается корень правого поддерева корневой вершины А (LR-поворот). Это иллюстрируется соответственно рис.4 и рис.5. Во втором случае вершина С правого поддерева дерева А становится корнем, а вершина дерева А подчиняет левое поддерево вершины С.

                R                                  A

          A                                                R

 


                     III         Þ            I

I      II

 k-1                                                    II     III

 k                                       k

 k+1

Рисунок 4. LL поворот

                   R                                  C

            A                                 A              R

                 C

                          IV       Þ

       I

k-1         II    III                    I      II      III     IV

 k

 k+1

 


Рисунок 5. LR поворот

Алгоритм включения и балансировки существенно зависит от того, каким образом хранится информация о сбалансированности дерева. Крайнее решение – хранить эту информацию полностью неявно. Однако в этом случае сбалансированность для узла требуется определять всегда, когда включение затрагивает узел. Другая крайность: хранение показателя сбалансированности в каждой вершине:

Type Ptr=^retro;

Retro=record

Key:integer;

Info:string;

Bal: integer;    

Lp:Ptr;

Rp:Ptr

End;

Здесь показатель сбалансированности bal – разность между глубиной правого и левого поддерева данной вершины. Процесс включения вершины состоит фактически из трех последовательных этапов:

Этап 1. Проход по пути поиска, если такого ключа нет, то выполнение этапа 2;

Этап 2. Включение новой вершины и определение результирующего показателя сбалансированности.

Этап 3. Отступление по пути поиска (возможно, с балансировкой).

Таким образом, процедура включения вершины в сбалансированное дерево является некоторым обобщением процедуры включения в дерево поиска. В силу рекурсивности последней её легко приспособить для выполнения дополнительных действий при возврате вдоль пути поиска. Информацию, которую нужно передать на каждом шаге, указывает, увеличилась ли глубина поддерева, где произошло включение. Так что соответствующая процедура имеет три параметра:

ADD (X:INTEGER; VAR P:PTR; VAR B:BOOLEAN).

Здесь В указывает на увеличение глубины дерева.

Пусть теперь процесс из левой ветви возвращается к вершине р, причем указывается, что глубина соответствующего поддерева увеличилась. В зависимости от высоты поддеревьев перед включением мы должны различать три возможных ситуации:

-  предыдущая несбалансированность ликвидируется, если p^.bal=1;

-  сбалансированность сохраняется, если p^.bal=0;

-  сбалансированность нарушена, требуется балансировка, если p^.bal=1.

В третьем случае по показателю сбалансированности левого поддерева, то есть pl^.bal, можно определить, к какому повороту нужно прибегать:

-  если Pl^.bal меньше нуля, то требуется LL-поворот;

-  если pl^.bal больше нуля, требуется LR-поворот.

Операция балансировки состоит только из последовательных переприсваиваний ссылок. Фактически ссылки циклически меняются местами, что приводит к одно- или двукратному повороту двух или трех участвующих в процессе верщин. Кроме «вращения» ссылок нужно должным образом направлять показатели сбалансированности соответствующих вершин.

Блок-схема алгоритма включения вершин с балансировкой представлена на рис.6.

Структура записи для вершины дерева:

key

inf

lp

rp

bal – показатель сбалансиров.
Скачать файл