Контрольная работа: Моделі та структури даних

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 може бути тільки там згідно умови впорядкованості), інакше - у правому піддереві. Очевидно, що довжина шляху не перевищує висоти дерева, тому час пошуку є O (h), де h - висота дерева.

Мінімум, максимум, наступник та попередник.

Мінімальний елемент в дереві можна знайти, розглянувши послідовно ліве піддерево left [x]:

MINIMUM (x)

1 while left [x] <>NULL

2 do x: =left [x]

3 return x

Процедура знаходження максимуму симетрична. Обидві процедури знову ж таки знаходять елемент за час, пропорційний O (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

Процедура знаходження попереднього даному елемента є симетричною. Обидві процедури знову ж таки знаходять елемент за час, пропорційний O (h)

Додавання елементу.

Процедура додавання елементу в бінарне дерево T додає елемент, зберігаючи умову впорядкованості.

Параметром тут є вказівник z на нову вершину, в яку поміщене значення val [z], left [z] =right [z] =NULL.

INSERT (T, z)

1 y: =NIL

2 x: =root [T]

3 while x <> NULL

4 do y: =x