Удаление в двоичном дереве поиска

Мы обсудили операции поиска и вставки BST. В этом посте обсуждается операция удаления. Когда мы удаляем узел, возникают три возможности.

1) Удаляемый узел — это лист: просто удалите его из дерева.

              50                                      50
            /             delete(20)          /  
         30      70       ———>      30     70 
         /      /                                       /   
     20   40  60   80                        40  60   80

2) У удаляемого узла есть только один дочерний элемент: скопируйте дочерний элемент в узел и удалите дочерний элемент.

              50                                   50
           /             delete(30)        /  
        30      70       ———>    40     70 
               /                                      /   
         40  60   80                            60   80

3) У узла, который нужно удалить, есть два потомка: Найдите неупорядоченный преемник узла. Скопируйте содержимое неупорядоченного преемника в узел и удалите неупорядоченного преемника.

Примечание. Можно также использовать предшественник в порядке убывания.

              50                                    60
           /              delete(50)        /  
        40      70       ———>     40    70 
                 /                                         
              60   80                                   80

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

Выполните следующие шаги, чтобы решить проблему:

• Если корень равен NULL, верните корень (базовый случай)
• Если ключ меньше значения корня, то установите root->left = deleteNode(root->left, key)
• Если ключ больше значения корня, то установите root->right = deleteNode(root->right, key)
• В противном случае проверьте
  • Если корень является листовым узлом, верните null
  • иначе, если у него есть только левый дочерний элемент, верните левого дочернего элемента
  • иначе, если у него есть только правильный дочерний элемент, верните правильный дочерний элемент
  • иначе установите значение root как его неупорядоченный преемник и повторите удаление узла со значением неупорядоченного преемника
• Возвращаться

Ниже приведена реализация вышеуказанного подхода:

Иллюстрация:

Временная сложность: O (log N)
Вспомогательное пространство: O (log N), пространство, используемое для стека рекурсии

Примечание. Приведенный выше подход может быть оптимизирован для двух дочерних случаев:

We recursively call delete() for the successor in the above recursive code. We can avoid recursive calls by keeping track of the parent node of the successor so that we can simply remove the successor by making the child of a parent NULL. We know that the successor would always be a leaf node.

Ниже приведена реализация вышеуказанного подхода:

Спасибо wolffgang010 за предложенную выше оптимизацию.

Ссылки по теме:

• Введение в двоичное дерево поиска, поиск и вставка
• Викторина по двоичному дереву поиска
• Практика кодирования на BST
• Все статьи о BST