Page 47 - 6110
P. 47
Рисунок 11.3 – Реалізація бінарного дерева з використанням
вказівників
Модифікована реалізація бінарного дерева. Кожна вершина
містить також вказівник на батьківську вершину
Також іноді додається вказівник p[x] на батьківську вершину.
Це виявляється корисним, коли необхідний швидкий доступ до
батьківської вершини, що спрощує деякі алгоритми. Іноді достатньо
тільки вказівника на батьківську вершину. Взагалі будь-яке
орієнтоване дерево можна описати, знаючи тільки зв'язки від дітей
до батьківської вершини. Деякі різновиди бінарних дерев
(наприклад, червоно-чорні дерева або AVL-дерева), вимагають
збереження в вершинах і деякої додаткової інформації. Якщо у
вершини відсутня одна чи обидві дитини, відповідні вказівники
ініціалізуються спеціальними “порожніми” значеннями.
Бінарні дерева також можуть бути побудовані на базі масивів
(рис.11.4). Такий метод набагато ефективніший щодо економії
пам'яті. В такому представленні, якщо вершина має порядковий
номер i, то її діти знаходяться за індексами 2i+1 та 2i+2, а
батьківська вершина за індексом ((i-1)/2) (за умов, що коренева
вершина має індекс 0).
Рисунок 11.4 – Бінарні дерево побудоване на базі масиву
46
