Page 24 - 4761

К7: Якщо у поточного вузла є права вершина, то зробити її поточною і повернутися
до К3, інакше – до К8.
К8: Створити нову вершину, помістити в неї черговий ідентифікатор, зробити її
правою вершиною поточного вузла і повернутися до К1.

Приклад 2.1. Побудувати бінарне дерево для заданої послідовності ідентифікаторів:
GA, D1, M22, E, A12, BC, F.

Рисунок 2.4 – Покрокове заповнення бінарного дерева

Пошук потрібного елемента в дереві виконується за алгоритмом, подібним до
алгоритму заповнення дерева:
К1: Зробити поточним вузлом кореневу вершину.
К2: Порівняти з поточним елементом шуканий елемент.
К3: Якщо елементи співпадають, то шуканий елемент знайдено і кінець, якщо ні –
то К4 .
К4: Якщо шуканий елемент менший, то перейти на К5, інакше – на К6.
К5: Якщо у поточного вузла є ліва вершина, то зробити її поточним вузлом і
повернутись до К2, інакше – шуканий ідентифікатор не знайдено і кінець.
К6: Якщо у поточного вузла є права вершина, то зробити її поточним вузлом і
повернутися до К2, інакше – шуканий ідентифікатор не знайдено і кінець.
Приклад 2.2 . Знайти ідентифікатор А12 в дереві, що зображено на рисунку 2.4.
Беремо кореневу вершину (вона є поточним вузлом), порівнюємо ідентифікатори
GA i A12. Шуканий елемент є <, тому поточним вузлом стає ліва вершина D1.
Порівнюємо ідентифікатори знову. Шуканий елемент є < , тому поточним вузлом стає ліва
вершина А12. При наступному порівнянні шуканий елемент знайдено.
Приклад 2.3. Якщо шукати відсутній ідентифікатор, наприклад, А11, то пошук
знову піде від кореневої вершини. Порівнюємо ідентифікатори GA i A11. А11 менший,
тому поточним вузлом стає ліва вершина D1. Знову порівнюємо ідентифікатори. А11
менший, тому поточним вузлом стає ліва вершина А12. При наступному порівнянні А11
менший , але ліва вершина у вузла А12 відсутня, тому А11 не знайдено.
Для даного методу число потрібних порівнянь і форма дерева залежить від того
порядку, в якому поступають ідентифікатори. Ця особливість є недоліком даного методу

22