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

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

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

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

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

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

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

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

Обхід двійкового дерева

Часто виникає необхідність обійти усі вершини дерева для аналізу інформації, що в них знаходиться. Існують декілька порядків такого обходу, кожний з яких має певні властивості, важливі в тих чи інших алгоритмах: прямий (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-арного дерева відповідає вершині M деякого двійкового дерева. Ліва дитина вершини M відповідає першій дитині вершини N, а права дитина M відповідає першому з наступних братів N (тобто першому з наступних дітей батька вершини N).

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

Див. також

• Двійкове дерево пошуку
• Збалансоване дерево
• AVL-дерево
• B-дерево
• Червоно-чорне дерево
• Префіксне дерево
• Список структур даних

Література

• Parmar, Anand K. (22 січня 2020). Different Types of Binary Tree with colourful illustrations. Medium (англ.). Процитовано 24 січня 2020.
• Introduction to algorithms. Cormen, Thomas H., Cormen, Thomas H. (вид. 2nd). Cambridge, Mass.: MIT Press. 2001. с. 128. ISBN 0-262-03293-7. OCLC 46792720.

Посилання

• Dung X. Nguyen (2003). Binary Tree Structure. rice.edu. Процитовано 28 грудня 2010.
• Binary trees entry in the FindStat database
• Binary Tree Proof by Induction
• Balanced binary search tree on array How to create bottom-up an Ahnentafel list, or a balanced binary search tree on array
• Binary trees and Implementation of the same with working code examples
• Binary Tree JavaScript Implementation with source code