Самостоятельная работа №2: авл-деревья: Балансировка дерева, поиск и вставка элемента Работу
Скачать 106.5 Kb.
|
- Навигация по данной странице:
- АВЛ–деревья
|
Тартуский Университет Факультет математики и информатики Институт вычислительной науки
Алгоритмы и структуры данныхСамостоятельная работа №2: АВЛ–деревья:Балансировка дерева, поиск и вставка элементаРаботу выполнил: Студент 1.курса Тартуского Университета по специальности Информатика Константин Третьяков (kt@ut.ee) Руководитель: Айн Изотамм Тарту, осень 2001 г. Постановка задачи: Реализация алгоритмов поиска элемента в сбалансированном по высоте двоичном дереве (АВЛ), вставки нового элемента и балансировки дерева после добавления элемента. Алгоритмы: Представление АВЛ-дерева в памяти Для представления АВЛ-дерева в памяти компьютера используется структура, типичная для всех двоичных деревьев. Это запись (record) с несколькими полями: TAVLTree = record Data:Integer; Subtree:array[0..1] of PAVLTree; Balance:Integer; end;
АВЛ-дерево – это бинарное дерево поиска. В нём все элементы меньшие корня хранятся в левом поддереве, а все элементы большие корня – в правом. Причем оба поддерева обладают тем же свойством. Это позволяет довольно быстро находить требуемый элемент с помощью следующего простого алгоритма: 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. После добавления или удаления элемента свойство сбалансированности может нарушиться. Для восстановления баланса в таком случае необходимо проделать т.н. «поворот». Например, в случае, если правое поддерево какого-либо узла стало «слишком большим», то проделывается «левый поворот»:
В указанном примере у узла b правое поддерево выше левого. Если левое поддерево узла b выше правого, то для балансировки необходимо проделать т.н. «двукратный поворот»:  (рис.2)
Видно, что приведённый на рисунке двукратный левый поворот состоит из правого поворота в узле b и затем – левого поворота в узле a. Для того чтобы иметь возможность определить момент, когда необходимо совершить перебалансировку, в каждом узле имеется поле Balance, которое содержит величину разницы высот правого и левого поддеревьев. К примеру, если высота левого поддерева на 1 больше высоты правого поддерева какого-либо узла, то в поле Balance этого узла будет храниться значение –1. Это значение обновляется при необходимости во время добавления или удаления элементов (см. Добавление элемента). Как только баланс узла достигает 2 или –2 вызывается процедура Rebalance, в которой определяется, какой тип поворота необходимо проделать для восстановления баланса:
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;
Поворот и двукратный поворот Для совершения любого поворота необходимо: во-первых - переставить соответствующим образом узлы дерева, во-вторых – обновить значения поля Balance в этих узлах, и в-третьих - определить, уменьшилась ли высота дерева после этой процедуры. Первый пункт достаточно тривиален, третий тоже не представляет особых проблем, если мы никогда не удаляем элементы из дерева (легко заметить что в этом случае любой поворот всегда уменьшает высоту дерева). Осталось рассмотреть как изменяются балансы узлов: Простой левый поворот (см. рис. 1). Обозначим за A0 и B0 значения поля Balance в узлах a и b до поворота, а за A1 и B1 – после поворота. Очевидно, что
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;
Теперь рассмотрим подсчёт балансов для двукратного поворота (см. рис. 2). Как и в предыдущем случае, обозначим за A0, B0 и C0 значения поля Balance в узлах a, b и c до поворота, а за A1, B1 и C1 – после поворота. При левом повороте есть три возможности:
Это можно записать следующим образом: 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
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);
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;
PAVLTree = ^TAVLTree; TAVLTree = record Data:Integer; Subtree:array[0..1] of PAVLTree; Balance:Integer; end;
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);
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;
{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;
{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);
if T^.Balance<>0 then AVLInsert := not AVLRebalance(T) end;
end; end;
{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
if T^.Subtree[RIGHT]^.Balance = -1 then AVLRotateTwice(T, LEFT) else AVLRotateOnce(T, LEFT); end else if T^.Balance = -2 then begin
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;
T^.Balance := 0; OldRoot^.Balance := 0; end;
procedure AVLRotateTwice(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; {Update balance} T^.Subtree[LEFT]^.Balance := -Max(T^.Balance, 0); T^.Subtree[RIGHT]^.Balance := -Min(T^.Balance, 0); T^.Balance := 0; end;
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;
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
Enter 0 to quit Your choice: 15
Current Tree: 10
Enter 0 to quit Your choice: 7
Current Tree: 10
Please enter a positive integer < 100 to add to the tree Enter 0 to quit Your choice: 6
Current Tree: 10
Please enter a positive integer < 100 to add to the tree Enter 0 to quit Your choice: 8
Current Tree: 7
Please enter a positive integer < 100 to add to the tree Enter 0 to quit Your choice: 12
Current Tree: 7
Enter 0 to quit Your choice: 11
Current Tree: 7
Enter 0 to quit Your choice: 13
Current Tree: 7
Enter 0 to quit Your choice: 9
Current Tree: 10
Enter 0 to quit Your choice: 14 Current Tree: 10
Enter 0 to quit Your choice: 1
Current Tree: 10
Please enter a positive integer < 100 to add to the tree Enter 0 to quit Your choice: 2
Current Tree: 10
Please enter a positive integer < 100 to add to the tree Enter 0 to quit Your choice: 3
Current Tree: 10
Please enter a positive integer < 100 to add to the tree Enter 0 to quit Your choice: 4
Current Tree: 10
Please enter a positive integer < 100 to add to the tree Enter 0 to quit Your choice: 0 * Этот вариант, кстати, невозможен в случае, когда мы не удаляем элементы из дерева Каталог: a&a a&a -> Правила: Ось и Союзники Европа 1940 компоненты игры краткое содержание игры… как выигрывают войну… начальная расстановка… политическая ситуация… порядок игры… Скачать 106.5 Kb. Поделитесь с Вашими друзьями:
|
(рис.1)