Поняття основних структур даних

План

Вступ

1. Елементарні структури даних

1.1. Масив

1.2 Лінійний список.

А) Стек.

Б) Черга

В) Зв’язаний список

2. Більш складні структури даних

2.1 Граф

2.2 Дерево

А) Бінарне дерево:

Б) Бінарне дерево пошуку:

1.3 Купа

А) Бінарна купа

Б) Біноменальна купа

Використана література

Вступ

В програмуванні та комп'ютерних науках структури даних -- це способи організації даних в комп'ютерах. Часто разом зі структурою даних пов'язується і специфічний перелік операцій, які можуть бути виконаними над даними, організованими в таку структуру.

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

Відома формула "Програма = Алгоритми + Структури даних" дуже точно виражає необхідність відповідального ставлення до такого підбору. Тому іноді навіть не обраний алгоритм для обробки масиву даних визначає вибір тої чи іншої структури даних для їх збереження, а навпаки.

Підтримка базових структури даних, які використовуються в програмуванні, включена в комплекти стандартних бібліотек найбільш розповсюджених мов програмування, такиї як Standart Template Library для C++, Java API, Microsoft .NET.

1. Елементарні структури даних

1.1. Масив

В програмуванні масив (англ. array) — одна з найпростіших структур даних, сукупність елементів переважно одного типу даних, впорядкованих за індексами, які зазвичай репрезентовані натуральними числами, що визначають положення елемента в масиві.

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

В переважній більшості мов програмування масив є стандартною вбудованою структурою даних.

Переваги та недоліки

Ефективність операцій

Масиви ефективні при звертанні до довільного елементу, яке відбувається за постійний час (O(1)), однак такі операції як додавання та видалення елементу, потребують часу O(n), де n — розмір масиву. Тому масиви переважно використовуються для зберігання даних, до елементів яких відбувається довільний доступ без додавання або видалення нових елементів, тоді як для алгоритмів с інтенсивними операціями додавання та видалення, ефективнішими є зв'язані списки.

Збереження в пам'яті

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

Масиви є дуже економною щодо пам'яті структурою даних. Для збереження 100 цілих чисел в масиві необхідно рівно в 100 разів більше пам'яті, ніж для збереження одного числа (плюс, можливо, ще декілька байтів). В той же час, усі структури даних, які базуються на вказівниках, потребують додаткової пам'яті для збереження самих вказівників разом з даними. Однак, операції з фіксованими масивами ускладнюються тоді, коли виникає необхідність додавання нових елементів у вже заповнений масив. Тоді його необхідно розширювати, що не завжди можливо і для таких задач слід використовувати зв'язані списки, або динамічні масиви.

Індекси в масивах

У випадках, коли розмір масиву є досить великий та використання звичайного звертання за індексом стає проблематичним, або великий відсоток його комірок не використовується, слід звертатись до асоціативних масивів, де проблема індексування великих об'ємів інформації вирішується більш оптимально.

З тої причини, що масиви мають фіксовану довжину, слід дуже обережно ставитись до процедури звертання до елементів за їхнім індексом, тому що намагання звернутись до елементу, індекс якого перевищує розмір такого масива (наприклад, до елементу з індексом 6 в масиві з 5 елементів), може призвести до непередбачуваних наслідків.

Слід також бути уважним щодо принципів нумерації елементів масиву, яка в одних мовах програмування може починатись з 0, а в інших — з 1.

Зберігання багатовимірних масивів

Збереження одновимірного масиву в пам'яті є тривіальним, тому що сама пам'ять комп'ютера є одновимірним масивом. Для збереження багатовимірного масиву ситуація ускладнюється. Припустимо, що ми хочемо зберігати двовимірний масив наступного виду:

$\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}$

Найпоширеніші способи його організації в пам'яті такі:

Розташування «рядок за рядком». Це найбільш уживаний на сьогодні спосіб, який зустрічається у більшості мов програмування.

Розташування «стовпчик за стовпчиком». Такий метод розташування масивів використовується, зокрема, в мові програмування Fortran

Масив з масивів. Багатовимірні масиви репрезентуються одновимірними масивами вказівників на одновимірні масиви. Розташування може бути як «рядок за рядком» так і «стовпчик за стовпчиком».

Двовимірний масив як масив вказівників на одновимірних масивів

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

1.2 Лінійний список.

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

конструктор для створення порожнього списка;
операція визначення порожності списка;
операція для додавання елемента в початок списка (cons в Лісп);
операція отримання першого елемента списка (або «голови») списка (car в Лісп);
операція для визначення списка, що складається із всіх елементів списка окрім першого (або його «хвоста») (cdr в Лісп).

