том. p align="justify"> Схематичне зображення бінарного дерева представлено на малюнку 1:
В
Рисунок 1 - Схематичне зображення бінарного дерева
Бінарне дерево може виродитися в список, представлений на малюнку 2:
В
Рисунок 2 - Схематичне зображення списку
Особливість структури таких дерев виявляється в тому, що вона явно реалізує методи бінарного пошуку, тому що кожен вузол дерева має 2 покажчика, тобто 2 альтернативи шляху пошуку. Якщо шуканий ключ більше, ніж ключ вершини, то подальший пошук здійснюється по правому піддерев, в іншому випадку по лівому. На відміну від бінарного пошуку в послідовному списку, в бінарному дереві не потрібно ніяких обчислень подальшого шляху пошуку. p align="justify"> Строго двійковим деревом називається дерево, у якого кожна внутрішня вершина має непусті ліве і праве піддерева. Це означає, що в строго довічним дереві немає вершин, у яких є тільки одне піддерево. p align="justify"> Повним двійковим деревом називається дерево, у якого все листя знаходяться на одному рівні і кожна внутрішня вершина має непусті ліве і праве піддерева, [1].
1.2 Впорядковане двійкове дерево і його властивості
впорядкування називають таке дерево, в якому впорядковані всі нащадки кожної вершини. Прийнято вважати, що на діаграмі дерева зображуються так, щоб всі нащадки були впорядковані зліва направо. Двійкове (бінарне) дерево можна визначити як упорядковане дерево, кожна вершина якого має не більше двох нащадків, причому кожен з нащадків вважається або лівим, або правим нащадком свого батька. Піддерево, корінь якого знаходиться в лівому (правому) нащадку вершини, називається лівим (правим) піддерево цієї вершини. p align="justify"> Двійкове дерево впорядковано, якщо для будь-якої його вершини x справедливі такі властивості:
) всі елементи в лівому поддереве менше елемента, що зберігається в x;
) всі елементи в правому поддереве більше елемента, що зберігається в x;
) всі елементи дерева різні, [3].
Приклад упорядкованого двійкового дерева представлений на малюнку 3:
В
Рисунок 3 - Впорядковане двійкове дерево
Якщо в дереві виконуються перші дві властивості, але зустрічаються однакові елементи, то таке дерево є частково впорядкованим. Основними операціями, що здійснюються з упорядкованим деревом, є:
) пошук вершини;
) додавання вершини;
) видалення вершини;
) висновок (друк) дерева;
) очищення дерева, [2].
2. Двійкові дерева пошуку
Дерева пошуку - приватний, але практично, мабуть, найбільш важливий вид двійкових дер...
