Самостоятельная работа №2: авл-деревья: Балансировка дерева, поиск и вставка элемента Работу



Скачать 106.5 Kb.
Дата12.04.2019
Размер106.5 Kb.
#81274
ТипСамостоятельная работа

Тартуский Университет

Факультет математики и информатики

Институт вычислительной науки


Алгоритмы и структуры данных


Самостоятельная работа №2:

АВЛ–деревья:

Балансировка дерева, поиск и вставка элемента



Работу выполнил:

Студент 1.курса Тартуского Университета

по специальности Информатика

Константин Третьяков (kt@ut.ee)



Руководитель: Айн Изотамм

Тарту, осень 2001 г.



Постановка задачи:

Реализация алгоритмов поиска элемента в сбалансированном по высоте двоичном дереве (АВЛ), вставки нового элемента и балансировки дерева после добавления элемента.


Алгоритмы:
Представление АВЛ-дерева в памяти

Для представления АВЛ-дерева в памяти компьютера используется структура, типичная для всех двоичных деревьев. Это запись (record) с несколькими полями:


TAVLTree = record

Data:Integer;

Subtree:array[0..1] of PAVLTree;

Balance:Integer;

end;
Поле Data содержит данные, хранящиеся в корневом узле дерева (в данном случае это просто целое число). Мы будем говорить, что узел А больше (меньше / равен) узла Б, если A.Data > (< / =) B.Data. Поле Subtree – это массив из двух указателей на левое и правое поддеревья (PAVLTree = ^TAVLTree), а в поле Balance хранится разность высот правого и левого поддеревьев (значение, необходимое при балансировке дерева).
Поиск элемента

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


function Search(T:PAVLTree; k:Integer):Boolean;

begin


while (T <> nil) and (T^.Data <> k) do begin

if k < T^.Data then T := T^.Subtree[LEFT]

else T := T^.Subtree[RIGHT];

end;


Search := (T <> nil);

end;
(Т.к. никаких реальных данных с узлом дерева в данной реализации не связано, то этот алгоритм просто определяет, есть ли узел с определённым значением в дереве или нет.)


Балансировка дерева

Основное свойство АВЛ-дерева – сбалансированность по высоте. Для любого узла разница высот поддеревьев не должна превышать 1. После добавления или удаления элемента свойство сбалансированности может нарушиться. Для восстановления баланса в таком случае необходимо проделать т.н. «поворот».

Например, в случае, если правое поддерево какого-либо узла стало «слишком большим», то проделывается «левый поворот»:

(рис.1)

В указанном примере у узла b правое поддерево выше левого. Если левое поддерево узла b выше правого, то для балансировки необходимо проделать т.н. «двукратный поворот»:



(рис.2)

Видно, что приведённый на рисунке двукратный левый поворот состоит из правого поворота в узле b и затем – левого поворота в узле a.

Для того чтобы иметь возможность определить момент, когда необходимо совершить перебалансировку, в каждом узле имеется поле Balance, которое содержит величину разницы высот правого и левого поддеревьев. К примеру, если высота левого поддерева на 1 больше высоты правого поддерева какого-либо узла, то в поле Balance этого узла будет храниться значение –1. Это значение обновляется при необходимости во время добавления или удаления элементов (см. Добавление элемента). Как только баланс узла достигает 2 или –2 вызывается процедура Rebalance, в которой определяется, какой тип поворота необходимо проделать для восстановления баланса:
function Rebalance(var T:PAVLTree):Boolean;

begin


Rebalance := True;

if T^.Balance = 2 then begin


{Левое поддерево слишком большое, необходим правый поворот}

if T^.Subtree[RIGHT]^.Balance = -1

then RotateTwice(T, LEFT)

else RotateOnce(T, LEFT);

end else if T^.Balance = -2 then begin
{Правое поддерево слишком большое, необходим левый поворот}

if T^.Subtree[LEFT]^.Balance = 1

then RotateTwice(T,RIGHT)

else RotateOnce(T,RIGHT);


end else Rebalance := False;

end;
Функция возвращает значение True, если какой-либо поворот был произведён и в результате высота дерева (в котором был произведён поворот) уменьшилась. Саму процедуру балансировки осуществляют функции RotateOnce и RotateTwice, описание которых и последует далее.


Поворот и двукратный поворот

