Структури даних

Реферат на тему:

Структури даних.

Означення. Опис складних об'єктів засобами більш простих типів даних, які безпосередньо представляються у машині, називається структурами даних.

Найпоширеними складними об'єктами є множини та послідовності (впорядковані множини).

Списком називається впорядкована послідовність елементів a1, a2, …, an. Розмір або довжина цього списку дорівнює n. Список розміру 0 називається порожнім. Список можна реалізувати або за допомогою масиву або за допомогою зв’язування його елементів вказівниками (зв'язаний список). У зв’язаному списку елементи лінійно впорядковані, їх порядок визначається вказівниками, що входять у склад елементів списка. Елемент двостороннього зв’язаного списка містить три поля: ключ та два вказівника — наступний та попередній. В односторонньому зв’язаному списку відсутнє поле ‘попередній'. У впорядкованому списку елементи розташовані в порядку зростання ключів на відміну від невпорядкованого списка.

Стеки та черги — це динамічні множини (або спеціальні типи списків), в яких елемент що додається, визначається структурою множини. Стек працює за принципом «останній прийшов — перший пішов (LIFO)», а черга — за принципом «перший прийшов — перший пішов (FIFO)».

Нехай PList — вказівник на однозв’язний список.

PList = ^List;

List = object.

val: integer; /* значення */.

next: PList; /* вказівник на наступний елемент списку */.

end;

Стек має наступні методи:

PUSH — покласти елемент до стеку;

POP — взяти верхній елемент зі стеку;

TOP — повернути верхній елемент стеку без його вилучення;

IsEmpty — перевірити, чи є стек порожнім;

PRINT — надрукувати елементи стеку.

Pstack — вказівник на об'єкт стек.

PStack = ^Stack;

Stack = object.

lst: PList;

procedure Push (Value: integer);

function Pop: integer;

function Top: integer;

function IsEmpty: boolean;

procedure Print;

end;

procedure Stack. Push (Value:integer);

var temp: PList;

begin.

New (temp);

temp^.val := Value;

temp^.next := lst;

lst := temp;

end;

function Stack. Pop: integer;

begin.

if (lst = NIL) then Pop := -1 else.

begin.

Pop := lst^.val;

lst := lst^.next;

end;

end;

function Stack. Top: integer;

begin.

Top := lst^.val;

end;

function Stack. IsEmpty: boolean;

begin.

if (lst = NIL) then IsEmpty := TRUE.

else IsEmpty := FALSE;

end;

procedure Stack. Print;

var tmp: PList;

begin.

tmp := lst;

while (tmp <> NIL) do.

begin.

write (tmp^.val); write («»);

tmp := tmp^.next;

end;

writeln;

end;

Орієнтованим графом називається структура G = (V, E), де V — скінченна множина вершин, E — множина ребер, що задається як бінарне відношення на V, тобто E xF0CDxF020V xF0B4xF020V. Орієнтований граф називається орграфом. Граф може містити ребра — цикли, які сполучають вершину саму з собою. Про ребро (u, v) говорять, що воно виходить із вершини u та входить у вершину v.

В неорієнтованому графі множина ребер E складається із невпорядкованих пар вершин. Про ребро (u, v) неорієнтованого графу говорять, що воно інцидентно вершинам u та v. Якщо в графі G є ребро (u, v), то говорять, що вершина u суміжна з вершиною v. Для неорієнтованого графу відношення суміжності є симетричним.

Степенем вершини в неорієнтованому графі називається кількість інцидентних їй ребер. Для орієнтовних графів розрізняють вхідну та вихідну вершини; сума вхідних та вихідних степеней називається степенем вершини.

Деревом називається зв’язаний граф без циклів. Дерево являє собою скінченну множину елементів Т, які називаються вершинами. Якщо множина вершин Т порожня, то дерево називається порожнім; інакше в дереві повинна бути виділена одна вершина, яка називається коренем (якщо виділеної вершини не існує, то така структура називається деревом без виділеного кореня). Якщо (y, x) є останнім ребром на шляху з кореня до х, то y називається батьком, а x — сином. Корінь є єдиною вершиною, яка не має батька. Вершини, які мають одного спільного батька, називаються братами. Якщо кожна вершина T (батько) сполучається не більше ніж з k іншими вершинами T1, T2, …, Tk (синами), то таке дерево називається k — арним. Якщо вершина не має синів, то вона називається листом; інакше вершина називається внутрішньою. Кількість синів у вершини дерева називається її степенем. Глибиною вершини називається довжина шляху від кореня до цієї вершини. Висотою дерева називається найбільша довжина від кореня до листа. Повним k — арним деревом називається k — арне дерево, в якому усі листи мають однакову глибину та усі внутрішні вершини мають однаковий степінь.

Властивість дерев. Нехай G = (V, E) — неорієнтований граф. Тоді наступні твердження еквівалентні:

G є деревом без виділеного кореня;

для довільних двох вершин G існує єдиний простий шлях, що їх сполучає;

граф G є зв’язним, але не залишається таким при вилученні хоча б одного ребра;

граф G є зв’язним і |E| = |V| - 1;

граф G є ациклічним і |E| = |V| - 1;

граф G є ациклічним, але додання довільного ребра породжує цикл.

У двійковому дереві кожна вершина може мати не більше двох синів (лівий та правий сини). Кожна вершина окрім кореня, має батька. При представленні двійкового дерева за допомогою вказівників кожна вершина містить ключ Val, вказівники на лівого Left та правого Right синів, а також на батька Up. Якщо сина або батька (для кореня) не існує, то відповідний вказівник містить NIL.

Ключі у двійковому дереві містяться у відповідності до властивості впорядкованості:

Нехай x — довільна вершина двійкового дерева. Якщо вершина y знаходиться в лівому піддереві вершини x, то x. Val > y.Val. Якщо вершина y знаходиться в правому піддереві вершини x, то x. Val < y.Val.

Нехай PTree — вказівник на структуру типу бінарне дерево.

PTree = ^Tree;

Tree = object.

Val: integer; /* значення вершини */.

Left: PTree; /* вказівник на лівого сина */.

Right: PTree; /* вказівние на правого сина */.

Up: PTree; /* вказівник на батька */.

end;

Об'єкт дерево має наступні методи:

INSERT — вставка елемента до дерева;

DELETE — вилучення елемента з дерева;

FIND — пошук елемента в дереві;

FindMin — пошук вузла дерева з мінімальним елементом;

FindMax — пошук вузла дерева з максимальним елементом;

PrintLR — обхід дерева зліва направо.

PTreeStr = ^TreeStr;

TreeStr = object.

TTree: PTree;

procedure Insert (Value:integer);

procedure Delete (Value:integer);

function Find (Value:integer): boolean;

function FindMin: PTree;

function FindMax: PTree;

procedure PrintLR;

end;

Властивість впорядкованості дозволяє надрукувати всі ключі у неспадному порядку за допомогою обходу дерева зліва направо, який відбувається наступним чином:

побувати в лівому піддереві.

побувати в корені.

побувати в правому піддереві.

procedure PLR (Tree: PTree);

begin.

if (Tree = NIL) then Exit;

PLR (Tree^.left);

write (Tree^.Val, «»);

PLR (Tree^.right);

end;

procedure 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 = NILx7420×6568×206Ex6946×646Ex694Dx206Ex3D3Ax4E20x4C49×200Dx6520×736Cx2065×6946×646Ex694Dx206Ex3D3Ax4620×694Dx206Ex5428×7254×6565x3B29×650Dx646Ex0D3B.

У процедурі вставки Insert елемента Value в бінарне дерево Tree відбувається рух вниз по дереву від корня до листа. В кожній вершині x, яка не є листом, процедура обирає напрямок руху (вліво чи вправо) у відповідності до властивості впорядкованості: якщо Value < x. Val, то відбувається рух вліво, інакше — вправо. Дійшовши до листа z, процедура вставляє нову вершину w, ключ якої дорівнює Value знову ж таки за властивістю впорядкованості: якщо Value < z. Val, то z. Left := w, інакше z. Right := w. Час виконання процедури дорівнює O (h), де h — висота дерева.

procedure InsElem (var Tree: Ptree; Value: integer);

begin.

if (Tree = NIL) then.

begin.

New (Tree);

Tree^.val := Value;

Tree^.Left := nil;

Tree^.Right := nil;

Exit;

end;

if (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^.Left, Value).

else 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) thenx7220×7065×206Cx3D3Ax5420×6572x5E65×522Ex6769×7468x0D3B††x6669×2820×7254×6565x2E5Ex6952×6867×2074×203Dx494Ex294Cx7420×6568×206Ex6572x6C70x3A20×203Dx7254×6565x2E5Ex654Cx7466x0D3B††x6944×7073×736Fx2065×7428×706Dx3B29×200D†x5420×6572×2065x3D3Ax5220×7065x3B6Cx200Dx6520×646Ex0D3Bx6E65x3B64x0D0Dx7270×636Fx6465×7275×2065×7254×6565×7453x2E72×6544×656Cx6574×2820×6156×756Cx3A65x6E69×6574×6567×2972x0D3Bx6562×6967x0D6E†x6544×456Cx656Cx206Dx5428×7254×6565×202Cx6156×756Cx2965x0D3Bx6E65x3B64x0D0D.

