Двійкове дерево
.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 впорядкованого n-арного дерева відповідає вершині M деякого двійкового дерева. Ліва дитина вершини M відповідає першій дитині вершини N, а права дитина M відповідає першому з наступних братів N (тобто першому з наступних дітей батька вершини N).
Така відповідність має назву природної відповідності між n-арним та двійковим деревом.
Див. також [ред.]
- Двійкове дерево пошуку
- Збалансоване дерево
- AVL-дерево
- B-дерево
- Червоно-чорне дерево
- Префіксне дерево
- Список структур даних
 |
Ця стаття не містить посилань на джерела. (січень 2009) |
