BST删除操作（二叉搜索树）

雨点打透心脏的1/2处 2021-06-10 20:39 433阅读 0赞

BST的删除操作向来被认为难度很大，因为它不同于插入，定位到了那个该插入的位置选择左边/右边进行插入即可，而删除操作则需要分成以下三种情况进行讨论，删除难度从上到下依次递增：

*  case1 叶子结点
 *  case2 只有左子树/只有右子树的结点
 *  case3 左子树和右子树都存在的结点

其实case1，case2的难度系数都不大，重难点就是在于处理case3这种情况的结点

*  case1 叶子结点直接将结点删除(树少了ta照样长得很茁壮，没有人会记得一片叶子的存在)
 *  case2 要删除的结点用一个指针进行保存，而自己跳到自己的左/右子树上，即parent牺牲自己抱住了lchild/rchild(孩子在路中央呆若木鸡，眼看着大卡车迎面而来，父亲眼疾手快将孩子推向一边，而让冰冷的钢铁撞击在自己炙热的身躯上，代替了孩子的牺牲)
 *  case3 见下文具体分析

注：以下讲解的代码思路参考于《大话数据结构》

本体代码树结构如下定义：

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */

那么下面我们就开始进行整个代码思路的讲解  
首先我们给出解BST问题的一个代码框架，我们定义这里删除BST中某个结点的函数为deleteNode(TreeNode\* root, int key)，其中TreeNode\* root为已经构造好了的一棵符合规范的BST，而int key则是我们即将要删除的目标

TreeNode* deleteNode(TreeNode* root, int key) {
    	if ( root == nullptr )
    		return root;
    
    	if ( key == root->val ) {
    		// 定位到目标进行删除操作...
    	}
    	// 若key小于当前定位到的root->val，则说明root->val应该继续往左走才有机会定位到key
    	else if ( key < root->val )
    		root->left = deleteNode(root->left, key);
    	// 若key大于当前定位到的root->val，则说明root->val应该往右走才有机会定位到当前key
        else
            root->right = deleteNode(root->right, key);
    }

以上的模版在接BST题时非常有用！完美利用了BST的性质，一定要牢记于心。  
剩下的便是今天我们要攻克的难题：删除结点。

### case1 叶子结点 ###

直接进行删除(直接使用delete删除其实是不严谨，这里我们忽略删除的细节，具体讲解整体思路部分)

if ( key == root->val ) {
    	// 定位到目标进行删除操作...
    	// case1 : 叶子结点的删除操作
    	if ( root->left == nullptr && root->right == nullptr )
    		delete root;
    }

### case2 只有左子树/只有右子树的结点 ###

保存这个被删除的结点，把孩子推向一边，有左子树就把孩子推到左边，有右子树就把孩子推到右边

### case3 左子树和右子树都存在的结点 ###

在开始讲解最关键的这一部分之前，首先介绍一个BST中直接前驱/直接后继的概念：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NDA2NjU2_size_16_color_FFFFFF_t_70_pic_center]  
如果不能理解这个概念，那么我给你一个建议：找一棵普通的树，完完整整的结合中序遍历的代码过一遍遍历的顺序，好好的去理解中序遍历回溯的时机。  
在理解了上述概念后，直接后继留给你们去推导。  
其次需要注意的是，这里我们所说的直接前驱/后继是数组进行中序遍历时遍历到的当前结点的上一个元素！  
好，接着往下讲，我们又知道，BST的中序遍历结果是一个升序数组，但是结合BST的这点性质，可以得出一个结论：BST中某个结点的前驱/后继结点 就是 BST中序遍历得到的已排序数组中前一个/后一个元素。  
还是看上面的例子，5的直接前驱结点是4，也是中序遍历得到的排序数组中5的前一个元素，这不是巧合！  
奇怪的思路增加了：  
**狸猫换太子**  
这是什么意思呢？不难发现：我们的直接前驱/后继结点所属的情况一定属于case1和case2，即一定为叶子结点or只有左/右子树的结点。假设我们将要删除的结点伪装成其直接前驱/后继结点，再将直接前驱/后继结点删除，神不知鬼不觉的“算法版狸猫换太子”岂不美哉？好，现在我们已经清晰的转化了问题，我们来开始写代码：

不知道你是否敏感，我们在狸猫换太子之后出现了问题。正如我上面所说，直接前驱结点也是分两种情况的：**i.一种是当前的结点的左结点的最右边的结点 ii.那么如果出现当前结点的左结点没有右子树，则当前结点的左结点就是当前结点的前驱结点**(这段有点套娃，不理解的就去看上面我给出的图)。所以我是如何得知这里的前驱结点属于哪一种情况的呢？  
这里又不得不提一个链表问题中常用的思想：用一个指针pre记录之前遍历过的位置。  
我们不难发现，假设我们用一个指针p记录指针q上一次遍历到的结点，那么当我对应情况 **i** 时，我的p结点只要继承q结点的“遗产”就好了(下面会具体讲遗产是什么)，而对应到情况 **ii** 的时候，q刚到达当前结点的左结点，p根本就没有挪动的必要。不难看出，我们可以用一个指针p在不同情况会处于不同的位置上来区分两种情况。

