Вставление в двоичный справочник нового элемента в качестве листа

Определим отношение добавить. Простейший способ: ввести новый элемент на самый нижний уровень дерева, так что он станет его листом. Место, на которое помещается новый элемент, выбрать таким образом, чтобы не нарушить упорядоченность дерева. На Рисунок 9.9 показано, какие изменения претерпевает дерево в процессе введения в него новых элементов. Назовем такой метод вставления элемента в множество

        доблист( Д, X, Д1)

Правила добавления элемента на уровне листьев таковы:

• Результат добавления элемента Х к пустому дереву есть дерево дер( nil, X, nil).
• Если Х совпадает с корнем дерева Д, то Д1 = Д (в множестве не допускается дублирования элементов).
• Если корень дерева Д больше, чем X, то Х вносится в левое поддерево дерева Д; если корень меньше, чем X, то Х вносится в правое поддерево.

На Рисунок 9.10 показана соответствующая программа.

Теперь рассмотрим операцию удалить. Лист дерева удалить легко, однако удалить какую-либо внутреннюю вершину - дело не простое. Удаление листа можно на самом деле определить как операцию, обратную