Характеристики

За визначенням, список — це послідовність з n≥0 елементів X[1],X[2], … X[n], для якої виконується наступна умова: якщо n>0 та X[1] — перший елемент у списку, а X[n] — останній, то k-й елемент розташований між X[k-1] та X[k+1] елементами для усіх 1<k<n.

З такими структурами даних виконуються наступні операції:

отримання k-го елемента списку для читання чи запису в нього нового значення;
додавання нового елемента в будь-яку позицію в списку;
видалення елемента списку;
об'єднання в одному списку двох або більше лінійних списків;
розбиття списку на два або більше фрагментів;
створення копії списку;
визначення кількості елементів в списку;
сортування елементів списку;
пошук елемента, що задовільняє певним критеріям.

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

стек

лінійний список, в якому операції додавання та вилучення виконуються лише на одному кінці списку (верхівці стеку). Принцип побудови стеку називають LIFO

(англ. last in, last out).

черга (однобічна черга)

лінійний список, в якому усі операції додавання виконується на одному кінці (в голові черги), а операції вилучення — на іншому кінці списку (в хвості черги). Принцип побудови черги називають FIFO (англ. first in, first out).

дек або двобічна черга (англ. double-ended queue, deq)

лінійний список, в якому всі операції вставки та видалення виконуються на обох кінцях списку.

Не менш важливим окремим випадком лінійного списку є зв'язаний список, в якому кожний елемент окрім поля даних зберігає також вказівник на наступний. Така структура дозволяє зняти обмеження на зберігання лінійного списку в безперервній області пам'яті.

Важливим узагальненням лінійного списку є багатовимірний масив.

А) Стек.

СТЕК в інформатиці та програмуванні -- різновид лінійного списку, структура даних, яка працює за принципом (дисципліною) "останнім прийшов -- першим пішов" (LIFO, last in, first out). Всі операції (наприклад, видалення елементу) в стеку можна проводити тільки з одним елементом, який знаходиться на верхівці стеку та був введений в стек останнім.

Стек можна розглядати як певну аналогію до стопки тарілок, з якої можна взяти верхню, і на яку можна покласти верхню тарілку (інша назва стеку -- "магазин", за аналогією з принципом роботи магазину в автоматичній зброї)

Операції зі стеком

push ("заштовхнути елемент"): елемент додається в стек та розміщується в його верхівці. Розмір стеку збільшується на одиницю. При перевищенні розміру стека граничної величини, відбувається переповнення стека (stack overflow)

pop ("виштовхнути елемент"): отримує елемент з верхівки стеку. При цьому він видаляється зі стеку і його місце в верхівці стеку займає наступний за ним відповідно до правила LIFO, а розмір стеку зменшується на одиницю. При намаганні "виштовхнути" елемент з вже пустого стеку, відбувається ситуація "незаповнення" стеку (stack underflow)

Кожна з цих операцій зі стеком виконується за фіксований час O(1) і не залежить від розміру стеку.

Додаткові операції (присутні не у всіх реалізаціях стеку):

isEmpty: перевірка наявності елементів в стеку; результат: істина (true), коли в стеку немає елементів.

isFull: перевірка заповненості стека. Результат: істина, коли додавання нового елементу неможливе

clear: звільнити стек (видалити усі елементи).

top: отримати верхній елемент (без виштовхування).

size: отримати розмір (кількість елементів) стека.

swap: поміняти два верхніх елементи місцями.

Організація в пам'яті комп'ютера

Стек може бути організований як масив або множина комірок в певній області комп'ютера з додатковим зберіганням ще й вказівника на верхівку стека. Заштовхування першого елемента в стек збільшує адресу вказівника, виштовхування елементу зменшує її. Таким чином, адреса вказівника завжди відповідає комірці масиву, в якій зараз знаходиться верхівка стеку.

Багато процесорів ЕОМ мають спеціалізовані регістри, які використовуються як вказівники на верхівку стеку, або використовують деякі з регістрів загального вжитку для цієї спеціальної функції в певних режимах адресації пам'яті.

Приклади застосування

Калькулятори, які використовують зворотню польську нотацію, використовують стек для збереження даних обчислень.

Існує велика кількість "стеко-орієнтованих" мов програмування (Forth, PostScript), які використовують стек як базову структуру даних при виконанні багатьох операцій (арифметичних, логічних, вводу-виводу тощо).

Стеко-орієнтованими є багато з віртуальних машин, наприклад віртуальна машина Java.

