Page 50 - 6110

Процедура знаходження попереднього даному елементу є
симетричною. Обидві процедури знову ж таки знаходять елемент за
час, пропорційний Т(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
5 if val[z] < val[x]
6 then x:=left[x]
7 else x:=right[x]
8 p[z]:=NULL
9 if y = NULL
10 then root[T] :=z
11 else if val[z]<val[y]
12 then left[y]:=z
13 else right[y]:=z
Процедура рухається вниз по дереву, при цьому зберігаючи в y
вказівник на батька вершини x. Порівнюючи значення в x та z,
процедура вирішує, в яке з піддерев рухатись далі. Процес
завершується тоді, коли x=NULL. Саме сюди й слід помістити
вершину z (рядки 8-13). Ця операція також потребує часу для
виконання, пропорційного Т(h)
Параметром для процедури видалення елементу є вказівник на
вершину, що видаляється. Тут можливі три варіанти дій:
- якщо у вершини немає дітей, достатньо помістити NULL у
відповідне поле його батька (замість вказівника на вершину, що
видаляється);
- якщо у вершини є одна дитина, можна з'єднати батька цієї
вершини безпосередньо з її дитиною;
- якщо вершина має двох дітей, слід спочатку знайти слідуючий
(в сенсі порядку) елемент y, в якого немає лівої дитини, а потім
скопіювати значення та додаткові дані з вершини y на місце
вершини, що видаляється, а саму вершину y видалити:
DELETE (T, z)
1 if left[z] = NULL or right[z]=NULL
2 then y:=z
3 else y:=SUCCESSOR(z)
4 if left[y] <> NULL
5 then x:=left[y]
49