Удаление элемента из двоичного справочника



Рисунок 9. 13.  Удаление элемента из двоичного справочника.

line();

Для того, чтобы добавить Х в двоичный справочник Д, необходимо одно из двух:

  • добавить Х на место корня дерева (так, что Х станет новым корнем) или
  • если корень больше, чем X, то внести Х в левое поддерево, иначе - в правое поддерево.
line();

Трудным моментом здесь является введение Х на место корня. Сформулируем эту операций в виде отношения

        добкор( Д, X, X1)

где Х - новый элемент, вставляемый вместо корня в Д, а Д1 - новый справочник с корнем Х. На Рисунок 9.14 показано, как соотносятся X, Д и Д1. Остается вопрос: что из себя представляют поддеревья L1 и L2 (или, соответственно, R1 и R2) на Рисунок 9.14?



Содержание раздела