Дерева з довільним розгалудженням можна перетворити у двійкове дерево за принципом «ліва дитина — правий сусід». Кожна вершина містить три вказівники:

вказівник 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 < r) дерево відрізків T (l, r) будується рекурсивно наступним чином: воно складається з кореня v з параметрами B[v] = l, E[v] = r (B — Begin, E — End). Якщо r — l > 1, то воно складається з лівого піддерева T (l, [(B[v] + E[v])/2]) та правого піддерева T ([(B[v] + E[v])/2], r).

J.

Z.

h.

x00A8.

x031Ex5A6A.

K називаються стандартними інтервалами дерева T (l, r). Стандартні інтервали, які належать листам T (l, r), називаються елементарними інтервалами. T (l, r) збалансоване та має глибину xF0E9log2(r — l) xF0F9.

Дерево відрізків призначено для динамічного запам’ятання інтервалів, кінці яких належать множині {l, l + 1, …, r}. Якщо r — l > 3, то інтервал [b, e] з цілими b < e буде розбито в набір не більш ніж xF0E9log2 (r — l) xF0F9 + xF0EBlog2 (r — l) xF0FB — 2 стандартних інтервалів дерева T (l, r).

Функція BuildTree (l, r) будує та повертає дерево відрізків T (l, r). Складний тип даних tree має структуру дерева, в якій left та right — вказівники на лівого та правого сина, begin та end — параметри вершини.

