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

Question

Here - один из вариантов метода remove для BST. Цитирую оттуда:

Removing an element from a search tree, although tricky, 
is conceptually straight-forward with one (common) exception: removing the element at a 
    node with two non-null children. In this case, the solution is either: 

removeMax: remove the maximum (rightmost) node from the left subtree 
and replace the root's value with the value of the removed node. 
removeMin: remove the minimum (leftmost) node from the right subtree 
and replace the root's value with the value of the removed node. 

    In either case the search tree's order structure is preserved. 

Если вы посмотрите на это бинарное дерево,

Я хочу удалить 8 и если я выбираю, чтобы выбрать элемент из leftTree, используя removeMax, я выберу 7 в соответствии с выше определения.

, но мне нужно выбрать 13 из right Tree, используя removeMin и чтобы перерыть BST.

Я не понимаю это правильно?

Путь remove работы является получение либо maximum от leftTree или minimum из rightTree и заменить node быть удалены с data.

Answer 1

Несмотря на визуальный внешний вид, самый левый узел правого поддерева сверху равен десяти, а не 13. Достижение 13 требует перемещения справа (от десяти до 14), поэтому 13 не может быть самым левым узлом. Если вы выберете десять, свойство BST не будет нарушено.

правое поддерево имеет три узла - 10, 14 и 13.

10 
    \ 
     \ 
     14 
    /
    13 

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

Что делать, если левый номер 10 не null, но какой-то узел?

Тогда дерево будет выглядеть следующим образом:

10 
/\ 
/ \ 
9  14 
    /
    13 

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

Answer 2

Минимальное значение из правого поддерева 10, а не 13.

Что-то, что может помочь, если вам нужен визуальный мнемоник: минимальное значение правого поддерева является «крайним левым потомком правого ребенка.»