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). Ця операція також потребує часу для виконання, пропорційного O (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]

6 else x: = right [y]

7 if x <> NULL

8 then p [x]: =p [y]

9 if p [y]: =NULL

10 then root [T]: =x

11 else if y=left [p [y]]

12 then left [p [y]]: =x

13 else right [p [y]]: =x

14 if y <> z

15 then val [z]: =val [y]

16 // копіювання додаткових даних з y

17 return y

Відкриття програми