WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Структури даних - Реферат

Структури даних - Реферат

TreeStr.PrintLR;
begin
PLR (TTree);
writeln;
end;
function FindEl (var Tree: PTree; Value:integer):boolean;
begin
if (Tree = NIL) then FindEl := FALSE else
if (Tree^.Val = Value) then FindEl := TRUE else
if (Value < Tree^.Val) then FindEl := FindEl (Tree^.Left, Value)
else FindEl := FindEl (Tree^.Right, Value);
end;
function TreeStr.Find (Value:integer):boolean;
begin
Find := FindEl (TTree, Value);
end;
Мінімальний (максимальний) ключ в дереві можна знайти, якщо пройти по вказівникам Left (Right) від кореня поки не досягнемо вершини, лівий (правий) син якої дорівнює NIL. Процедура FindMin (FindMax) повертає вказівник на вершину, яка містить мінімальний (максимальний) ключ. Час виконання вказаних процедур дорівнює O(h), де h - висота дерева.
function FMax (Tree:PTree):PTree;
begin
if (Tree^.Right = NIL) then FMax := Tree
else FMax:= FMax (Tree^.Right);
end;
function TreeStr.FindMax:PTree;
begin
if TTree = NIL then FindMax := NIL
else FindMax := FMax (TTree);
end;
function Fmin (Tree:PTree):PTree;
begin
if (Tree^.Left = NIL) then FMin := Tree
else FMin:= FMin (Tree^.Left);
end;
function TreeStr.FindMin:PTree;
begin
if TTree = NIL then FindMin := NIL
else FindMin := FMin (TTree);
end;
У процедурі вставки Insert елемента Value в бінарне дерево Tree відбувається рух вниз по дереву від корня до листа. В кожній вершині x, яка не є листом, процедура обирає напрямок руху (вліво чи вправо) у відповідності до властивості впорядкованості: якщо Value < x.Val, то відбувається рух вліво, інакше - вправо. Дійшовши до листа z, процедура вставляє нову вершину w, ключ якої дорівнює Value знову ж таки за властивістю впорядкованості: якщо Value Tree^.Val) then
if Tree^.Right = NIL then
begin
New (Tree^.Right);
Tree^.Right^.val := Value;
Tree^.Right^.Left := NIL;
Tree^.Right^.Right := NIL;
Tree^.Right^.Up := Tree;
end
else InsElem (Tree^.Right, Value)
else
if Tree^.Left = NIL then
begin
New (Tree^.Left);
Tree^.Left^.val := Value;
Tree^.Left^.Left := NIL;
Tree^.Left^.Right := NIL;
Tree^.Left^.Up := Tree;
end
else InsElem (Tree^.Left, Value);
end;
procedure TreeStr.Insert (Value:integer);
var Tmp: PTree;
begin
InsElem (TTree, Value);
end;
При видаленні вершини х з бінарного дерева можливі три випадки:
* х не має синів - тоді достатньо розташувати NIL у відповідне поле його батька (замість х);
* х має одного сина - тоді його можна вирізати, поєднавши його батька напряму з цим сином;
* х має двох синів - необхідно знайти наступний за х елемент y (який вже не має лівого сина), скопіювати його ключ та певні дані з вершини y до вершини x, а саму вершину y видалити вище описаним способом.
procedure DelElem (var Tree: PTree; Value: integer);
var tmp, Repl: PTree;
begin
if (Tree = NIL) then Exit;
if (Value Tree^.Val) then DelElem (Tree^.Right, Value)
else if ((Tree^.Left NIL) and (Tree^.Right NIL)) then
begin
Repl := Fmin (Tree^.Right);
Tree^.Val := Repl^.Val;
DelElem (Tree^.Right, Repl^.Val);
end
else
begin
tmp := Tree;
if (Tree^.Left = NIL) then repl := Tree^.Right;
if (Tree^.Right = NIL) then repl := Tree^.Left;
Dispose (tmp);
Tree := Repl;
end;
end;
procedure TreeStr.Delete (Value:integer);
begin
DelElem (TTree, Value);
end;
Дерева з довільним розгалудженням можна перетворити у двійкове дерево за принципом "ліва дитина - правий сусід". Кожна вершина містить три вказівники:
вказівник p на батька;
вказівник left-child[x] на саму ліву дитину вершини х;
вказівник right-child[x] на найближчого сусіда вершини х;
Вершина х не має дітей тоді і тільки тоді коли left-child[x] = NIL. Вершина х є крайньою правою дитиною свого батька якщо right-child[x] = NIL.
AVL - деревом (Adelson-Velskii and Landis) називається бінарне дерево, яке має наступні властивості:
* висоти піддерев кожного батька відрізняються не більше ніж на 1:
* кожне піддерево батька є AVL - деревом.
AVL - дерева належать до класу збалансованих бінарних дерев.
Ліве дерево є AVL - деревом, оскільки у нього висота кожного лівого сина на 1 більша за висоту відповідного правого сина. Дерево, яке зображене справа, не є AVL - деревом, оскільки лівий син вершини 12 (дерево з коренем 8) має висоту 4, а правий син вершини 12 (дерево з коренем 18) має висоту 2.
Дерево відрізків - це структура даних, яка створена для роботи з такими інтервалами на числовій осі, кінці яких належать фіксованій множині з N абсцис (далі цими абсцисами будемо вважати цілі числа в інтервалі [1, N]). Оскільки множина абсцис фіксована, то дерево відрізків являє собою статичну структуру по відношенню до цих абсцис.
Дерево відрізків - це двійкове дерево з коренем. Для заданих цілих чисел l та r (l 1, то воно складається з лівого піддерева T(l, [(B[v] + E[v])/2]) та правого піддерева T([(B[v] + E[v])/2], r).
Інтервали, що належать множині {[B[v], E[v]]: v - вузел T(l, r)}, називаються стандартними інтервалами дерева T(l, r). Стандартні інтервали, які належать листам T(l, r), називаються елементарними інтервалами. T(l, r) збалансоване та має глибину log2(r - l) .
Дерево відрізків призначено для динамічного запам'ятання інтервалів, кінці яких належать множині {l, l + 1, ..., r}. Якщо r - l > 3, то інтервал [b, e] з цілими b < e буде розбито в набір не більш ніж log2 (r - l) + log2 (r - l) - 2 стандартних інтервалів дерева T(l, r).
Функція BuildTree ( l, r ) будує та повертає дерево відрізків T(l, r). Складний тип даних tree має структуру дерева, в якій left та right - вказівники на лівого та правого сина, begin та end - параметри вершини.
BuildTree ( l, r )
temp new tree;
begin [temp] l;
end [temp] r;
if (r - l < 2) then
begin
left[temp] NIL;
right[temp] NIL;
return temp;
end;
left[temp] BuildTree ( l, [(l + r) / 2] );
right[temp] BuildTree ( [(l + r) / 2], r );
return temp;
Фрагментація інтервала [b, e] повністю визначається операцією занесення [b, e] в дерево відрізків Т. До структури даних tree додамо булевий параметр flag, який буде відповідати за включення стандартного інтервалу до інтервалу [b, e]. Тобто якщо для деякої вершини v має місце flag[v] = TRUE, то [ begin[v], end[v] ] [b, e].
InsertTree ( b, e, T )
if (b begin[T] and end[T] e) then flag[T] =TRUE;
else
begin
if (b < begin[T] + end[T] ) / 2 ) then InsertTree ( b, e, left[T] )
if ( begin[T] + end[T] ) / 2 < e) then InsertTree ( b, e, right[T] )
end;
Наприклад, після занесення інтервала [5, 14] до дерева відрізків T(4,15) параметр flag у наступних стандартних інтервалах буде встановлено в істину:
[5, 6], [6, 9], [9, 12], [12, 13], [13, 14].
2-3 деревом називається дерево, в якому кожний вузол, який не є листом, має двох або трьох синів, а довжини всіх шляхів з кореня до листів однакові.
Позначимо через E[l] елемент даних,
Loading...

 
 

Цікаве