Является ли удаление из двоичного дерева поиска симметричным?

Если я удалю узел x, а затем узел y или удалю y и x, после удаления я останусь с тем же двоичным деревом поиска?

Я попробовал несколько примеров, и я думаю, что это правда.

Но как я могу это доказать?


algorithm data-structures binary-search-tree
person mohamad rabee    schedule 07.09.2014    source источник
comment
Вы храните значения во внутренних узлах или только в листьях?   -  person rob mayoff    schedule 07.09.2014
comment
у меня есть значение во всех узлах   -  person mohamad rabee    schedule 07.09.2014

Ответы (1)


arrow_upward
1
arrow_downward

Это ложь. Рассмотрим дерево

  4
 / \
1   5
 \
  2
   \
    3 ,

из которых 4 и 5 удаляются в некотором порядке. Если порядок 5, то 4, результат

1
 \
  2
   \
    3 .

Если порядок 4, затем 5, результат может быть

  3
 /
1
 \
  2 ,

предполагая, что когда мы удаляем узел с двумя дочерними элементами, мы вместо этого заменяем его значение значением его предшественника в порядке и удаляем предшественника. (Я предполагаю также стандартную процедуру удаления для узлов с нулевым и одним дочерним элементом.)

Хотя я нашел этот пример вручную, я часто обращаюсь за помощью к компьютеру.

person David Eisenstat    schedule 07.09.2014