Компілятори мов програмування використовують стек для передавання параметрів в процесі виклику підпрограм, процедур та функцій. Спеціалізований стек використовується також для збереження адрес повернення з підпрограм.

Реалізація базових алгоритмів

На високорівневих мовах програмування, стек може бути реалізований за допомогою масиву та додаткової змінної:

Для зберігання елементів стеку резервується масив S[1 n] певного розміру та додаткова змінна top[S], яка буде зберігати індекс верхівки стеку.

Операції push та pop тоді можуть бути записані так (без перевірки на переповнення та "незаповнення"):

PUSH (S, x)

1 top[S]:= top[S]+1 //збільшення індексу на 1

2 S[top[S]]:=x //запис нового елемента у верхівку стека

POP (S)

1 top[S]:=top[S]-1 // зменшення індексу на 1

2 return S[top[S]+1] //повернення колишньої верхівки стеку

Б) Черга

Черга в програмуванні — динамічна структура даних, що працює за принципом "перший прийшов - перший пішов" (англ. FIFO — first in, first out). У черги є голова (англ. head) та хвіст (англ. tail). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові.

Така черга повністю аналогічна звичній "базарній" черзі, в якій хто перший встав в неї, той першим буде обслуженим (але, на відміну від реальної черги, імовірність пройти поза чергою виключена)

Основні операції з чергою

англ. enqueue — "поставити в чергу". Операція додавання елемента в "хвіст" черги. При цьому довжина черги збільшується на одиницю. Якщо відбувається намагання додати елемент у вже заповнену чергу, відбувається її переповнення (англ. queue overflow).

англ. dequeue — "отримання з черги". Операція, яка повертає елемент з голови та видаляє його з черги, таким чином встановлюючи голову на наступний за видаленим елемент та зменшуючи довжину на одиницю. При намаганні видалити елемент з пустої черги, виникає ситуація "незаповнення" (англ. queue underflow).

Реалізація на мовах програмування

Черга може бути реалізована за допомогою масива Q[1 .n], в якому зберігаються дані та двох додаткових змінних head[Q] та tail[Q], в яких зберігаються індекси відповідно "голови" та "хвоста" черги, lenght[Q] -- довжина черги.

Тоді операції enqueue та dequeue запишуться так:

ENQUEUE (Q, x)

1 Q[tail[Q]] := x

2 if tail[Q] = length[Q]

3 then tail[Q] := 1

4 else tail[Q] := tail[Q] + 1

DEQUEUE (Q)

1 x := Q[head[Q]]

2 if head[Q] = length[Q]

3 then head[Q] := 1

4 else head[Q] := head[Q] + 1

5 return x

Черга з пріорітетами (англ. priority queue) — це структура даних, що призначена для обслуговування множини S, з кожним елементом якої пов'язано певне значення, що зветься ключем (англ. key). Черга з пріорітетами може бути неспадною або незростаючою. В незростаючій черзі з пріорітетами підтримуються наступні операції:

Операція Insert(S,x) вставляє елемент x в множину S.

Операція Maximum(S) повертає елемент множини S з найбільшим ключем.

Операція Extract_Max повертає елемент з найбільшим ключем, видаляючи його при цьому з множини S.

Операція Change_Key(S,x,k) змінює значення ключа для елемента x, шляхом заміни його ключем зі значенням k.

Реалізація

Черга з пріорітетами може бути реалізована на різних структурах даних. В залежності від обраної структури змінюється ефективність виконання операцій з чергою. Найбільш часто вживаними є масиви і купи.

Черга повідомлень

Перейти до: навігація, пошук

Черга повідомлень — в програмуванні, програмна компонента що використовується для організації взаємодії між процесами або взаємодії між потоками програми. Такі компоненти використовують чергу для впорядкування повідомлень.

В) Зв’язаний список

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

Зв'язані списки мають серію переваг порівняно з масивами. Зокрема, в них набагато ефективніше (за час О(1), тобто незалежно від кількості елементів) виконуються процедури додавання та вилучення елементів. Натомість, масиви набагато кращі в операціях, які потребують безпосереднього доступу до кожного елементу, що у випадку зі зв'язаними списками неможливо та потребує послідовного перебору усіх елементів, які передують даному.

Різновиди зв'язаних списків

[ред.] Однобічно зв'язані списки

Однобічно зв'язаний список з трьох елементів

В однобічно зв'язаному списку, який є найпростішим різновидом зв'язаних списків, кожний елемент складається з двох полів: data або даних, та вказівника next на наступний елемент. Якщо вказівник не вказує на інший елемент (інакше: next = NULL), то вважається, що даний елемент — останній в списку.

