二分搜索树节点的删除(remove)

在这一小节中，我们会介绍二分搜索树中如何查找最小最大值、最小最大值的删除、删除任意节点（删除只有左孩子的节点、删除只有右孩子的节点和删除左右孩子都存在的节点）；下面我们一一讲解：

一. 查找最小最大值及其删除

1. 查找最小最大值
   其实很简单，首先我们想一想二分搜索树的定义就会明白，最小值在以跟节点的左孩子节点的左孩子节点………上，看图吧：

直接看代码吧！
在public中定义：

// 寻找二分搜索树的最小的键值
  Node* minmum(){
    assert(count != 0);
  Node* minnode = minmum(root);
 return minnode->left;
 }

在private中定义：

 // 寻找二分搜索树的最小的键值
Node* minmum(Node* node){
        if(node != NULL){
            minmum(node->left);
  }
        return node;

对于最大值嘛，逻辑一样的这里就省略了
直接上代码吧！
在public中定义：

// 寻找二分搜索树的最大的键值
Node* maxmum(){
    assert(count != 0);
  Node* maxnode = maxmum(root);
 return maxnode ->right;
}

在private中定义：

// 寻找二分搜索树的最大的键值
Node* maxmum(Node* node){
    if(node != NULL){
        maxmum(node->right);
  }
    return node;
}

2.删除最小值最大值
以最大值为例：
其实就是将最大值找到，然后删除(

我们在public中定义：

//删除最大值的node
void removeMax(){
    if(root){
        root = removeMax(root);
        }
}

在private中定义：

//从二分搜索树中删除最大值所在的节点
Node* removeMax(Node* node){
    if(node->right == NULL){
        Node* NODE = node->left;
       delete node;
       count--;
       return NODE;
  }
    node->right = removeMax(node->right);
    return node;
}

同理，删除最小值也就是将最小值查找到，然后删除：
我们依然在public中定义：

void removeMin(){
       if(root){
           root = removeMin(root);
       }
}

在private中定义：

Node* removeMin(Node* node){
        if(node->left == NULL){
              Node* NODE = node->right;
              delete node;
              return NODE;
        }
        node->left =  removeMin(node->left)；
        return node; 
}

二.删除二分搜索树中任意节点

1. 情况一：删除只有左孩子(右孩子)的节点
   例如下图，我们删除节点58，但此时它存在左孩子，而从二分搜索树的定义可知如果将58删除，就应该将50节点作为41节点的右孩子节点；所以我们需要在删除58节点之前将50节点变成41节点的右孩子。

最后41节点的右子树应该变成：

        41
          \
           50  
          /   \
        42     53   

同理对于只有右孩子的节点是相同的逻辑（在这里省略)
下面看代码：(c++实现）
在public中定义：

//删除二分搜索树中值的任意节点
void remove( Key key){
    root = remove(root, key);
}

在private中定义：

//删除二分搜索树中值的任意节点
Node* remove(Node* node, Key key){
    //判断node是否为空
  if(node == NULL) {
        return NULL;
  }

   //先找到需要删除的值的node
  else if(key < node->key) {      //key为需要删除的，node->key为当前位置
        node->left =  remove(node->left, key);
        return node;
  }

  else if(key > node->key) {
        node->right = remove(node->right, key);
        return node;
  }

    //这里就找到了需要delete的node
  else {   //key == node->key)

 // 待删除节点左子树为空的情况  
         if(node->left == NULL){
               Node* rightNode = node->right;
              delete node;
              count--;
              return rightNode;
          }
        // 待删除节点右子树为空的情况
         if(node->right == NULL){
              Node* leftNode = node->left;
              delete node;
              count--;
              return leftNode;
          }
  }

2. 情况二：删除同时拥有左右孩子的节点
   如图，我们现在要删除图中58节点，如果直接删除58则41节点的右子树就不再是在该二分搜索树中了
   

所以，现在我们需要将59拿出来，作为41节点的右孩子(这里只有59，53位置满足条件)

继续往下看：

这里需要将原来58节点的右孩子变成59节点的右孩子
s->right = delMin(d->right)

s->right = delMin(d->right)就变成了下图：

再将50节点变成59的左孩子
s->left = d->left:

最后将58节点删除即可；利用递归将59节点返回给41节点(成为41节点的右孩子)。

下面看代码：
在public中定义：

//删除二分搜索树中值的任意节点
void remove( Key key){
    root = remove(root, key);
}

在private中定义：

//删除二分搜索树中值的任意节点
Node* remove(Node* node, Key key){
    //判断node是否为空
  if(node == NULL) {
        return NULL;
  }

   //先找到需要删除的值的node
  else if(key < node->key) {      //key为需要删除的，node->key为当前位置
        node->left =  remove(node->left, key);
        return node;
  }

  else if(key > node->key) {
        node->right = remove(node->right, key);
        return node;
  }

    //这里就找到了需要delete的node
  else {   //key == node->key)

 // 待删除节点左子树为空的情况  
         if(node->left == NULL){
               Node* rightNode = node->right;
              delete node;
              count--;
              return rightNode;
          }
        // 待删除节点右子树为空的情况
         if(node->right == NULL){
              Node* leftNode = node->left;
              delete node;
              count--;
              return leftNode;
          }
              // 待删除节点左右子树都不为为空的情况
         Node *succeer =new Node(minmum(node->right)); //找到最小key值的节点返回给succeer
         count ++;
         succeer->right = removeMin(node->right); //将最小key值的node删除，并将返回值给succeer的右孩子

         succeer->left = node->left;
         delete node;
         count--;
         return succeer;
    }
}

Golang版本:

func deleteNode(root *TreeNode, key int) *TreeNode {
//递归终止条件
if root == nil {
return nil
}

if key < root.Val {
//找左子树
root.Left = deleteNode(root.Left, key)
} else if key > root.Val {
//找右子树
root.Right = deleteNode(root.Right, key)
} else {
//找到值
//判断需要删除的节点是否存在左右子树

//左子树为空
if root.Left == nil {
return root.Right
}
if root.Right == nil {
return root.Left
}
//找到右子树最小节点，或者找到左子树最大节点
//找到右子树最小节点
success := root.Right
for success.Left != nil {
success = success.Left
}
//同时需要移除用来替换root位置的节点
success.Right = deleteNode(root.Right, success.Val)
success.Left = root.Left
return success
}
return root
}

本作品采用《CC 协议》，转载必须注明作者和本文链接