Двійкове дерево
.png)
У програмуванні двійкове дерево — структура даних у вигляді дерева, в якому кожна вершина має не більше двох дітей. Зазвичай такі діти називаються правим та лівим. На базі двійкових дерев будуються такі структури, як двійкові дерева пошуку та двійкові купи.
- Двійкове дерево — таке кореневе дерево, в якому кожна вершина має не більше двох дітей.
- Повне (закінчене) двійкове дерево — таке двійкове дерево, в якому кожна вершина має нуль або двох дітей.
- Ідеальне двійкове дерево — це таке повне двійкове дерево, в якому листя (вершини без дітей) лежать на однаковій глибині (відстані від кореня).
Двійкове дерево на кожному n-му рівні має від 1 до 2n вершин.
Часто виникає необхідність обійти усі вершини дерева для аналізу інформації, що в них знаходиться. Існують декілька порядків такого обходу, кожний з яких має певні властивості, важливі в тих чи інших алгоритмах: прямий (preorder), центрований (inorder) та зворотний (postorder).
Залежно від задач, які вирішуються цими структурами та можливостей тої чи іншої мови програмування, існує декілька варіантів конструювання двійкових дерев.
Реалізація з використанням вказівників передбачає зберігання в кожній вершині дерева x, разом із даними власне цієї вершини, також двох полів — правого та лівого (right[x] та left[x]), які містять вказівники на відповідних дітей цієї вершини.
Також іноді додається вказівник p[x] на батьківську вершину. Це спрощує деякі алгоритми та виявляється корисним, коли необхідно забезпечити швидкий доступ до батьківської вершини. Іноді достатньо тільки вказівника на батьківську вершину. Взагалі будь-яке орієнтоване дерево можна описати, знаючи тільки зв'язки від дітей до батьківської вершини.
Деякі різновиди двійкових дерев (наприклад, червоно-чорні дерева або AVL-дерева), вимагають збереження в вершинах і деякої додаткової інформації. Якщо у вершини відсутня одна чи обидві дитини, відповідні вказівники ініціалізуються спеціальними «пустими» значеннями.
Двійкові дерева також можуть бути побудовані на базі масивів. Такий метод набагато ефективніший щодо економії пам'яті. В такому представленні, якщо вершина має порядковий номер i, то її діти знаходяться за індексами 2i+1 та 2i+2, а батьківська вершина за індексом ((i-1)/2) (за умов, що коренева вершина має індекс 0).
Інший варіант зберігання дерева в масиві — зберігати індекси дітей.
Існує єдине та взаємооднозначне відображення довільного впорядкованого дерева в двійкове.
Для цього слід послідовно зв'язати усіх дітей кожної сім'ї з першою дитиною та видалити усі вертикальні з'єднання за виключенням з'єднання батька з першою дитиною в сім'ї. Тобто кожна вершина 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.
- 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
|
Це незавершена стаття про структури даних. Ви можете допомогти проєкту, виправивши або дописавши її. |