[ред.] Двобічно зв'язаний список

Зображення:Doubly_linked_list.png Двобічно зв'язаний список

В двобічно зв'язаному списку елемент складається з трьох полів — вказівника на попередній елемент prev, поля даних data та вказівника next на наступний елемент. Якщо prev=NULL, то в елемента немає попередника (тобто він є «головою» списку), якщо next=NULL, то в нього немає наступника («хвіст» списка).

[ред.] Кільцевий список

В кільцевому списку перший та останній елемент зв'язані. Тобто, поле prev голови списка вказує на хвіст списка, а поле next хвоста списка вказує на голову списка.

Застосування списків:

Списки інтенсивно застосовуються в програмуванні як самостійні структури. Також на їх основі можуть будуватись більш складні структури даних, такі як дерева. На базі списків також можуть бути реалізовані стеки та черги.

[ред.] Переваги та недоліки

В загальному випадку, якщо необхідно оперувати з динамічними множинами, де присутні інтенсивні операції з додавання або видалення елементів, існують досить переконливі аргументи для використання саме зв'язаних списків.

[ред.] Зв'язані списки та масиви

Списки мають деякі переваги над масивами. Вони досить ефективні щодо операцій додавання або видалення елементу в довільному місці списка, виконуючи їх за постійний час, тоді як масиви для цього потребують часу O(n), тобто час зростає з ростом кількості елементів масиву.

В списках також не існує проблеми "розширення", яка рано чи пізно виникає в масивах фіксованого розміру, коли виникає необхідність включити в нього додаткові елементи. Точно так, фіксований масив, з якого було видалено багато елементів (або вони просто не використовуються) є дуже неефективним з точки зору використання пам'яті. Функціонування списків можливо в ситуації, коли пам'ять комп'ютера фрагментована, тоді як масиви переважно потребують неперервної області для зберігання.

З іншого боку, масиви дозволяють безпосередній доступ до будь-якого елементу. Однобічно зв'язані списки, натомість, потребують проходження усіх попередніх елементів. Це призводить до складнощів застосування списків в задачах, де необхідно швидко знаходити елемент за його індексом, наприклад в алгоритмах сортування. Кешування списків в таких випадках майже не дає ефекту.

Іншим очевидним недоліком списків є необхідність разом з корисною інформацією додаткового збереження інформації про вказівники, що позначається на ефективності використання пам'яті цими структурами.

Двобічне та однобічне зв'язування:

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

2. Більш складні структури даних

2.1 Граф

Граф — пара множин V і E, елементи множини V називають вершинами (англ. vertex), множина E містить впорядковані та невпорядковані пари вершин. Невпорядкована пара вершин називається ребром, впорядкована — дугою.

Граф, який містить тільки ребра називається неорієнтованим, який містить тільки дуги — орієнтованим. Якщо пара вершин сполучається кількома ребрами чи дугами одного напрямку, то ребра (дуги) називають кратними. Дуга чи ребро що сполучає вершину саму із собою називається петлею. Вершини сполучені ребром чи дугою називають суміжними, також називають суміжними ребра, що мають спільну вершину.

Кожен граф можна відобразити в евклідовому просторі множиною точок, які відповідають вершинам, сполучених лініями, що відповідають ребрам (дугам).

Крім того, варто зазаначити, що в сучасній теорії графів існує проблема відсутності уніфікованої термінології. Тому при поданні певного визначення чи поняття із цього розділу дискретної математики треба мати це на увазі. Тут використовується найбільшвживана термінологія — американська

Ось альтернативне і доповнене означення графа.

Простим графом називають пару G=(V,E), де V - скінченна і непорожня множина, елементи якої називають вершинами. E - множина ребер, кожне з яких - це невпорядкована пара різних вершин з V.

Іноді є потреба якусь пару вершин з'яднати більше, ніж одним ребром. Тому вводять означення Мультиграфа. Мультиграфом називають пару G=(V,E), де V - скінченна і непорожня множина, елементи якої називають вершинами. E — сім'я ребер, кожне з яких — це невпорядкована пара різних вершин із V.

Ребра, які з'єднують одну й ту саму пару вершин, називають кратними (перелельними) ребрами.

