Общая стратегия удаления узла Z из бинарного дерева поиска T имеет три основных случая, но один из них немного сложен.

  1. Если у Z нет дочерних элементов, мы просто удаляем его, изменяя его родителя, заменяя Z на NIL в качестве дочернего элемента.
  2. Если у Z есть только один дочерний элемент, то мы повышаем уровень этого дочернего элемента, чтобы он занял позицию Z в дереве, модифицируя родителя Z, заменяя Z дочерним элементом Z.
  3. Если Z имеет двух потомков, то мы находим узел-преемник Z Y, который должен находиться в правом поддереве Z, и заставляем Y занимать позицию Z в дереве. Остальная часть исходного правого поддерева Z становится новым правым поддеревом Y, а левое поддерево Z становится новым левым поддеревом Y. Этот случай сложен, потому что, как мы увидим, имеет значение, является ли y правым потомком Z.

Процедура удаления данного узла Z из BST принимает в качестве аргументов указатель на узел и Z. Она организует свои случаи немного иначе, чем три описанных выше случая, рассматривая четыре случая:

  1. Если у Z нет левого дочернего элемента (рис. 1), то мы заменяем Z его правым дочерним элементом, который может быть или не быть NIL. Когда правым потомком Z является NIL, этот случай имеет дело с ситуацией, в которой у Z нет детей. Когда правый дочерний элемент Z не равен нулю, этот случай обрабатывает ситуацию, в которой Z имеет только одного дочернего элемента, который является правильным дочерним элементом.

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

3. В противном случае у Z есть и левый, и правый потомок. Мы находим преемника Z Y, лежащего в правом поддереве Z. Мы хотим соединить Y из его текущего местоположения и заменить Z в дереве.

3.1: Если Y — правый потомок Z (рис. 3), то мы заменяем Z на Y, оставляя правого потомка Y в покое.

3.2: В противном случае Y лежит в правом поддереве Z, но не является правым потомком Z (рис. 4). В этом случае мы сначала заменяем Y его собственным правым дочерним элементом, а затем заменяем Z на Y.

Анализ:

  1. Время выполнения Tree-Delete на дереве высотой h равно O(h), так как мы идем по простому пути вниз по дереву.
  2. Плюс время работы, чтобы найти преемника в дереве, занимает O (h), так как мы либо идем по простому пути вверх по дереву, либо идем по простому пути вниз по дереву.

3. O(1) постоянное время для фактического удаления узла.

Код:

Структура узла:

struct node
{
  int key;
  node *left;
  node *right;
  node *parent;
  
  node (int key)
  {
     this->key = key;
     left = right = nullptr;
     parent = nullptr;
  }
};

Преемник дерева:

node* find_min_recursively(node *x)
{
   if (x->left) {
       return find_min_recursively(x->left);
   }
   return x;
}
node* successor_of(node *x)
{
   if (! x) return nullptr;
   if (x->right) {
      return find_min_recursively(x->right);
   }
   
   node *y = x->parent;
   while (y && x == y->right) {
          x = y;
          y = y->parent;
   }
   return y;
}

Удалить:

void remove(node *root, int x)
{
 node *current;
 current = root;
 while (current) {
      if (current->key == x) {
         break;
      }
      if (x < current->key) {
          current = current->left;
      } else if (x > current->key) {
          current = current->right;
      }
 }
 if (! current) {
     cout << "required node to delete not found...\n";
     return;
 }
//actual deletion
//1. deletion with one node with empty left subtree
if ( !current->left && current->right) {
      current->right->parent = current->parent;
      if (current->parent->left == current) {
          current->parent->left = current->right;
      } else if (current->parent->right == current) {
          current->parent->right = current->right;
      }
}
//1.1 deleting node with empty right subtree
else if ( !current->right && current->left) {
   current->left->parent = current->parent;
   if (current == current->parent->left) {
       current->parent->left = current->left;
   } else if (current == current->parent->right) { 
       current->parent->right = current->left;
   }
}
//2. deleting node which is leaf node
else if ( !current->left && !current->right) {
     
     if (current == current->parent->left) {
         current->parent->left = nullptr;
     } else if (current == current->parent->right) {
         current->parent->right = nullptr;
     }
}
//3. deleting a node with non empty left and right subtree
else {
   //find the successor of current node
   node *successor_node = this->successor_of(current);
   
   if (successor_node->parent != current) {
       successor_node->parent->left = successor_node->right;
       successor_node->right = current->right; 
       successor_node->right->parent = successor_node;
   }
   successor_node->left = current->left; 
   successor_node->left->parent = successor_node;
   successor_node->parent = current->parent;
   if (! current->parent) {
     root = successor_node;
   } else if (current == current->parent->left) {
     current->parent->left = successor_node;
   } else {
     current->parent->right = successor_node;
   }
}
 delete current;
}