Page 48 - 6110

Інший варіант збереження дерева в масиві – це збереження
індексів дітей.
Існує єдине та взаємооднозначне відображення довільного
впорядкованого дерева в бінарне (рис.11.5).
Для цього слід послідовно зв'язати усіх дітей кожної сім'ї з
першою дитиною та видалити усі вертикальні з'єднання за
виключенням з'єднання батька з першою дитиною в сім'ї. Тобто
кожна вершина N впорядкованого дерева відповідає вершині M
деякого бінарного дерева. Ліва дитина вершини M відповідає
першій дитині вершини N, а права дитина M відповідає першому з
наступних братів N (тобто першому з наступних дітей батька
вершини N).
Така відповідність має назву природної відповідності між
впорядкованим та бінарним деревом.

Рисунок 11.5 – Відображення довільного впорядкованого дерева в
бінарне

Бінáрне дéрево пóшуку (BST: binary search tree) в інформатиці
– це бінарне дерево, в якому кожній вершині x співставлене певне
значення val[x]. При цьому такі значення повинні задовольняти
умові впорядкованості:
- нехай x – це довільна вершина бінарного дерева пошуку.
Якщо вершина y знаходиться в лівомі піддереві вершини x,
то val[y] ≤ val[x]. Якщо у знаходиться у правому піддереві x,
то val[y] ≥ val[x].

47