TreeNode* p;
    TreeNode* q;
    if ( key == root->val ) {
    	// 定位到目标进行删除操作...
    	// case1 : 叶子结点的删除操作
    	if ( root->left == nullptr && root->right == nullptr )
    		delete root;
    	// case2 : 只有左子树/只有右子树的结点
    	// 重接左子树
        if ( root->right == nullptr ) {
            p = root;
            root = root->left;
            delete p;
        }
        // 重接右子树
        else if ( root->left == nullptr ) {
             p = root;
             root = root->right;
             delete p;
        }
        else {
        	// case3 : 左子树右子树都存在的结点
    		// 我们首先按伪装成前驱结点来写代码，找到当前结点root的左结点的最右边的结点
    		// p指向当前结点，q指向当前结点的左结点
    		p = root;	
    		q = root->left;
    		// 假设q有右子树就不断往右推进，p随之跟进，而假设q没有右子树，p和q都滞留在原地
    		while ( q->right ) {
    			p = q;
    			q = q->right;
    		}
    		// 狸猫换太子，不难理解，我们即将要删除的并不是root，而是q
    		root->val = q->val;
    		// 情况i：直接前驱为当前的结点的左结点的最右边的结点
    		if ( p != root )
    			// 直接前驱结点是一定不会存在右子树这一说了，已经推到了最右边，所以左子树是他留给p的遗产(当然如果q是个叶子结点的就是一个穷光蛋，什么都不剩)，接到p的右子树上
    			p->right = q->left;
    		// 情况ii：当前结点的左结点就是当前结点的前驱结点，将遗产接到p的左子树上
    		else 
    			p->left = q->left;
    
    		delete q;
        }
    }

别忘记之前我们所讲的模版，这一部分只是属于if ( key == root->val )这个代码段的，下面附上完整代码，我在基准情形那一块做了点优化，即当树中仅有一个结点且这个结点的val值就是序要删除的值的时候直接返回nullptr：

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* deleteNode(TreeNode* root, int key) {
            TreeNode* p;
            TreeNode* q;
    
            if ( root == nullptr || root->val == key && root->left == nullptr && root->right == nullptr )
                return nullptr;
    
            else {
                if ( key == root->val ) {
                    if ( root->left == nullptr && root->right == nullptr )
                        delete root;
    
                    if ( root->right == nullptr ) {
                        p = root;
                        root = root->left;
                        delete p;
                    }
                    
                    else if ( root->left == nullptr ) {
                        p = root;
                        root = root->right;
                        delete p;
                    }
                    
                    else {
                        p = root;
                        q = root->left;
    
                        while ( q->right ) {
                            p = q;
                            q = q->right;
                        }
                        
                        root->val = q->val;
                        
                        if ( p != root )
                            p->right = q->left;
                        else
                            p->left = q->left;
    
                        delete q;
                    }
                }
    
                else if ( key < root->val )
                    root->left = deleteNode(root->left, key);
                else
                    root->right = deleteNode(root->right, key);
    
                return root;
            }
        }
    };

[LeetCode 450.Delete Node in a BST][]就是对BST删除操作的考察，这个操作我真的讲的很细致了。如何检验自己是否听明白了呢？没错，直接后继就是留给你检验自己有没有听懂的机会，首先你要推导出直接后继对应的是当前结点的什么结点，其次需要分析像分析直接前驱那样，分析直接后继中的情况，答案我会放在Github上，独立思考后可以进行参考o！

## 回顾总结 ##

**1.BST模版  
2.树的直接前驱/后继结点  
3.BST中序遍历结果对应升序数组  
4.记录前驱结点的思想  
5.利用指针位置的不同显性化出分类讨论出的结果  
6.关注我**

之后的博客风格可能都会像这样了，可能不会专门的去做LeetCode刷题栏目了，会专门拆开某个算法知识点，可能有针对性的对应一些题目留给大家去思考。另外之前自己基于nodejs和github搞了个博客，由于github对国内是真的不友好，可能之后会基于gitee再创建个博客吧。各位同学如果觉得我的博客内容写得不错求你们给个关注8！我会努力写出更优质的内容的！

github地址：[https://github.com/18260036169/LeetCode-Tree][https_github.com_18260036169_LeetCode-Tree]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NDA2NjU2_size_16_color_FFFFFF_t_70_pic_center]: /images/20210527/722c54fd310343a692e5894f4a643de9.png
[LeetCode 450.Delete Node in a BST]: https://leetcode-cn.com/problems/delete-node-in-a-bst/
[https_github.com_18260036169_LeetCode-Tree]: https://github.com/18260036169/LeetCode-Tree