二分搜索树系列之「 节点删除 (remove) 」

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

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

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

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

二分搜索树系列之【 节点删除 (remove) 】

直接看代码吧!
在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.删除最小值最大值
以最大值为例:
其实就是将最大值找到,然后删除(
二分搜索树系列之【 节点删除 (remove) 】

我们在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节点的右孩子。

二分搜索树系列之【 节点删除 (remove) 】
最后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. 情况二:删除同时拥有左右孩子的节点
    如图,我们现在要删除图中58节点,如果直接删除58则41节点的右子树就不再是在该二分搜索树中了
    二分搜索树系列之【 节点删除 (remove) 】

所以,现在我们需要将59拿出来,作为41节点的右孩子(这里只有59,53位置满足条件)
二分搜索树系列之【 节点删除 (remove) 】
继续往下看:

二分搜索树系列之【 节点删除 (remove) 】
这里需要将原来58节点的右孩子变成59节点的右孩子
s->right = delMin(d->right)

二分搜索树系列之【 节点删除 (remove) 】

s->right = delMin(d->right)就变成了下图:
二分搜索树系列之【 节点删除 (remove) 】

再将50节点变成59的左孩子
s->left = d->left:
二分搜索树系列之【 节点删除 (remove) 】

最后将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;
    }
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!