Исключает удаление из дерева двоичного поиска?

Question

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

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

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

Answer 1

Это неверно. Рассмотрим дерево

4 
/\ 
1 5 
\ 
    2 
    \ 
    3 , 

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

1 
\ 
    2 
    \ 
    3 . 

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

3 
/
1 
\ 
    2 , 

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

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