Page 49 - 6110

Таке структурування дозволяє надрукувати усі значення у
зростаючому порядку за допомогою простого алгоритма
центрованого обходу дерева. Бінарні дерева пошуку набагато
ефективніші в операціях пошуку, аніж лінійні структури, в яких
витрати часу на пошук пропорційні Т(n), де n – це розмір масиву
даних, тоді як в повному бінарному дереві цей час пропорційний в
середньому Т(log 2n) або Т(h), де h - висота дерева (хоча гарантувати,
що h не перевищує log 2n можна лише для збалансованих дерев, які є
ефективнішими при пошукових алгоритмах, ніж прості бінарні
дерева пошуку).
Процедура пошуку в бінарному дереві отримує на вході
значення k, яке необхідно знайти, та вказівник x на корень того
піддерева, в якому слід шукати.
SEARCH (x, k)
1 if x = NULL or k = val[x]
2 then return x
3 if k < val[x]
4 then return SEARCH (left[x], k)
5 else return SEARCH (right[x], k)
В процесі пошуку ми рухаємось від кореня, порівнюючи
значення k зі значенням в поточній вершині х. Якщо k < val[x],
пошук рекурсивно продовжується в лівому піддереві (k може бути
тільки там згідно умови впорядкованості), інакше - у правому
піддереві. Очевидно, що довжина шляху не перевищує висоти
дерева, тому час пошуку є Т(h), де h - висота дерева.
Мінімальний елемент в дереві можна знайти, розглянувши
послідовно ліве піддерево left[x]:
MINIMUM (x)
1 while left[x]<>NULL
2 do x:=left[x]
3 return x
Процедура знаходження максимуму симетрична. Обидві
процедури знову ж таки знаходять елемент за час, пропорційний
Т(h)
Елемент, що є наступним за даним (в сенсі відношення
впорядкованості) можна знайти за допомогою такої процедури:
SUCCESSOR (x)
1 if right[x] <> NULL
2 then return MINIMUM (right[x])
3 y:=p[x]
4 while y<>NULL and x = right[y]
5 do x:=y
6 y:=p[y]
7 return y
48