Базові структури даних

Сторінки роботи

зміст роботи

Лекція 4: Базові структури даних. Дерева

0 Вступ

Цей цикл лекцій, як зазначалося, присвячений базовим структурам даних. Однією з таких є структура, що має велике значення у практиці програмування. У цій лекції ми розглянемо поняття «дерево», види дерев, способи представлення їх у програмах.

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

1 То що таке «дерево»?

Дерево- це зв'язковий ациклічний неорієнтований граф. Що ж ховається за цими загадковими словами?

Граф– безліч вершин (V) і ребер (E), що поєднують їх, позначається якG(V,E). У загальному випадку, згадуючи графи, ми говоримо про так звані орієнтовані графи, в яких має значення напрямок (тобто вершини з'єднують «лінії зі стрілками», звані в українській літературі дугами 14). ). Унеорієнтованих графахнапрям значення не має.

Шляхз вершиниuу вершинуv– послідовність з'єднаних ребрами вершин , деv0=u,vk=v. Шлях, у якого початкова і кінцева вершини збігаються, називається циклом.Ациклічний граф- граф, що не містить циклів.

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

Розглянемо властивості дерев. Нехай ми маємо зв'язковий ациклічний неорієнтований графG(V,E). Тоді такі визначення рівносильні:

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

Довести ці властивості пропонується самостійно.

Якщо є (можливо) незв'язний, але ациклічний граф, можна говорити проліс. Ліс, як і належить, складається з дерев (компоненти зв'язності графа). Багато алгоритмів обробки дерев застосовуються і до лісів.

1.1 Дерева з коренем

Дерево з коренем виходить, якщо дереві зафіксувати вершину, назвавши її коренем (root). Вершини кореневого дерева англійською називають «nodes».

Нехайx– довільна вершина кореневого дерева з коренемr. Існує єдиний шлях зrдоx; всі вершини, що знаходяться на цьому шляху, ми називаємо предками (14) (ancestors) вершини x16. Якщоyє предкомx, тоxназиваєтьсянащадком(descendant). Кожну вершину прийнято вважати своїм предком та нащадком.

Для кожної вершиниxможна розглянути дерево, що складається з усіх нащадківx, у якихxвважається коренем. Воно називається піддеревим з коренемx(subtree rooted atx).

Якщо (y,x) - останнє ребро на шляху з кореня вx, тоyназиваєтьсябатьком(parent)x, аx-дитиною(child)y.

Корінь є єдиною вершиною, яка не має батька. Вершини, що мають спільного з батьків, в англійській літературі називають siblings; точного українського перекладу цього слова немає, тому використовується найближче за змістом – брати 14 . Вершина, що не має дітей, називається 13 листом (leaf). Вершини, що мають дітей, називаються внутрішніми (internal).

Число дітей у вершини кореневого дерева називають її ступенем (degree). Довжина шляху від кореня до довільної вершиниxназивається глибиною (depth) вершиниx. Максимальна глибина вершин дерева називається висотою (14) (height) дерева.

Дерево з порядком на дітях(ordered tree) – кореневе дерево, безліч дітей для кожної вершини якого впорядковано: точно визначено, який із дітей перший, який другий тощо.

1.2 Двійкові дерева. Позиційні дерева

Двійкове дерево(binary tree) найпростіше визначити рекурсивно як деякий набір вершин, який:

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

Двійкове дерево, яке не містить вершин, називається порожнім (empty). Якщо ліве піддерево не порожнє, то його корінь називаєтьсялівою дитиною(left child) кореня всього дерева, якщо не порожньо праве піддерево, то його корінь носить назвуправої дитини(right child) кореня всього дерева. Якщо ліве або праве піддерева порожні, кажуть що корінь не має лівого абоправої дитини (child is absent).

Ви запитаєте, чому б не визначити двійкове дерево як дерево з порядком на дітях, де ступінь кожної вершини не перевищує 2. Все просто. У дереві з порядком на дітях для вершин ступеня 1 не буде мати значення, якою є єдина дитина – лівою або правою.