Удаление узла в дереве двоичного поиска

Question

У меня есть BST, который выглядит так: Я пытаюсь удалить узел 12 (у которого 2 ребенка), Мне интересно, удаляю ли я его правильно?

Перед удалением

  12 
     _/ \_ 
    5   18 
/ \ / \ 
=  = 15  19 
2  9 /\  
      13 17 

После удаления:

  18 
     _/ \_ 
    5   19 
/ \ / 
=  = 15  
2  9 /\  
      13 17 

это моя реализация правильно здесь? Спасибо.

EDIT ОБНОВЛЕНО ПОСЛЕ УДАЛЕНИЯ:

  13 
     _/ \_ 
    5   18 
/ \ / \ 
=  = 15  19 
2  9  \  
       17 

Answer 1

Давайте рассмотрим простой пример.

Рассмотрим это дерево:

A 
/\ 
B C 

Для удаления, выполните следующие действия:

1. Выберите либо B или C в качестве замены, вы продвигаете этот узел до занять место А.
2. Возьмите другой подузел (B или C) и подключить его в первый (в или с)
   • Если вы выбрали B, как repla цемент для A, вам необходимо подключить C в B, как его новый крайний левый подузел
   • Если вы выбрали C в качестве замены A, вам необходимо подключить B в C в качестве нового крайнего правого подузла

Под «левым/правым субнодом» я подразумеваю, что вам нужно перемещаться вниз в левом или правом направлении, пока у вас есть подузлы в этом направлении, а затем, когда вы приходите к узлу без левого/правого поднода (в соответствии с каким направлением вы «переходите»), подключите «другой узел» к нему в качестве своего нового поднабора в этом направлении.

Рассмотрим собирание В первой, вы бы в конечном итоге с этим:

B 
    \ 
    ... 
     \ 
     C 

Если вы выбираете C первых, вы бы в конечном итоге с этим:

 C 
    /
    ... 
/
B 

Так назад в дерево, который начинался как это:

 12 
    / \ 
    5  18 
    /\ /\ 
    2 9 15 19 
     /\ 
     13 17 

для удаления 12, и вы выбрали 18, чтобы заменить его, сначала продвигать 18:

 5  18 
    /\ /\ 
    2 9 15 19 
     /\ 
     13 17 

Тогда, поскольку 18 соответствует C в моем предыдущем примере, вам нужно будет подключить 5 в 18 в качестве крайнего левого поддерева, давая вам это последнее дерево:

 18 
    /\ 
     15 19 
    /\ 
    13 17 
/
    5 
/\ 
2 9 

Давайте посмотрим на то, что бы «ве, если бы мы выбрали 5 заменить 12 вместо:

способствуют 5:

 5  18 
    /\ /\ 
    2 9 15 19 
     /\ 
     13 17 

Тогда крючок 18 на 5 в качестве нового правого правого поддерева:

5 
/\ 
    2 9 
     \ 
     18 
    /\ 
     15 19 
    /\ 
    13 17 

Любое было бы в порядке. Вероятно, есть дополнительная информация о Wikipedia page, которая была бы полезной для чтения.