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

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

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

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

直接看代码吧！

在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. 情况一：删除只有左孩子(右孩子)的节点
2. 例如下图，我们删除节点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;
        }
    }
}

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

所以，现在我们需要将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;
    }
}