Для совершения любого поворота необходимо: во-первых - переставить соответствующим образом узлы дерева, во-вторых – обновить значения поля Balance в этих узлах, и в-третьих - определить, уменьшилась ли высота дерева после этой процедуры. Первый пункт достаточно тривиален, третий тоже не представляет особых проблем, если мы никогда не удаляем элементы из дерева (легко заметить что в этом случае любой поворот всегда уменьшает высоту дерева). Осталось рассмотреть как изменяются балансы узлов:

Простой левый поворот (см. рис. 1). Обозначим за A0 и B0 значения поля Balance в узлах a и b до поворота, а за A1 и B1 – после поворота. Очевидно, что

A0 = 2 а B0 = 1 т.к. в случае B0 = -1 был бы произведён двукратный поворот вместо простого. Предположим, что возможен вариант B0 = 0. В нашем случае элементы из дерева не удаляются, а после добавления нового элемента может увеличиться высота только одного из двух поддеревьев b. Таким образом, B0 = 0 означает, что до вставки элемента дерево a было не сбалансировано, а этого быть не может. Итак, A0 = 2, B0 = 1. В таком случае после поворота мы получим балансы A1 = 0, B1 = 0. Ситуация аналогична при правом повороте. Итак – вот код процедуры RotateOnce:
procedure RotateOnce(var T:PAVLTree; Dir:Byte);

var OtherDir:Byte; OldRoot:PAVLTree;

begin

OtherDir := 1 - Dir;



{Произвести поворот}

OldRoot := T;

T := T^.Subtree[OtherDir];

OldRoot^.Subtree[OtherDir] := T^.Subtree[Dir];

T^.Subtree[Dir] := OldRoot;

{Обновить баланс}

T^.Balance := 0;

OldRoot^.Balance := 0;

end;
Для указания направления поворота процедуре передаётся параметр Dir, равный 0 при левом повороте или 1 – при правом. В программе также используются константы LEFT = 0 и RIGHT = 1 для указания левого или правого поддеревьев. Зная одно из направлений, второе можно легко найти, по формулам LEFT = 1 – RIGHT и RIGHT = 1 – LEFT. В этом и заключается смысл первой строки процедуры.



Теперь рассмотрим подсчёт балансов для двукратного поворота (см. рис. 2). Как и в предыдущем случае, обозначим за A
0, B0 и C0 значения поля Balance в узлах a, b и c до поворота, а за A1, B1 и C1 – после поворота. При левом повороте есть три возможности:


  1. A0 = 2, B0 = -1, C0 = -1, тогда A1 = 0, B1 = 1, C1 = 0

  2. A0 = 2, B0 = -1, C0 = 0, тогда A1 = 0, B1 = 0, C1 = 0*

  3. A0 = 2, B0 = -1, C0 = 1, тогда A1 = -1, B1 = 0, C1 = 0

Это можно записать следующим образом:


A1 = – Max (C0 , 0)

B1 = – Min (C0 , 0)

C1 = 0
При двукратном правом повороте имеются те же самые варианты, что и при левом, но с противоположными знаками. (Иллюстрация в случае правого поворота – зеркальное отражение рис. 2).

Таким образом, для правого поворота получаем:


A1 = – Min (C0 , 0)

B1 = – Max (C0 , 0)

C1 = 0

При обоих поворотах узел c становится новым корнем дерева вместо a. Далее, при левом повороте узел a становится новым левым поддеревом c а при правом – новым правым поддеревом с. И наоборот, узел b в случае левого поворота становится правым поддеревом с, а в случае правого поворота – левым. С учётом этого можно привести выведенные формулы к более простому виду:


Баланс нового левого поддерева с = – Max (C0 , 0)

Баланс нового правого поддерева с = – Min (C0 , 0)

Баланс нового корня (C1) = 0

Больше для написания процедуры двукратного поворота RotateTwice ничего не нужно.

procedure RotateTwice(var T:PAVLTree; Dir:Byte);

var OtherDir:Byte; OldRoot:PAVLTree; OtherDirSubtree:PAVLTree;

begin

OtherDir := 1-Dir;



OldRoot := T;

OtherDirSubtree := T^.Subtree[OtherDir];



{Переставить указатели}

T := OtherDirSubtree^.Subtree[Dir];

OtherDirSubtree^.Subtree[Dir] := T^.Subtree[OtherDir];

T^.Subtree[OtherDir] := OtherDirSubtree;

