End; writeln; end end.

В функцию del передаются указатель root на корень дерева и ключ key удаляемого элемента. С помощью функции find определяются указатели на удаляемый элемент p и его предка parent. Если искомого элемента в дереве нет, то выдается сообщение ({6}).

В операторах {7}-{9} определяется указатель на узел y, который должен заменить удаляемый. Если у узла p нет левого поддерева, на его место будет поставлена вершина (возможно пустая) его правого поддерева ({7}).

Иначе, если у узла p нет правого поддерева, на его место будет поставлена вершина его левого поддерева ({8}).

В противном случае, когда оба поддерева существуют, для определения замещающего узла вызывается функция spusk, выполняющая спуск по дереву ({9}).

В этой функции первым делом проверяется особый случай, описанный выше ({1}). Если же этот случай (отсутствие левого потомка у правого потомка удаляемого узла) не выполняется, организуется цикл ({2}), на каждой итерации которого указатель на текущий элемент запоминается в переменной pred, а указатель y смещается вниз и влево до того момента, пока не станет ссылаться на узел, не имеющий левого потомка (он-то нам и нужен).

В операторе {3} к этой пустующей ссылке присоединяется левое поддерево удаляемого узла. Перед тем как присоединять к этому узлу правое поддерево удаляемого узла ({5}), требуется «пристроить» его собственное правое поддерево. Мы присоединяем его к левому поддереву предка узла y, заменяющего удаляемый ({4}), поскольку этот узел перейдет на новое место.

Функция spusk возвращает указатель на узел, заменяющий удаляемый. Если мы удаляем корень дерева, надо обновить указатель на корень ({10}), иначе – присоединить этот указатель к соответствующему поддереву предка удаляемого узла ({11}).

После того как узел удален из дерева, освобождается занимаемая им память ({12}).