Дерево (структура даних)

Простий приклад неупорядкованого дерева

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


1. Визначення

  • Кореневий вузол - самий верхній вузол дерева (вузол 2 на прикладі).
  • Корінь - одна з вершин, за бажанням спостерігача.
  • лист, листовий або термінальний вузол - вузол, що не має дочірніх елементів (вузли 2, 4, 5, 11).
  • Внутрішній вузол - будь-який вузол дерева, що має нащадків, і таким чином, не є листовим вузлом (2, 7, 5, 6, 9).

Дерево вважається орієнтованим, якщо в корінь не заходить жодне ребро.

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

2. Вузли

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


2.1. Кореневі вузли

Самий верхній вузол дерева називається кореневим вузлом. Бути самим верхнім вузлом увазі відсутність у кореневого вузла предків. Це вузол, на якому починається виконання більшості операцій над деревом (хоча деякі алгоритми починають виконання з "листів" і виконуються, поки не досягнуть кореня). Всі інші вузли можуть бути досягнуті шляхом переходу від кореневого вузла по ребрах (чи посиланнях). (Згідно формальному визначенню, кожен подібний шлях повинен бути унікальним). У діаграмах він зазвичай зображається на самій вершині. У деяких деревах, наприклад, купах, кореневий вузол має особливі властивості. Кожен вузол дерева можна розглядати як кореневий вузол піддерева, "зростаючого" з цього вузла.


3. Піддерев

Піддерево - частина деревоподібна структури даних, яка може бути представлена ​​у вигляді окремого дерева. Будь вузол дерева T разом з усіма його вузлами-нащадками є піддерево дерева T. Для будь-якого вузла піддерева або повинен бути шлях в кореневий вузол цього піддерева, або сам вузол повинен бути кореневим. Тобто піддерево пов'язано з кореневим вузлом цілим деревом, а відносини піддерева з усіма іншими вузлами визначаються через поняття відповідне піддерево (за аналогією з терміном "відповідне підмножина ").


4. Упорядкування дерев

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

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


5. Подання дерев

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

5.1. Дерева як графи

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

6. Методи обходу

Покроковий перебір елементів дерева по зв'язкам між вузлами-предками і вузлами-нащадками називається обходом дерева. Найчастіше, операція може бути виконана переходом покажчика по окремих вузлах. Обхід, при якому кожен вузол-предок проглядається перш його нащадків називається предупорядоченним обходом або обходом в прямому порядку (pre-order walk), а коли проглядаються спочатку нащадки, а потім предки, то обхід називається поступорядоченним обходом або обходом в зворотному порядку (post- order walk). Існує також симетричний обхід, при якому відвідується спочатку ліве піддерево, потім вузол, потім - праве піддерево, і обхід в ширину, при якому вузли відвідуються рівень за рівнем (N-й рівень дерева - безліч вузлів з ​​висотою N). Кожен рівень обходиться зліва направо.


7. Загальні операції

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

8. Загальне застосування

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

Примітки

Література