OldRoot^.Subtree[OtherDir] := T^.Subtree[Dir];

T^.Subtree[Dir] := OldRoot;



{Обновить баланс}

T^.Subtree[LEFT]^.Balance := -Max(T^.Balance, 0);

T^.Subtree[RIGHT]^.Balance := -Min(T^.Balance, 0);

T^.Balance := 0;

end;
Добавление элемента

Вставка элемента осуществляется следующей рекурсивной функцией (которая возвращает True, если после добавления элемента в дерево высота дерева изменилась):


function Insert(var T:PAVLTree; k:Integer):Boolean;

var HChange:Boolean; WhatSubtree:Byte;

begin
{Если такой элемент уже есть в дереве, ничего не делать и вернуть False}

Insert := False;


if T = nil then begin
{Нашли место для вставки, добавить новый узел, вернуть True т.к. высота

дерева увеличилась}

New(T);


FillChar(T^, SizeOf(T^), #0);

T^.Data := k;

Insert:=True;

end else if T^.Data <> k then begin


{Вставить элемент в правильное поддерево}

if k < T^.Data then WhatSubtree := LEFT

else WhatSubtree := RIGHT;

HChange:=Insert(T^.Subtree[WhatSubtree], k);


{Если высота поддерева изменилась, то может быть нужна балансировка}

if HChange then begin


{Изменить значение баланса}

If WhatSubtree = LEFT then Dec(T^.Balance)

else Inc(T^.Balance);
{Если баланс стал равным 0, то высота не изменилась, иначе, изменение

высоты зависит от того, сделана ли балансировка}

if T^.Balance<>0 then

Insert := not Rebalance(T)

end;


end;

end;


Процедура находит место для вставки, добавляет элемент, и, «возвращаясь из рекурсии», обновляет значение поля Balance и вызывает процедуру Rebalance там, где это необходимо.
Использованная литература:

1. AVL Trees: Tutorial and C++ implementation, Brad Appleton (http://www.enteract.com/~bradapp/ftp/src/libs/C++/AvlTrees.html)

2. Algoritmid ja Andmestruktuurid, Jüri Kiho, Tartu 1997.

Исходный код программы: (файлы AVLTREE.PAS и AVLTEST.PAS)




unit AVLTree;



{The unit, containing procedures that handle AVL trees,

A lot of comments is removed to save paper.
Copyright 2001, Konstantin Tretyakov}
interface

uses Crt {for AVLPrintTree};


const

LEFT = 0;

RIGHT = 1;
type

PAVLTree = ^TAVLTree;

TAVLTree = record

Data:Integer;

Subtree:array[0..1] of PAVLTree;

Balance:Integer;

end;
{---------------Procedures and functions-------------------}
procedure AVLPrintTree(T:PAVLTree; col,lbound,rbound:Byte; lev:Integer);

function AVLSearch(T:PAVLTree; k:Integer):Boolean;

function AVLInsert(var T:PAVLTree; k:Integer):Boolean;

function AVLRebalance(var T:PAVLTree):Boolean;

procedure AVLDeleteTree(var T:PAVLTree);

procedure AVLRotateOnce(var T:PAVLTree; Dir:Byte);

procedure AVLRotateTwice(var T:PAVLTree; Dir:Byte);
implementation
{------------------Min and Max functions--------------}
function Min(A,B:Integer):Integer;

begin


if Aend;
function Max(A,B:Integer):Integer;

begin

if A>B then Max:=A else Max:=B;



end;
{--------------------AVLPrintTree---------------------}

{Outputs a tree to the screen by traversing it in preorder

It is really far from being perfect, but its sufficient

for this project}
procedure AVLPrintTree(T:PAVLTree; col,lbound,rbound:Byte; lev:Integer);

begin


if lev=0 then begin

ClrScr;


WriteLn('Current Tree:');

col:=2;


end;

if T=nil then begin

if lev=0 then begin

GotoXY((lbound+rbound) div 2 - 4, col);

WriteLn('EMPTY');

end else begin

GotoXY((lbound+rbound) div 2 - 1, col);

WriteLn(#1);

end;

end else begin



GotoXY((lbound+rbound) div 2 - 1, col);

WriteLn(T^.Data:2);

AVLPrintTree(T^.Subtree[LEFT], col + 2,

lbound, (lbound+rbound) div 2, lev + 1);

AVLPrintTree(T^.Subtree[RIGHT],col + 2,

(lbound+rbound) div 2 + 1, rbound, lev + 1);

end;

end;
{-----------------------AVLSearch---------------------}



{Returns True if a given value exists in the tree.

Performs a simple binary search}


function AVLSearch(T:PAVLTree; k:Integer):Boolean;

begin


while (T<>nil) and (T^.Data<>k) do begin

if k < T^.Data then T:=T^.Subtree[LEFT]

else T:=T^.Subtree[RIGHT];

end;


AVLSearch:=(T<>nil);

end;
{----------------------AVLInsert----------------------}



{Searches recursively for the place to insert the

element, inserts it and automatically balances

the tree if a disbalance occured.}
function AVLInsert(var T:PAVLTree; k:Integer):Boolean;

var HChange:Boolean; WhatSubtree:Byte;

begin

AVLInsert := False;



if T = nil then begin

{Found a place to insert element}

New(T);


FillChar(T^, SizeOf(T^), #0);

T^.Data := k;

AVLInsert:=True;

end else if T^.Data <> k then begin



{Insert into the right subtree}

if k < T^.Data then WhatSubtree := LEFT

else WhatSubtree := RIGHT;

HChange:=AVLInsert(T^.Subtree[WhatSubtree], k);



{Check for disbalance, in case the height of a subtree changed}

if HChange then begin



{Update balance}

If WhatSubtree = LEFT then Dec(T^.Balance)

else Inc(T^.Balance);

{No height change if the balance became 0}

if T^.Balance<>0 then

AVLInsert := not AVLRebalance(T)

end;


end;

end;
{---------------------AVLRebalance--------------------}



{Decides what balancing operation to perform}
function AVLRebalance(var T:PAVLTree):Boolean;

begin


{As far as we don’t mess with item removal, any rotation decreases the height}

AVLRebalance := True;

if T^.Balance = 2 then begin

{Left subtree too heavy, need a right rotation}

if T^.Subtree[RIGHT]^.Balance = -1

then AVLRotateTwice(T, LEFT)

else AVLRotateOnce(T, LEFT);

end else if T^.Balance = -2 then begin

{Right subtree too heavy, need a left rotation}

if T^.Subtree[LEFT]^.Balance = 1

then AVLRotateTwice(T,RIGHT)

else AVLRotateOnce(T,RIGHT);

end else AVLRebalance := False;

end;


{--------------------AVLRotateOnce--------------------}

{Performs a single rotation in the given direction}
procedure AVLRotateOnce(var T:PAVLTree; Dir:Byte);

var OtherDir:Byte; OldRoot:PAVLTree;

begin

OtherDir := 1 - Dir;



{Perform the rotation (swap pointers)}

OldRoot := T;

T := T^.Subtree[OtherDir];

OldRoot^.Subtree[OtherDir] := T^.Subtree[Dir];

T^.Subtree[Dir] := OldRoot;

{Update balances}

T^.Balance := 0; OldRoot^.Balance := 0;

end;
{--------------------AVLRotateTwice--------------------}

{Performs a double rotation in the given direction}

procedure AVLRotateTwice(var T:PAVLTree; Dir:Byte);

var OtherDir:Byte; OldRoot:PAVLTree; OtherDirSubtree:PAVLTree;

begin


OtherDir := 1-Dir;

OldRoot := T;

OtherDirSubtree := T^.Subtree[OtherDir];

{Perform rotation (swap pointers)}

T := OtherDirSubtree^.Subtree[Dir];

OtherDirSubtree^.Subtree[Dir] := T^.Subtree[OtherDir];

T^.Subtree[OtherDir] := OtherDirSubtree;

OldRoot^.Subtree[OtherDir] := T^.Subtree[Dir];

T^.Subtree[Dir] := OldRoot;



{Update balance}

T^.Subtree[LEFT]^.Balance := -Max(T^.Balance, 0);

T^.Subtree[RIGHT]^.Balance := -Min(T^.Balance, 0);

T^.Balance := 0;

end;
{---------------------AVLDeleteTree--------------------}

{The procedure recurses on the tree removing all the

subnodes and freeing the allocated memory}
procedure AVLDeleteTree(var T:PAVLTree);

begin


if T=nil then Exit;

AVLDeleteTree(T^.Subtree[LEFT]); AVLDeleteTree(T^.Subtree[RIGHT]);

Dispose(T); T:=nil;

end;


end.


program AVLTest;

uses AVLTree, Crt;

{The program demonstrates the usage of the AVLTree unit}

{Copyright 2001, Konstantin Tretyakov}
var k:Integer; T:PAVLTree;

begin


T:=nil; k:=10;

while k<>0 do begin

if (Abs(k)>=100) or (k<0) then begin

WriteLn('Wrong argument!');

ReadKey;

end else AVLInsert(T, k);

AVLPrintTree(T, 1, 1, 80, 0);

GotoXY(1,15);

Write('Please enter a positive integer < 100 to add to the ');

WriteLn('tree' + #13#10 + 'Enter 0 to quit');

Write('Your choice: ');

ReadLn(k);

end;

AVLDeleteTree(T);



WriteLn('Bye!’ + #13#10 + 'Copyright(c) 2001, Konstantin Tretyakov');

end.


Приложение: Пример хода выполнения программы


Current Tree:

10
☺ ☺

Please enter a positive integer < 100 to add to the tree

Enter 0 to quit

Your choice: 5



Current Tree:

10
5 ☺
☺ ☺
Please enter a positive integer < 100 to add to the tree

Enter 0 to quit

Your choice: 15

Current Tree:

10
5 15
☺ ☺ ☺ ☺
Please enter a positive integer < 100 to add to the tree

Enter 0 to quit

Your choice: 7

Current Tree:

10
5 15
☺ 7 ☺ ☺
☺ ☺

Please enter a positive integer < 100 to add to the tree

Enter 0 to quit

Your choice: 6



Current Tree:

10
6 15
5 7 ☺ ☺
☺ ☺ ☺ ☺

Please enter a positive integer < 100 to add to the tree

Enter 0 to quit

Your choice: 8



Current Tree:

7
6 10
5 ☺ 8 15
☺ ☺ ☺ ☺ ☺ ☺

Please enter a positive integer < 100 to add to the tree

Enter 0 to quit

Your choice: 12



Current Tree:

7
6 10
5 ☺ 8 15
☺ ☺ ☺ ☺ 12 ☺
☺ ☺
Please enter a positive integer < 100 to add to the tree

Enter 0 to quit

Your choice: 11

Current Tree:

7
6 10
5 ☺ 8 12
☺ ☺ ☺ ☺ 11 15
☺ ☺ ☺ ☺
Please enter a positive integer < 100 to add to the tree

Enter 0 to quit

Your choice: 13

Current Tree:

7
6 12
5 ☺ 10 15
☺ ☺ 8 11 13 ☺
☺ ☺ ☺ ☺ ☺ ☺
Please enter a positive integer < 100 to add to the tree

Enter 0 to quit

Your choice: 9

Current Tree:

10
7 12
6 8 11 15
5 ☺ ☺ 9 ☺ ☺ 13 ☺
☺ ☺ ☺ ☺ ☺ ☺
Please enter a positive integer < 100 to add to the tree

Enter 0 to quit

Your choice: 14

Current Tree:

10
7 12
6 8 11 14
5 ☺ ☺ 9 ☺ ☺ 13 15
☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
Please enter a positive integer < 100 to add to the tree

Enter 0 to quit

Your choice: 1

Current Tree:

10
7 12
5 8 11 14
1 6 ☺ 9 ☺ ☺ 13 15
☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺

Please enter a positive integer < 100 to add to the tree

Enter 0 to quit

Your choice: 2



Current Tree:

10
7 12
5 8 11 14
1 6 ☺ 9 ☺ ☺ 13 15
☺ 2 ☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺

Please enter a positive integer < 100 to add to the tree

Enter 0 to quit

Your choice: 3



Current Tree:

10
7 12
5 8 11 14
2 6 ☺ 9 ☺ ☺ 13 15
1 3 ☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺

Please enter a positive integer < 100 to add to the tree

Enter 0 to quit

Your choice: 4



Current Tree:

10
7 12
3 8 11 14
2 5 ☺ 9 ☺ ☺ 13 15
1 ☺ 4 6 ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺

Please enter a positive integer < 100 to add to the tree

Enter 0 to quit

Your choice: 0



* Этот вариант, кстати, невозможен в случае, когда мы не удаляем элементы из дерева


Скачать 106.5 Kb.

Поделитесь с Вашими друзьями:




База данных защищена авторским правом ©vossta.ru 2022
обратиться к администрации

    Главная страница