Удаление элемента из двоичного справочника
Рисунок 9. 13. Удаление элемента из двоичного справочника.
line();
Для того, чтобы добавить Х в двоичный справочник Д, необходимо одно из двух:
- добавить Х на место корня дерева (так, что Х станет новым корнем) или
- если корень больше, чем X, то внести Х в левое поддерево, иначе - в правое поддерево.
Трудным моментом здесь является введение Х на место корня. Сформулируем эту операций в виде отношения
добкор( Д, X, X1)
где Х - новый элемент, вставляемый вместо корня в Д, а Д1 - новый справочник с корнем Х. На Рисунок 9.14 показано, как соотносятся X, Д и Д1. Остается вопрос: что из себя представляют поддеревья L1 и L2 (или, соответственно, R1 и R2) на Рисунок 9.14?
Содержание раздела