Двійкове дерево

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Двійкове дерево

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

Різновиди двійкових дерев

[ред. | ред. код]
  • Двійкове дерево — таке кореневе дерево, в якому кожна вершина має не більше двох дітей.
  • Повне (закінчене) двійкове дерево — таке двійкове дерево, в якому кожна вершина має нуль або двох дітей.
  • Ідеальне двійкове дерево — це таке повне двійкове дерево, в якому листя (вершини без дітей) лежать на однаковій глибині (відстані від кореня).

Двійкове дерево на кожному 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-арним та двійковим деревом.

Література

[ред. | ред. код]
  • Дональд Кнут. Fundamental Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 1. — 650 с. — ISBN 0-201-89683-4.(англ.)
  • Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 12. Двійкові дерева пошуку. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
  • Parmar, Anand K. (22 січня 2020). Different Types of Binary Tree with colourful illustrations. Medium (англ.). Процитовано 24 січня 2020.

Посилання

[ред. | ред. код]