Розділ 3. Абстрактні типи даних

326-330 [4]

структур даних. Визначальною характеристикою лінійних структур є те, що зв'язок

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

Щоб згадати термінологію можна почитати (с.77-83 [1], с.326-327 [4] ).

1, 2 ..., n. Найпростішим представленням дерева Т, що підтримує

оператор визначення батька вузла, буде лінійний масив А, де кожен елемент А[i] є покажчиком або курсором на батька вузла i. Корінь дерева Т відрізняється від інших вузлів тим, що має нульовий покажчик або покажчик на самого себе як на батька.
Дане уявлення використовує властивість дерев, що кожен вузол, відмінний від кореня, має тільки одного батька. Використовуючи це уявлення, батька будь-якого вузла можна знайти за фіксований час. Проходження по будь-якому шляху, тобто перехід по вузлах від батька до батька, можна виконати за час, пропорційний кількості вузлів шляху.

операторів, що вимагають інформацію про синів. Використовуючи описане представлення, вкрай

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

З прикладом реалізації можна ознайомитись в (с.86 [1]).

представлення дерев полягає у формуванні для кожного вузла списку його

синів. Ці списки можна представити будь-яким методом для представлення списків, але, оскільки число синів у різних вузлів може бути різним, найчастіше для цих цілей застосовуються зв'язані списки.

не дозволяє створювати великі дерева з малих. Це є наслідком

того, що всі дерева спільно використовують один масив для представлення зв'язаних списків синів; по суті, кожне дерево має власний масив заголовків для своїх вузлів.
З прикладом реалізації, що виправляє цей недолік, можна ознайомитись в (с.88-91 [1]).

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

328-336 [4]

є їх номери 1,2, … n, то підходящою структурою для

представлення цього дерева може бути масив записів з полями “лівий син” та “правий син”.

дерева може бути зв'язаним не більше ніж із двома піддеревами,

що називаються лівим і правим піддеревами вузла. Оголошення типу вузла бінарного дерева на мові Pascal може бути таким:

Для листків покажчики left та right мають значення nil

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

кількістю вузлів. Усі вузли-нащадки, що створюються, рівномірно розподіляються зліва та справа від кожного вузла-предка. При цьому досягається мінімально можлива глибина для заданої кількості вузлів дерева. Правило рівномірного розподілу п вузлів можна визначити рекурсивно:
перший вузол вважати коренем дерева;
створити ліве піддерево з кількістю вузлів nleft=п div 2;
створити праве піддерево з кількістю вузлів nright=п-nleft–1.

Оскільки структура дерева визначена рекурсивно, то для його створення та

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

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

Якщо кількість вузлів дорівнює нулю, дерево порожнє, а отже, виконано умову завершення рекурсії і функція має повернути значення nil. Якщо кількість вузлів дерева відрізняється від нуля, необхідно виділити пам'ять для кореня дерева, за наведеними вище формулами обчислити кількість вузлів у лівому та правому піддеревах і двічі рекурсивно викликати функцію tree для створення піддерев. Для посилання на корінь дерева використано локальний покажчик newnode. Значення покажчиків на корені піддерев, що їх повертатиме функція tree в результаті рекурсивних викликів, слід присвоїти полям left та right змінної newnode^.

спочатку буде відображене ліве піддерево, потім - корінь піддерева рівня

L, перед яким буде виведено L пробілів, далі - праве піддерево.

Трьома основними способами обходу дерева є обхід зверху вниз (в

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

передається параметр-значення, що є покажчиком на корінь дерева. Тіло всіх

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

яких потрібно знаходити за заданим значенням ключа. Такі дерева називаються

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

спускатися від кореня дерева бінарного пошуку за таким правилом: ліве

піддерево обирається тоді, коли значення розглядуваного вузла більше за шукане, а праве піддерево — тоді, коли вказане значення менше за шукане. Якщо значення вузла дорівнює шуканому, пошук слід завершити. Якщо пошук привів до порожньої гілки дерева, то ключового значення в дереві немає.
Для знаходження за таким алгоритмом значення ключа серед n-елементної множини буде переглянуто O(log п) елементів.

функції передається ключове значення і покажчик на корінь дерева, а

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

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

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

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

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

містять два інформаційні поля: поле рядкового типу для збереження слова

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

пошуку :
вузол, що видаляється, є листком дерева;
вузол, що

видаляється, має одного нащадка;
вузол, що видаляється, має двох нащадків.

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

на цей вузол слід присвоїти адресу його нащадка і звільнити

пам'ять, яку вузол х займав.

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

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

виконання практичної роботи №3.