BuildTree (l, r).

temp xF0AC new tree;

begin [temp] xF0AC l;

end [temp] xF0AC r;

if (r — l < 2) then.

begin.

left[temp] xF0AC NIL;

right[temp] xF0AC NIL;

return temp;

end;

left[temp] xF0AC BuildTree (l, [(l + r) / 2]);

right[temp] xF0AC BuildTree ([(l + r) / 2], r);

return temp;

Фрагментація інтервала [b, e] повністю визначається операцією занесення [b, e] в дерево відрізків Т. До структури даних tree додамо булевий параметр flag, який буде відповідати за включення стандартного інтервалу до інтервалу [b, e]. Тобто якщо для деякої вершини v має місце flag[v] = TRUE, то [ begin[v], end[v] ] xF0CD [b, e].

InsertTree (b, e, T).

if (b xF0A3xF020begin[T] and end[T] xF0A3xF020e) then flag[T] = TRUE;

else.

begin.

if (b.

if (xF020xF028begin[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] елемент даних, приписаний вершині l. Кожна вершина v, яка не є листом, містить два додаткові елементи: L[v] та M[v] найбільший елемент множини даних S у піддереві, коренем якого є відповідно лівий та середній син вершини v.

Вставка в 2 — 3 дерево. Для вставки нового елемента, а необхідно знайти місце для нового листа l. Для цього шукають елемент, а в дереві. Пошук закінчується у вузлі f, який має двох чи трьох синів що є листами.

Якщо з вузла f виходить лише два вузла l1 та l2, то l стає сином f. Якщо a < E[l1], то l стає самим лівим сином вузла f і покладаємо L[f] = a, M[f] = E[l1]. Якщо E[l1] < a < E[l2], то l стає середнім сином вузла f і покладаємо M[f] = a. Якщо E[l2] < a, то l стає третім сином вузла f. В останньому випадку може виникнути необхідність змінити значення L та M на деяких предках вузла f.

Нехай вузел вже має три листа l1, l2 та l3. L робимо відповідним сином вузла f, після чого f має чотирьох синів. Для збереження 2 — 3 властивості утворимо новий вузел g. Два лівих сина залишаємо синами вузла f, а два правих робимо синами g. Потім робимо g братом f, зробивши його сином батька f. Якщо батько вузла мав двох синів, то зупиняємося. Якщо трьох, то рекурсивно повторюємо вказану процедуру до тих пір, поки в дереві не залишиться більше трьох синів. Якщо корінь матиме чотири сина, утворимо новий корінь з двома новими синами, кожний з яких буде мати в якості двох своїх синів двох із чотирьох синів старого кореня.

Формула Ейлера. Позначимо через V, E, F кількість вершин, ребер та граней планарного графу G (включаючи необмежену область). Тоді справедлива формула:

V — E + F = 2.

Малюнок Х. Граф. V = 4, E = 6, F = 4: V — E + F = 4 — 6 + 4 = 2.

Якщо граф G незв’язний, а С — кількість компонент зв’язності, то має місце формула:

V — E + F — C = 1.

Теорема. Планарний граф з V вершинами має не більше 3(V — 2) ребер та не більше 2(V — 2) граней.

Доведення. Припустимо, що граф не має подвійних ребер та циклів. Побудуємо триангуояцію графу.

Реберний список з подвійними зв’язками (РСПЗ) використовується для представлення планарного графа. Плоске укладання планарного графа — це відображення кожної вершини у точку на площині, а кожного ребра — в просту лінію, яка сполучає пару образів кінцевих вершин цього ребра так, щоб образи ребер перетиналися лише у своїх кінцевих точках.

Головною компонентою РСПЗ для планарного графа (V, E) є реберний вузел. Між ребрами та реберними вузлами існує взаємно однозначна відповідність. Реберний вузел містить чотири інформаційні поля (V1, V2, F1, F2) та два поля вказівників (P1, P2). Поле V1 містить початок ребра, а поле V2 містить його кінець (ребро таким чином має орієнтацію). Поля F1 та F2 містять імена граней. Вказівник P1 (відповідно P2) задає реберний вузел, який містить перше ребро, що зустрічається за ребром (V1, V2) при повороті від нього проти годинникової стрілки навколо V1 (відповідно V2). Імена граней та вершин задаються цілими числами.

a8 5 4 1 2 4 9.

a9 4 7 4 2 3 7.

a10 3 7 5 4 2 9.

Якщо граф має N вершин та F граней, то введемо два масива HV[1:N] та HF[1:F], які містять номер ребра, що виходить з відповідної вершини (обмежує грань). Процедура Fill заповнює ці масиви переглядаючи V1 та F1 за час O (N).

Fill.

for i xF0ACxF0201 to N do.

begin.

if (HV[V1[i]] = 0) then HV[V1[i]] xF0AC i;

if (HV[V2[i]] = 0) then HV[V2[i]] xF0AC i;

if (HF[F1[i]] = 0) then HF[F1[i]] xF0AC i;

if (HF[F2[i]] = 0) then HF[F2[i]] xF0AC i;

end;

Після виконання процедури Fill для наведеного прикладу масиви HV та HF приймуть наступні значення:

HV = [1,1,2,3,4,5,6];

HF = [1,7,4,2,1].

Процедура vertex (i) будує послідовність ребер, інцидентних vi як послідовність адрес, занесених в масив An.

Vertex (j).

i xF0AC 1;

a xF0ACxF020HV[j];

a0 xF0AC a;

An[i] xF0AC a;

i xF0AC i + 1;

if (V1[a] = j) then a xF0AC P1[a].

else a xF0AC P2[a];

while (a xF0B9xF020 a0) do.

begin.

An[i] xF0AC a; i xF0AC i + 1;

if (V1[a] = j) then a xF0AC P1[a].

else a xF0AC P2[a];

end;

Час роботи процедури Vertex (j) пропоційна числу ребер, інцидентних vj. Аналогічно можна створити процедуру Facet (j), за допомогою якої можна отримати послідовність ребер, які обмежують грань fj, замінивши в попередній процедурі HV та V1 на HF та F1.

Процедури Vertex (j) перелічує ребра в порядку обхода навколо вершини проти годинникової стрілки, а Facet (j) перелічує їх в порядку обхода за годинниковою стрілкою навколо грані.

Хеш таблиці. Нехай дано n елементів, ключами яких є цілі числа в межах від 1 до m, m xF0B3xF020n. У найпростішому випадку задані n елементів можна зберігати у таблиці T[m] з прямою адресацією: T[i] або порожнє, або містить один елемент. Пошук в такій таблиці відбувається за час O (1). При такому зберіганні даних повинні виконуватись дві умови:

всі ключі повинні бути унікальними;

значення ключів повинні знаходитися у певних межах.

Якщо ключі не унікальні, то можна утворити m списків, кожен з який містить елементи з однаковими ключами. Час пошуку елемента із заданим ключем залишається рівним O (1). Але якщо елементи з одного списку мають різні характеристики (незважаючи на спільний ключ), і кількість елементів у списку дорівнює d, то час пошуку такого елемента складатиме O (d).

Система неперитинаючих множин — це набір непорожніх множин, які не перетинаються, в кожній з яких зафіксовано один із елементів (представник). На системі неперетинаючих множин підтримуються наступні операції:

Make-Set (x). Утворення множини. Процедурі передається вказівник на вже існуючий об'єкт х. Процедура утворює нову множину, єдиний елемент якої задається вказівником х. Оскільки множини не повинні перетинатися, елемент х повинен вказувати на новий об'єкт (який не лежить в жодній із існуючих множин).

Find-Set (x). Знайти множину. Повертає вказівник на представника (єдиного) множини, який містить елемент, на який вказує х.

Union (x, y). Об'єднання. Процедура застосовується, якщо елементи x та y містяться у різних множинах Sx та Sy і замінює ці множини на об'єднання Sx xF0C8 Sy; при цьому обирається деякий представник для Sx xF0C8 Sy. Самі множини Sx та Sy при цьому знищуються.

Реалізація системи непертинаючих множин за допомогою списків. Кожна множина зберігається у вигляді списку. Представником множини вважається перший елемент списку, а кожний елемент містить вказівники на наступний та перший елементи. Для кожного списку зберігаються вказівники на перший та останній (він потрібний для додавання елементів в кінець списку) елементи.

При такій реалізації операції Make-Set утворює список із одного елемента, а Find-Set повертає вказівник на початок списку і обидві вимагають часу O (1). Для виконання операції Union (x, y) необхідно додати список, який містить x, до кінця списку, що містить y. При цьому треба також встановити правильні вказівники на початок списку для усіх бувших елементів множини, що містила х; час вказаної операції лінійно залежить від розміру вказаної множини.

PList.

next.

val.

next.

val.

next.

val.

Малюнок Х. Однозв’язний список Малюнок Х. Стек.

Малюнок Х. Орієнтований граф. V = {1, 2,, 3, 4, 5, 6},.

E = {{1, 3}, {3, 2}, {2, 2}, {2, 4}, {5, 6}}.

Граф містить цикл, тому не є ані деревом, ані лісом Ліс дерев.

Дерево без.

виділеного кореня.

Малюнок Х.

Пошук вершини 3 у бінарному дереві.

3 < 15.

3 < 5.

3 > 2.

Малюнок Х. Пошук вершини з мінімальним та.

максимальним ключем у бінарному дереві.

MAX.

MIN.

Малюнок Х.

Вставка вершини 30 у бінарне дерево.

30 > 15.

30 > 24.

30 < 35.

Малюнок Х. Вилучення вершини.

24 з бінарного дерева.

FMin (24.Right) = 30,.

Delete (24.Right, 30).

ROOT.

Малюнок Х. Перетворення дерева з довільним розгалудженням у бінарне Малюнок Х. Структура AVL — дерева.

4,15.

4, 9.

9,15.

4, 6.

6, 9.

9,12.

12,15.

4, 5.

5, 6.

6, 7.

7, 9.

9,10.

10,12.

12,13.

13,15.

7, 8.

8, 9.

10,11.

11,12.

13,14.

14,15.

Малюнок Х. Дерево відрізків T (4, 15).

2; 4.

1; 2.

3; 4.

5; 6.

Малюнок Х. 2 — 3 дерево.

v2.

f4.

e5.

f2.

f1.

e2.

e1.

v4.

e6.

e4.

f3.

v3.

e3.

v1.

a2.

a10.

a3.

a1.

a9.

a8.

a4.

a7.

a5.

a6.

Малюнок Х. Планарний граф.

a.

b.

c.

x.

y.

a.

b.

c.

x.

y.

Малюнок Х. Операція UNION над двома неперитинаючими множинами.