Подальше узагальнення означення графу полягає у введенні поняття псевдограф. Псевдограф — це пара G=(V,E), де V - скінченна і непорожня множина, елементи якої називають вершинами. E - множина ребер, кожне з яких - це невпорядкована пара (не обов'язково різних! ) вершин із V.

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

Розглянуть три типи називають неорієнтованими графами. Псевдограф є узагальненням мультиграфа, а мультиграф у свою чергу - простого графа.

Тип графа	Ребра	Кратні ребра дозволені?	Петлі дозволені?
Простий граф	Неорієнтовані	Ні	Ні
Мультиграф	Неорієнтовані	Так	Ні
Псевдограф	Неорієнтовані	Так	Так
Орієнтований граф	Орієнтовані	Ні	Так
Орієнтований мультиграф	Орієнтовані	Так	Так

2.2 Дерево

Зображення:Gen tree.png

Дерево - в інформатиці та програмуванні одна з найпоширеніших структур даних. Формально дерево визначається як скінченна множина Т з однієї або більше вершин (вузлів, nodes), яке задовольняє наступним вимогам:

існує один виокремлений вузол - корень (root) дерева

інші вузли (за виключенням кореня) розподілені серед m ≥ 0 непересічних множин T1 .Tm і кожна з цих множин в свою чергу є деревом. Дерева T1 .Tm мають назву піддерев (subtrees) даного кореня.

З цього визначення випливає, що кожна вершина є в свою чергу коренем деякого піддерева. Кількість піддерев вершини має назву ступеня (degree) цієї вершини. Вершина ступеню нуль має назву кінцевої (terminal) або листа (leaf). Некінцева вершина також має назву вершини розгалуження (branch node). Нехай x - довільна вершина дерева з коренем r. Тоді існує єдиний шлях з r до x. Усі вершини на цьому шляху називаються предками (ancestors) x; якщо деяка вершина y є предком x, то x називається нащадком (descendant) y. Нащадки та предки вершини x, що не співпадають з нею самою, називаються власними нащадками та предками. Кожну вершину x, в свою чергу, можна розглядати як корень деякого піддерево, елементами якого є вершини-нащадки x. Якщо вершини x є предком y та не існує вершин поміж ними (тобто x та y з'єднані одним ребром), а також існують предки для x (тобто x не є коренем), то вершина x називається батьком (parent) до y, а y - дитиною (child) x. Коренева вершина єдина не має батьків. Вершини, що мають спільного батька, називаються братами (siblings). Вершини, що мають дітей, називаються внутрішніми (internal). Глибиною вершини x називається довжина шляху від кореня до цієї вершини. Максимальна глибина вершин дерева називається висотою.

Якщо існує відносний порядок на піддеревах T1 .Tm, то таке дерево називається впорядкованим (ordered tree) або пласким (plane tree).

Лісом (forest) називають множину дерев, які не перетинаються.

Найчастіше дерева в інформатиці зображують з коренем, який знаходиться зверху (говорять, що дерево в інформатиці "росте вниз").

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

Важливими операціями на деревах є:

обхід вершин в різному порядку

перенумерація вершин

пошук елемента

додавання елемента у визначене місце в дереві

видалення елемента

видалення цілого фрагмента дерева

додавання цілого фрагмента дерева

трансформації (повороти) фрагментів дерева

знаходження кореня для будь-якої вершини

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

А) Бінарне дерево:

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

Зображення:Binary tree.png Бінарне дерево

Різновиди бінарних дерев

Бінарне дерево -- таке кореневе дерево, в якому кожна вершина має не більше двох дітей.

Повне (закінчене) бінарне дерево -- таке бінарне дерево, в якому кожна вершина має нуль або двох дітей.

Ідеальне бінарне дерево -- це таке повне бінарне дерево, в якому листя (вершини без дітей) лежать на однаковій глибині (відстані від кореня).

Бінарне дерево на кожному n-му рівні має від 1 до 2n вершин.

Обхід бінарного дерева

Докладніше дивись статтю Обхід дерева.

Часто виникає необхідність обійти усі вершини дерева для аналізу інформації, що в них знаходиться. Існують декілька порядків такого обходу, кожний з яких має певні властивості, важливі в тих чи інших алгоритмах: прямий (preorder), центрований (inorder) та зворотній (postorder).

Реалізація бінарних дерев

Реалізація бінарного дерева. Кожна вершина містить вказівники на праву та ліву дитину (left та right)

Існують декілька варіантів конструювання бінарних дерев в залежності від задач, які вирішуються цими структурами та можливостей тої чи іншої мови програмування. Реалізація з використанням вказівників передбачає зберігання в кожній вершині дерева x разом з даними двох полів з вказівниками (правим та лівим) right[x] та left[x] на відповідних дітей цієї вершини.

Модифікована реалізація бінарного дерева. Кожна вершина містить також вказівник на батьківську вершину

Також іноді додається вказівник p[x] на батьківську вершину. Це виявляється корисним, коли необхідний швидкий доступ до батьківської вершини та спрощує деякі алгоритми. Іноді достатньо тільки вказівника на батьківську вершину. Взагалі будь-яке орієнтоване дерево можна описати, знаючи тільки зв'язки від дітей до батьківської вершини. Деякі різновиди бінарних дерев (наприклад, червоно-чорні дерева або AVL-дерева), вимагають збереження в вершинах і деякої додаткової інформації. Якщо у вершини відсутня одна чи обидві дитини, відповідні вказівники ініціалізуються спеціальними "пустими" значеннями.

Бінарне дерево на базі масиву

Бінарні дерева також можуть бути побудовані на базі масивів. Такий метод набагато ефективніший щодо економії пам'яті. В такому представленні, якщо вершина має порядковий номер i, то її діти знаходяться за індексами 2i+1 та 2i+2, а батьківська вершина за індексом ((i-1)/2) (за умов, що коренева вершина має індекс 0). Інший варіант зберігання дерева в масиві — зберігати індекси дітей.

Представлення n-арних дерев як бінарних

Існує єдине та взаємооднозначне відображення довільного впорядкованого дерева в бінарне.

Приклад трансформації n-арного дерева в бінарне

Для цього слід послідовно зв'язати усіх дітей кожної сім'ї з першою дитиною та та видалити усі вертикальні з'єднання за виключенням з'єднання батька з першою дитиною в сім'ї. Тобто кожна вершина N впорядкованого n-арного дерева відповідає вершині M деякого бінарного дерева. Ліва дитина вершини M відповідає першій дитині вершини N, а права дитина M відповідає першому з наступних братів N (тобто першому з наступних дітей батька вершини N).

Така відповідність має назву природної відповідності між n-арним та бінарним деревом.

Б) Бінарне дерево пошуку:

Бінáрне дéрево пóшуку (англ. binary search tree, BST) в інформатиці - бінарне дерево, в якому кожній вершині x співставлене певне значення val[x]. При цьому такі значення повинні задовольняти умові впорядкованості:

нехай x -- довільна вершина бінарного дерева пошуку. Якщо вершина y знаходиться в лівомі піддереві вершини x, то val[y] ≤ val[x]. Якщо у знаходиться у правому піддереві x, то val[y] ≥ val[x].

Таке структурування дозволяє надрукувати усі значення у зростаючому порядку за допомогою простого алгоритма центрованого обходу дерева. Бінарні дерева пошуку набагато ефективніші в операціях пошуку, аніж лінійні структури, в яких витрати часу на пошук пропорційні O(n), де n -- розмір масиву даних, тоді як в повному бінарному дереві цей час пропорційний в середньому O(log2n) або O(h), де h - висота дерева (хоча гарантувати, що h не перевищує log2n можна лише для збалансованих дерев, які є ефективнішими на пошукових алгоритмах, аніж прості бінарні дерева пошуку).

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

Процедура пошуку в бінарному дереві отримує на вході значення k, яке необхідно знайти, та вказівник x на корень того піддерева, в якому слід шукати.

SEARCH (x, k)

1 if x = NULL or k = val[x]

2 then return x

3 if k < val[x]

4 then return SEARCH (left[x], k)

5 else return SEARCH (right[x], k)

В процесі пошуку ми рухаємось від кореня, порівнюючи значення k зі значенням в поточній вершині х. Якщо k < val[x], пошук рекурсивно продовжується в лівому піддереві (k може бути тільки там згідно умови впорядкованості), інакше -- у правому піддереві. Очевидно, що довжина шляху не перевищує висоти дерева, тому час пошуку є O(h), де h - висота дерева.

Мінімум, максимум, наступник та попередник

Мінімальний елемент в дереві можна знайти, розглянувши послідовно ліве піддерево left[x]:

MINIMUM (x)

1 while left[x]<>NULL

2 do x:=left[x]

3 return x

Процедура знаходження максимуму симетрична. Обидві процедури знову ж таки знаходять елемент за час, пропорційний O(h)

Елемент, що є наступним за даним (в сенсі відношення впорядкованості) можна знайти за допомогою такої процедури:

SUCCESSOR (x)

1 if right[x] <> NULL

2 then return MINIMUM (right[x])

3 y:=p[x]

4 while y<>NULL and x = right[y]

5 do x:=y

6 y:=p[y]

7 return y

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

Додавання елементу

Процедура додавання елементу в бінарне дерево T додає елемент, зберігаючи умову впорядкованості. Параметром тут є вказівник z на нову вершину, в яку поміщене значення val[z], left[z]=right[z]=NULL.

