При удалении узла с двумя дочерними элементами вы можете выбрать его преемный узел по порядку или предшествующий узел по порядку. В этом случае он находит наибольшее значение в левом поддереве (что означает самый правый дочерний элемент его левого поддерева), что означает, что он находит узел предшественника по порядку узла.
Найдя заменяющий узел, вы на самом деле не удаляете удаляемый узел. Вместо этого вы берете значение из узла-преемника и сохраняете это значение в узле, который хотите удалить. Затем вы удаляете узел-преемник. При этом вы сохраняете двоичное свойство дерева поиска, поскольку вы можете быть уверены, что у выбранного вами узла будет значение, которое меньше значений всех дочерних элементов в левом поддереве исходного узла и больше, чем значения всех дочерних элементов в правом поддереве исходного узла.
EDIT
Прочитав ваш вопрос немного больше, я думаю, что нашел проблему.
Обычно, помимо функции delete, у вас есть функция replace, которая заменяет рассматриваемый узел. Я думаю, вам нужно изменить эту строку кода:
FindParent(largestValue).Right <- 0
до:
FindParent(largestValue).Right <- largestValue.Left
Если у узла largestValue нет левого потомка, вы просто получаете null или 0. Если у него есть левый дочерний элемент, этот дочерний элемент становится заменой для узла largestValue. Так ты прав; код не учитывает сценарий, что у узла largestValue может быть левый потомок.
Другая редакция
Поскольку вы только опубликовали фрагмент, я не уверен, каков контекст кода. Но приведенный фрагмент, похоже, имеет проблему, которую вы предлагаете (замена неправильного узла). Обычно есть три случая, но я замечаю, что комментарий в вашем фрагменте говорит //Case 4 (так что, возможно, есть какой-то другой контекст).
Ранее я упоминал о том, что delete обычно идет с replace. Поэтому, если вы найдете узел largestValue, вы удалите его в соответствии с двумя простыми случаями (узел без дочерних элементов и узел с одним дочерним элементом). Поэтому, если вы смотрите на псевдокод для удаления узла с двумя дочерними элементами, вы будете делать следующее:
get largestValue from nodeToRemove.Left
nodeToRemove.Value <- largestValue.Value
//now replace largestValue with largestValue.Left
if largestValue = largestValue.Parent.Left then
largestValue.Parent.Left <- largestValue.Left //is largestValue a left child?
else //largestValue must be a right child
largestValue.Parent.Right <- largestValue.Left
if largestValue.Left is not null then
largestValue.Left.Parent <- largestValue.Parent
Мне кажется странным, что в книге «Структуры данных и алгоритмы» эта часть будет пропущена, поэтому я склонен думать, что книга еще больше разделила удаление на еще несколько случаев (поскольку существует три стандартных случая), чтобы сделать это легче понять.
Чтобы доказать, что приведенный выше код работает, рассмотрим следующее дерево:
8
/ \
7 9
Допустим, вы хотите удалить 8. Вы пытаетесь найти largestValue из nodeToRemove.Left. Это дает вам 7, поскольку у левого поддерева есть только один дочерний элемент.
Тогда вы делаете:
nodeToRemove.Value <- largestValue.Value
Что означает:
8.value <- 7.Value
или
8.Value <- 7
Итак, теперь ваше дерево выглядит так:
7
/ \
7 9
Вам нужно избавиться от узла замены, и вы собираетесь заменить largestValue на largestValue.Left (что составляет null). Итак, сначала вы узнаете, что за ребенок 7:
if largestValue = largestValue.Parent.Left then
Что означает:
if 7 = 7.Parent.Left then
или
if 7 = 8.Left then
Поскольку 7 является 8 левым ребенком, необходимо заменить 8.Left на 7.Right (largestValue.Parent.Left <- largestValue.Left). Так как 7 не имеет детей, 7.Left является нулевым. Таким образом, largestValue.Parent.Left получает значение null (что эффективно удаляет его левого потомка). Таким образом, это означает, что вы получите следующее дерево:
7
\
9