Дерева виразів - студопедія

Мал. 72. Виняток вузлів з дихотомічного дерева

Мал. 71. виродження дихотомічне дерево

Мал. 70. Діхоміческіе дерева

Пошук в дихотомічному дереві вузла з заданим значенням ключа здійснюється на основі порівняння заданого ключа з ключем кореня. Єдине порівняння дозволяє перейти до лівого або до правого піддерева кореня. Якщо дихотомічне дерево є збалансованим, то пошук вузла з заданим значенням ключа вимагає не більше ніж [log2 N] +1 порівнянь, де N - кількість вузлів дихотомічного дерева. В окремому випадку, коли безліч ключів є лінійно впорядкованим, дихотомічне дерево фактично вироджується в лінійний список (рис. 71). У цьому випадку пошук серед N вузлів виконується максимум за N порівнянь, а в середньому - за N / 2 порівнянь.

Структура дихотомічного дерева визначається послідовністю завдання ключів. Послідовності завдання ключів для

¨ дерева рис. а) - 150, 70, 300, 100, 30, 200, 50;

¨ дерева рис. б) - 100, 50, 30, 70, 200, 150, 300;

¨ дерева рис. - 300, 200, 150, 100, 70, 50, 30.

Включення в дихотомічне дерево вузла з заданим значенням ключа проводиться таким чином: якщо пошук вузла привів в глухий кут (тобто до порожнього Піддерево, позначеному посиланням зі значенням NIL), то новий вузол необхідно включити в дерево на місце порожнього поддерева. Таким чином, вузол включається в дихотомічне дерево завжди в якості листа.

Procedure Ins_Node (var root: PDtree;

Якщо кореневий вузол не містить шуканого ключа, процедура рекурсивно викликає саму себе для продовження пошуку або в правій, або в лівій половині дерева. У тому випадку, якщо досягнуто кінець гілки і не виявлений шуканий ключ, створюється новий вузол з цим значенням ключа. Рекурсія закінчується, коли шуканий ключ знайдений (при цьому видається повідомлення про неможливість повторного включення вузла) або досягнутий кінець гілки (при цьому новий вузол включається в дерево).

Який алгоритм обходу лежить в основі процедури включення вузла в дихотомічне дерево?

При построеніідіхотоміческого дерева з N вузлів на кожному з N кроків циклу здійснюється вставка вузла з заданим значенням ключа (виклик процедури Ins_Node). Тому складність створення дихотомічного дерева з N вузлів оцінюється як N * log2 N операцій.

При удаленііузла. із заданим значенням ключа з дихотомічного дерева розрізняють три випадки:

1. вузла з заданим значенням ключа в дереві немає.

2. вузол з заданим значенням ключа має не більше одного нащадка. У цьому випадку виключається вузол замінюється своїм нащадком.

3. Вузол з заданим значенням ключа має двох нащадків. У цьому випадку виключається вузол замінюється або на самий правий вузол його лівого піддерева. має не більше одного нащадка, або на самий лівий вузол його правого піддерева. має не більше одного нащадка.

Приклад виключення вузлів з дихотомічного дерева наведено на рис. 72.

Руйнування бінарного дерева будь-якого виду полягає в послідовному звільнення ділянок пам'яті, в яких розміщені елементи зберігання вузлів з поверненням їх в купу. В результаті руйнування дерево стає порожнім.

Який алгоритм обходу необхідно використовувати для руйнування бінарного дерева?

Дерево виразів - бінарне дерево, в кореневих вузлах якого зберігаються ознаки операцій, а в термінальних вузлах - операнди виразу (змінні або константи). Дерево виразів представлено на рис. 73.