INSERT (T, z)

1 y:=NIL

2 x:=root[T]

3 while x <> NULL

4 do y:=x

5 if val[z] < val[x]

6 then x:=left[x]

7 else x:=right[x]

8 p[z]:=NULL

9 if y = NULL

10 then root[T] :=z

11 else if val[z]<val[y]

12 then left[y]:=z

13 else right[y]:=z

Процедура рухається вниз по дереву, при цьому зберігаючи в y вказівник на батька вершини x. Порівнюючи значення в x та z, процедура вирішує, в яке з піддерев рухатись далі. Процес завершується тоді, коли x=NULL. Саме сюди й слід помістити вершину z (рядки 8-13). Ця операція також потребує часу для виконання, пропорційного O(h)

Видалення елементу

Параметром для процедури є вказівник на вершину, що видаляється. Тут можливі три варіанти дій:

якщо у вершини немає дітей, достатньо помістити NULL у відповідне поле його батька (замість вказівника на вершину, що видаляється)

якщо у вершини є одна дитина, можна з'єднати батька цієї вершини безпосередньо з її дитиною

якщо вершина має двох дітей, слід спочатку знайти слідуючий (в сенсі порядку) елемент y, в якого немає лівої дитини, а потім скопіювати значення та додаткові дані з вершини y на місце вершини, що видаляється, а саму вершину y видалити.

DELETE (T, z)

1 if left[z] = NULL or right[z]=NULL

2 then y:=z

3 else y:=SUCCESSOR(z)

4 if left[y] <> NULL

5 then x:=left[y]

6 else x:= right[y]

7 if x <> NULL

8 then p[x]:=p[y]

9 if p[y]:=NULL

10 then root[T]:=x

11 else if y=left[p[y]]

12 then left[p[y]] :=x

13 else right[p[y]]:=x

14 if y <> z

15 then val[z]:=val[y]

16 //копіювання додаткових даних з y

17 return y

1.3 Купа

КУПА або піраміда (англ. heap) в інформатиці -- спеціалізована деревовидна структура даних, в якій існують певні властивості впорядкованості. Така структура даних повинна задовільняти основній властивості купи:

нехай А та B -- елементи купи, такі що B підпорядковане A (B - дитина А). Тоді значення B не повинно перевищувати А, тобто val[B] ≤ val[A]

Найбільш уживаним класом куп є бінарні купи.

Базові операції з купою такі:

підтримка основної властивості купи

побудова купи з невпорядкованого масиву

сортування купи

видалення найменшого елемента

отримання найбільшого елемента

додавання елемента

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

А) Бінарна купа

Бінарна купа (англ. binary heap) — це структура даних, що є масивом, який можна розглядати як майже повне бінарне дерево. Кожен вузол цього дерева відповідає певному елементу масиву. На всіх рівнях, крім, можливо останнього, дерево повністю заповнене (заповнений рівень — такий, що містить максимально можливу кількість вузлів). Останній рівень заповнюється послідовно зліва направо до тих пір, доки в масиві не закінчатся елементи.

Для масиву A у корені дерева знаходиться елемент A[1]. Далі дерево будується за наступним принципом: якщо якомусь вузлу відповідає індекс i, то індекс його батьківського вузла обчислюється за допомогою процедури Parent(i), індекс лівого дочірнього вузла — за допомогою процедури Left(i), а індекс правого дочірнього вузла — за допомогою процедури Right(i):

Parent(i)

return $\lfloor\;i/2\rfloor$

Left(i)

return 2i

Right(i)

return 2i + 1

Розглядають два види бінарних куп: неспадні і незростаючі. В обох видах значення, що розташовані у вузлах купи, задовільняють властивості купи (англ. heap property). Властивісь незростаючої купи (англ. max-heap property) полягає в тому, що для кожного вузла крім кореневого виконується нерівність:

$A[Parent(i)] \ge\; A[i]$ .

Іншими словами, значення вузла не перевищує значення батьківського вузла. Таким чином найбільший елемент знаходиться в корені дерева. Принцип побудови неспадної купи(англ. min-heap) протилежний. Властивість неспадної купи (англ. min-heap property) полягає в тому, що кожен елемент крім кореневого є неменшим за свій батьківський елемент:

$A[Parent(i)] \le\; A[i]$ .

Підтримка властивостей купи

