Двоичное дерево поиска - удаление узла

Question

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

Почему бы просто не взять удаляемый узел левым потомком, если он есть? Это все еще работает правильно?

Или я что-то пропустил.

Я читаю эту статью.

Answer 1

Вы упрощаете.

Узел, выбранный для замены удаленного, должен быть больше всех узлов слева от удаленного и меньше всех узлов справа. Таким образом, это должен быть либо самый правый потомок левого поддерева, либо самый левый потомок правого поддерева; за исключением случаев, когда одно или другое поддерево полностью отсутствует, мы можем полностью удалить уровень дерева, просто заменив удаленный узел дочерним, который присутствовал.

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

Это не "работает правильно", чтобы просто всегда использовать левого ребенка. В самом деле, если справа есть ребенок, а у самого левого ребенка есть два ребенка, это невозможно сделать даже без существенного восстановления дерева.

Answer 2

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

   2
 /  \
1    6
    / \
   4   7
    \
     5  

Допустим, вы хотели переместить узел 6, теперь, следуя вашим инструкциям, мы заменим его левым дочерним узлом 4. Теперь, что мы будем делать с узлом 5? Мы могли бы сделать его левым потомком узла 7 (или самым левым потомком узла 7, если он существовал), но зачем вам делать все эти перестановки, когда вы знаете, что удаление листа тривиально и вы просто хотите заменить узел другим узлом, который будет держать каждый узел слева меньше, а каждый узел справа больше.