Процедура удаления Дерева двоичного поиска

Я отвечаю на второе обновление Вивин.

Я думаю, что это хорошая переделка вопроса:

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

но это жирное предложение ниже неверно:

Когда вы удаляете узел (скажем, A), вы проходите правое поддерево, чтобы найти минимальный элемент. Этот узел будет листовым узлом и никогда не может быть равным B

, поскольку минимальный элемент в правом поддереве A может иметь правого дочернего элемента . Итак, это не лист. Назовем минимальный элемент в правом поддереве A преемником (A) . Теперь верно, что B не может быть преемником (A) , но может находиться в своем правом поддереве. Итак, это беспорядок.

Я пытаюсь подвести итог.

Гипотеза :

1. У A и B по два ребенка.
2. A и B находятся в одном поддереве.

Другой материал , который мы можем вывести из гипотезы:

1. B не является преемником (A) , ни A не является преемником (B) .

Теперь, учитывая это, я думаю, что есть 4 разных случая (как обычно, пусть A является предком B):

1. B находится в левом поддереве A
2. B является предком преемника ( A)
3. наследник (A) является предком B
4. B, а наследник (A) не имеют никаких отношений. (они находятся в разных поддеревьях A)

Я думаю (но, конечно, я не могу это доказать), что случаи 1, 2 и 4 не имеют значения. Таким образом, только в случае, если наследник (A) является предком B, процедура удаления не может быть коммутативной. Или может?

Я передаю мяч :)

С уважением.

Удаление (в общем случае) не коммутативно. Вот контрпример:

    4
   / \
  3   7
     /
    6

Что если мы удалим 4, а затем 3?

Когда мы удалим 4, мы получим 6 в качестве нового корня:

   6
  / \
 3   7

Удаление 3 не изменит дерево, но даст нам следующее:

  6
   \
    7

Что если мы удалим 3, а затем 4?

Когда мы удалим 3, дерево не изменится:

 4
  \
   7
  /
 6

Однако, когда мы теперь удалим 4, новым корнем станет 7:

  7
 /
6

Два получившихся дерева не одинаковы, поэтому удаление не коммутативно.

UPDATE

Я не прочитал ограничение, что это когда вы всегда удаляете узел с двумя детьми. Мое решение предназначено для общего случая. Я обновлю его, если/когда смогу найти контрпример.

ОБНОВЛЕНИЕ

У меня нет конкретных доказательств, но я рискну предположить:

В общем случае вы по-разному обрабатываете удаление в зависимости от того, есть ли у вас два ребенка, один ребенок или нет детей. В контрпримере, который я привел, я сначала удаляю узел с двумя детьми, а затем узел с одним ребенком. После этого я удаляю узел без детей, а затем еще один узел с одним ребенком.

В особом случае удаления только узлов с двумя детьми, вы хотите рассмотреть случай, когда оба узла находятся в одном поддереве (поскольку не имеет значения, если они находятся в разных поддеревьях; вы можете быть уверены, что общая структура не изменится в зависимости от порядка удаления). На самом деле нужно доказать, имеет ли значение порядок удаления узлов в одном и том же поддереве, где каждый узел имеет двух детей.

Рассмотрим два узла A и B, где A является предком B. Тогда вы можете уточнить вопрос следующим образом:

Является ли удаление коммутативным, когда вы рассматриваете удаление двух узлов из дерева бинарного поиска, которые имеют отношения предок-потомок друг с другом (это подразумевает, что они находятся в одном поддереве)?

Когда вы удаляете узел (допустим, A), вы обходите правое поддерево, чтобы найти минимальный элемент. Этот узел будет листовым узлом и никогда не может быть равен B (потому что B имеет двух детей и не может быть листовым узлом). Затем вы замените значение A значением этого листового узла. Это означает, что единственным структурным изменением дерева является замена значения A значением узла-листа и потеря узла-листа.

Тот же самый процесс происходит и для B. То есть, вы заменяете значение узла и заменяете узел-лист. Поэтому в общем случае, когда вы удаляете узел с двумя дочерними узлами, единственным структурным изменением является изменение значения удаляемого узла и удаление листового узла, значение которого вы используете в качестве замены.

Итак, вопрос уточняется:

Можете ли вы гарантировать, что всегда будете получать один и тот же заменяющий узел независимо от порядка удаления (когда вы всегда удаляете узел с двумя дочерними узлами)?

Ответ (я думаю) - да. Почему? Вот несколько наблюдений:

• Допустим, вы удаляете сначала узел-потомок, а затем узел-предок. Поддерево, которое было изменено при удалении узла-потомка, не находится в левом поддереве правого дочернего узла предка. Это означает, что это поддерево остается незатронутым. Это также означает, что независимо от порядка удаления изменяются два разных поддерева, и поэтому операция является коммутативной.
• Опять же, допустим, вы удаляете сначала узел-потомок, а затем узел-предок. Поддерево, которое было изменено при удалении узла-потомка, находится в левом поддереве правого дочернего узла предка. Но даже здесь нет перекрытия. Причина в том, что когда вы сначала удаляете узел-потомок, вы просматриваете левое поддерево правого дочернего узла is узла-потомка. Когда вы затем удаляете узел-предок, вы никогда не спуститесь вниз по этому поддереву, поскольку вы всегда будете двигаться влево после того, как войдете в левое поддерево правого дочернего узла предка. Таким образом, опять же, независимо от того, что вы удаляете первым, вы изменяете разные поддеревья, и поэтому порядок не имеет значения.
• Другой случай - если вы сначала удалите узел-предок и обнаружите, что минимальный узел является дочерним узлом узла-потомка. Это означает, что узел-потомок в итоге будет иметь одного ребенка, и удаление этого одного ребенка тривиально. Теперь рассмотрим случай, когда в этом сценарии вы сначала удалили узел-потомок. Затем вы заменили бы значение узла-потомка на его правого ребенка, а затем удалили бы правого ребенка. Затем, когда вы удаляете узел-предок, вы в итоге находите тот же самый минимальный узел (левый ребенок старого удаленного узла, который также является левым ребенком замененного узла). В любом случае, в итоге вы получите одну и ту же структуру.

Это не строгое доказательство; это просто некоторые наблюдения, которые я сделал. Не стесняйтесь указывать на дыры!