Підтримку властивості купи можна здійснювати за допомогою процедури Max_Heapify (для незростаючих бінарних куп). На вхід подається масив A й індекс i цього масиву. При виклику процедури Max_Heapify припускається, що бінарні дерева, коренями яких є елементи Left(i) і Right(i) є незростаючими купами, але сам елемент A[i] може бути меншим за його дочірні елементи і тим самим порушувати властивість незростаючої купи. Процедура Max_Heapify спускає значення елемента A[i] вниз по купі до тих пір, доки дерево в якому цей елемент буде корнем не стане незростаючою бінарною купою:

Max_Heapify(A,i)

1 $l\gets \;Left(i)$

2 $r\gets \;Right(i)$

3 if $l \le \;heap\_size[A]$ і A[l] > A[i]

4 then $largest \gets\; l$

5 else $largest \gets\; l$

6 if $r \le \;heap\_size[A]$ і A[r] > A[largest]

7 then $largest \gets\; r$

8 if $largest \ne\;i$

9 then Поміняти $A[i]\leftrightarrow\;A[largest]$

10 Max_Heapify(A,largest)

Час роботи процедури в найгіршому випадку пропорційний висоті купи. Якщо купа складається з n елементів, то її висота log2(n) . Тому оцінка часу роботи одного визову Max_Heapify є O(log n).

Для падтримки властивості неспадної бінарної купи можна скористатись процедурою Min_Heapify. Вона повністю подібна до Max_Heapify, тільки в рядках 3 і 6 алгоритму знак ">" треба замінити на "<".

Побудова купи

За допомогою процедури Max_Heapify можно перетворити масив A[1 n], де n = length[A], у незростаючу купу. Всі елементи підмасиву $A[(\lfloor\;n/2\rfloor\;+1) n]$ є листами дерева, тому кожен з них можна вважати одноелементною купою, з якої можна почати процес побудови. Процедура Build_Max_Heap проходить по всім іншим вузлам і для кожного з них иконує процедуру Max_Heapify:

Build_Max_Heap(A)

1 $heap\_size[A] \gets\; length[A]$

2 for $i \gets\;\lfloor\;length[A]/2\rfloor$ downto 1

3 do Max_Heapify(A,i)

По завершенню роботи процедури, масив A організується в незростаючу купу. Час роботи процедури Build_Max_Heap можна записати так:

$O\left(n\sum_{h=0}^{\lfloor\;\log_{2}n\rfloor}\frac{h}{2^h}\right) = O\left(n\sum_{h=0}^{\infty}\frac{h}{2^h}\right) = O(n)$

Для створення неспадної купи, необхідно замінити у третьому рядку алгоритма виклик Max_Heapify на Min_Heapify.

Алгоритм впорядкування купою

Робота алгоритму сортування купою починається з віклику процедури Build_Max_H, за допомогою якої з початкового масиву A[1 n] створюється незростаюча купа. Далі послідовно з купи виймається найбільший елемент, який міняють з останнім в купі. Після кожного обміну розмір купи зменшують на одиницю. В кінці отримують повністю відсортований неспадній масив:

Heapsort(A)

1 Build_Max_Heap(A)

2 for $i\gets\;length[A]$ downto 2

3 do Поміняти $A[1]\leftrightarrow\;A[i]$

4 $heap\_size[A]\gets\;heap\_size[A]-1$

5 Max_Heapify(A,1)

Час роботи процедури Heapsort рівний O(n log n), оскільки всього потрібно n-1 викликів Max_Heapify, кожен з яких працює за O(log n).

Б) Біноменальна купа

Біноміальна купа (англ. binomial heap) — це множина біноміальних дерев, що задовільняє властивостям біноміальної купи:

Кожне біноміальне дерево у купі підпорядковується властивості неспадної купи (англ. min-heap property): ключ вузла не менший за ключ його батьківського вузла.

Для будь якого невід'ємного цілого k в купі існує не більше одного біноміального дерева,чий корінь має ступінь k.

З даних властивостей випливає, що біноміальна купа, що має n візлів, складається з небільше ніж $\lfloor\;\log\;n\rfloor + 1$ біноміальних дерев.

Використана література:

1. "Алгоритми, побудова і аналіз" Т. Кормен, Ч. Лейзерсон, Р. Рівест, К. Штайн

2. Костів О.В. Структури даних. Львів, ЛНУ, 2000 р. 56 с.

3. http://uk.wikipedia.org/

4. Завада О.П Алгоритмізація і програмування: Тексти лекцій. Львів: Видавничий центр ЛНУ імені Івана франка, 2004.-76 с.

5. Матеріал з Вікіпедії — вільної енциклопедії.

Поняття основних структур даних

Дружественные ресурсы

Реклама