当前位置： 首页 > article >正文

平衡二叉搜索树删除的实现

article 2024/10/1 13:51:14

前言

        上期讲了平衡二叉搜索树的插入，这一期我们来讲讲删除。同时，二叉搜索树的简介不会出现在本篇博客之中，如有需要可以查看上一篇博客《平衡二叉搜索树插入的实现》。

平衡二叉搜索树插入的实现-CSDN博客文章浏览阅读659次，点赞9次，收藏13次。因为二叉搜索树在插入的时候最坏的情况可能会变成一条单一链表，从而使查找或者插入的时候消耗大量的时间。所以为了解决这一情况诞生了平衡二叉搜索树，其作用是为了减少二叉搜索树的整体高度，从而使查找插入删除的效率提高。https://blog.csdn.net/2302_81342533/article/details/142610087

一、删除思路

        首先，删除需要先找到需要删除的节点。通过关键值找到对应节点，小了向左，大了向右。找到节点就能够开始删除，相反没找到就删除失败。

        在之前的二叉搜索树的里面有提到怎么删除一个节点，现在复习一下。

        假如找到就开始删除，这里一共有4种情况，但是分为3种讨论：

        （1）该节点没有子节点。

        （2）该节点只有右子树。

        （3）该节点只有左子树。

        （4）该节点左右子树都存在。

        其中第一种情况包括在第二种情况中实现代码。

        如果只有一边子树有节点，那么就让父节点链接另一个子树。

        如果左右节点都存在，就用右子树最左侧节点，或者左子树最右侧节点对节点进行替换值，然后该节点就变成了情况（2）（3）。

        删除节点完成后就需要修改节点的记录值bf。这个时候也分为3种情况，如果节点的值为1或者-1表示节点的高度没有改变所以就可以不用继续向上查找节点。

图1-1 喊出节点后树的高度不变

        如果删除完成后，节点的值变为0，子树就变矮了，那么就需要继续向上遍历节点。

图1-2 节点删除后树变矮

        如果节点的值在修改之后等于2或者-2，就需要对二叉树进行旋转从而让它保持平衡。这一类就分为3种情况，而且旋转比插入的额时候复杂一点，同时这一部分也是重点内容。

1、左单旋

        左单旋的发生在节点的值在修改之后等于2的时候，当有节点的右子树高于左子树或者等于左子树的时候都需要左单旋。

图1-3 需要左单旋的情况

        以上两种情况再旋转之后的bf值夜不相同，如果是第一种情况，那么旋转后节点A、B的值都为0，树的高度仍然降低了，也就是说还需要继续向上修改父节点的记录值bf。如果是第二种情况，高度就和旋转前相同，就不需要继续向上搜索了。B节点的记录值变为-1，A的记录值变为1。

图1-4 左旋后高度降低的情况

图1-5 左旋之后高度不变的情况

2、右左双旋

        右左双旋夜发生在节点的记录值为2的时候，右节点中记录值为-1的情况。这中情况和插入的时候一样。使树的高度降低，所有节点的记录值修改也和插入的时候修改值相同。

图1-6 需要右左双旋

        甚至旋转的代码都能直接使用。

图1-7 右左双旋

3、右单旋

        右单旋就是左单旋的翻版，规律和左单旋是一样的。需要都单旋的情况发生在父节点记录值变为-2，而左节点记录值为-1或者0的情况。

图2-1 需要右单旋的情况

        同理，B的记录值如果是0旋转之后就不要要继续向上修改记录值bf，相反，则需要遍历。

图2-2 右单旋后高度变矮的情况

图2-3 右单旋后高度不变的情况

4、左右双旋

        当父节点记录值为-2，左节点记录值为1的时候就需要进行左右双旋。左右双旋之中同样分为三种情况。

图2-4 需要左右双旋的情况

        旋转之后的结果和插入的左右双旋一致。

图2-5 左右双旋

二、代码实现

        代码实现的解释写法都在代码的注释当中，代码同时包含之前实现的插入函数：

#include <iostream>
#include <string>
#include <assert.h>
#include <utility>
#include <algorithm>
#include <cmath>

using namespace std;

template<class T>
struct AVLTreeNode
{
	AVLTreeNode(const T& data = T())
	: _pLeft(nullptr)
	, _pRight(nullptr)
	, _pParent(nullptr)
	, _data(data)
	, _bf(0)
	{}

	AVLTreeNode<T>* _pLeft;
	AVLTreeNode<T>* _pRight;
	AVLTreeNode<T>* _pParent;
	T _data;
	int _bf;   // 节点的平衡因子
};

// AVL: 二叉搜索树 + 平衡因子的限制
template<class T>
class AVLTree
{
	typedef AVLTreeNode<T> Node;
public:
	AVLTree()
		: _pRoot(nullptr)
	{}

    // 在AVL树中插入值为data的节点
	bool Insert(const T& data)
    {
        // 根节点为空直接插入并修改
        if(nullptr == _pRoot)
        {
            _pRoot = new Node(data);
            return true;
        }

        Node* parent = nullptr;
        Node* cur = _pRoot;

        // 找到对应的插入节点
        while(cur)
        {
            parent = cur;
            if(data < cur->_data)
            {
                cur = cur->_pLeft;
            }
            else if(data > cur->_data)
            {
                cur = cur->_pRight;
            }
            else
            {
                return false;
            }
        }

        // 插入节点
        cur = new Node(data);
        if(data < parent->_data)
        {
            parent->_pLeft = cur;
            cur->_pParent = parent;
        }
        else if(data > parent->_data)
        {
            parent->_pRight = cur;
            cur->_pParent = parent;
        }
        else
        {
            assert(false);
            return false;
        }

        // AVL树向上检查，修改平衡因子
        while(parent)
        {
            // 修改平衡因子
            if(parent->_pLeft == cur)
            {
                parent->_bf--;
            }
            else if(parent->_pRight == cur)
            {
                parent->_bf++;
            }
            else
            {
                // 节点存储的有问题
                assert(false);
            }

            // 考虑是否旋转子树
            // 1. 为0不需要继续向上修改
            if(0 == parent->_bf)
            {
                break;
            }
            // 2. 等于1或者-1需要继续向上修改平衡因子
            else if(1 == parent->_bf || -1 == parent->_bf)
            {
                cur = parent;
                parent = parent->_pParent;
            }
            // 3. 因子等于2或者-2就说明需要旋转
            else if(-2 == parent->_bf || 2 == parent->_bf)
            {
                // 继续分为4种情况
                // 3.1. 左子树的左子树超高
                if(-2 == parent->_bf && -1 == cur->_bf)
                {
                    RotateR(parent);
                }
                // 3.2. 右子树的右子树超高
                else if(2 == parent->_bf && 1 == cur->_bf)
                {
                    RotateL(parent);
                }
                // 3.3. 左子树的右子树超高
                else if(-2 == parent->_bf && 1 == cur->_bf)
                {
                    RotateLR(parent);
                }
                // 3.4. 右子树的左子树超高
                else if(2 == parent->_bf && -1 == cur->_bf)
                {
                    RotateRL(parent);
                }
                break;
            }
        }
        return true;
    }

    bool Erase(const T& data)
    {
        if(_pRoot == nullptr)
        {
            return false;
        }

        // 双节点遍历链表
        Node* parent = nullptr;
        Node* cur = _pRoot;

        while(cur)
        {
            if(data > cur->_data)
            {
                cur = cur->_pRight;
            }
            else if(data < cur->_data)
            {
                cur = cur->_pLeft;
            }
            else
            {
                break;
            }
        }

        // 未查找到节点，删除失败
        if(cur == nullptr)
        {
            return false;
        }

        // 找到节点，能够删除
        pair<Node*, Node*> tmp = _Erasecur(cur);
        parent = tmp.first;
        cur = tmp.second;
        if(cur)
        {
            cur->_pParent = parent;
        }

        // 节点删除成功后，需要向上调整_bf值
        while(parent)
        {
            // 1. 节点删除后需要继续向上查改
            if(parent->_bf == 0)
            {
                cur = parent;
                parent = parent->_pParent;
                // 没有父节点退出
                if(nullptr == parent)
                {
                    break;
                }
                // 增减bf
                if(parent->_pLeft == cur)
                {
                    parent->_bf++;
                }
                else if(parent->_pRight == cur)
                {
                    parent->_bf--;
                }
                else
                {
                    assert(false);
                }
            }
            // 2. 节点的值为1或者-1的时候表示高度不变
            else if(1 == parent->_bf || -1 == parent->_bf)
            {
                break;
            }
            // 3. 节点的值为2或者-2就需要旋转，并且可能需要继续向上查找
            else if(2 == parent->_bf || -2 == parent->_bf)
            {
                Node* other = nullptr;
                if(parent->_pLeft == cur)
                {
                    other = parent->_pRight;
                }
                else if(parent->_pRight == cur)
                {
                    other = parent->_pLeft;
                }
                else
                {
                    assert(false);
                }

                if(2 == parent->_bf)
                {
                    if(0 == other->_bf)
                    {
                        RotateL(parent);
                        parent->_bf = 1;
                        other->_bf = -1;
                        parent = other;
                    }
                    else if(1 == other->_bf)
                    {
                        RotateL(parent);
                    }
                    else if(-1 == other->_bf)
                    {
                        RotateRL(parent);
                    }
                    else
                    {
                        assert(false);
                    }
                }
                else if(-2 == parent->_bf)
                {
                    if(0 == other->_bf)
                    {
                        RotateR(parent);
                        parent->_bf = -1;
                        other->_bf = 1;
                        parent = other;
                    }
                    else if(-1 == other->_bf)
                    {
                        RotateR(parent);
                    }
                    else if(1 == other->_bf)
                    {
                        RotateLR(parent);
                    }
                    else
                    {
                        assert(false);
                    }
                }
            }
        }
        return true;
    }
    
    // AVL树的验证
	bool IsAVLTree()
	{
		return _IsAVLTree(_pRoot).second;
	}

private:
    // 删除对应节点，返回父节点
    pair<Node*, Node*> _Erasecur(Node* cur)
    {
        Node* parent = cur->_pParent;
        // 1. 左子树为空
        if(nullptr == cur->_pLeft)
        {
            if(cur == _pRoot)
            {
                _pRoot = cur->_pRight;
                delete cur;
                return make_pair(parent, _pRoot);
            }
            else if(parent->_pLeft == cur)
            {
                parent->_pLeft = cur->_pRight;
                parent->_bf++;
                delete cur;
                return make_pair(parent, parent->_pLeft);
            }
            else if(parent->_pRight == cur)
            {
                parent->_pRight = cur->_pRight;
                parent->_bf--;
                delete cur;
                return make_pair(parent, parent->_pRight);
            }
            else
            {
                assert(false);
            }     
        }
        // 2. 右子树为空
        else if(nullptr == cur->_pRight)
        {
            if(cur == _pRoot)
            {
                _pRoot = cur->_pLeft;
                delete cur;
                return make_pair(parent, _pRoot);
            }
            else if(parent->_pLeft == cur)
            {
                parent->_pLeft = cur->_pLeft;
                parent->_bf++;
                delete cur;
                return make_pair(parent, parent->_pLeft);
            }
            else if(parent->_pRight == cur)
            {
                parent->_pRight = cur->_pLeft;
                parent->_bf--;
                delete cur;
                return make_pair(parent, parent->_pRight);
            }
            else
            {
                assert(false);
            }     
        }
        // 左右子树均不为空
        else
        {
            // 找到右子树最左节点
            Node* Rsonmin = cur->_pRight;
            while(Rsonmin->_pLeft)
            {
                Rsonmin = Rsonmin->_pLeft;
            }
            cur->_data = Rsonmin->_data;
            return _Erasecur(Rsonmin);
        }

        // 防出错
        return make_pair(nullptr, nullptr);
    }

    // 根据AVL树的概念验证pRoot是否为有效的AVL树
	pair<int, bool> _IsAVLTree(Node* pRoot)
    {
        if(pRoot == nullptr)
        {
            return make_pair(0, true);
        }

        pair<int, bool> lson = _IsAVLTree(pRoot->_pLeft);
        cout << pRoot->_data << " ";
        pair<int, bool> rson = _IsAVLTree(pRoot->_pRight);

        int hight = max(rson.first, lson.first) + 1;
        bool Is = rson.second && lson.second && abs(rson.first - lson.first) <= 1;

        return make_pair(hight, Is);
    }

	// size_t _Height(Node* pRoot)
    // {
    //     if(nullptr == pRoot)
    //     {
    //         return 0;
    //     }
    //     else{
    //         return max<size_t>(_Height(pRoot->_pLeft), _Height(pRoot->_pRight)) + 1;
    //     }
    // }
    // 右单旋
	void RotateR(Node* pParent)
    {
        Node* SubL = pParent->_pLeft;
        Node* SubLR = SubL->_pRight;
        Node* parent = pParent->_pParent;

        pParent->_pLeft = SubLR;
        pParent->_pParent = SubL;

        if(SubLR)
            SubLR->_pParent = pParent;

        SubL->_pRight = pParent;
        SubL->_pParent = parent;

        if(pParent == _pRoot)
        {
            _pRoot = SubL;
        }
        else
        {
            if(parent->_pLeft == pParent)
            {
                parent->_pLeft = SubL;
            }
            else if(parent->_pRight == pParent)
            {
                parent->_pRight = SubL;
            }
            else
            {
                assert(false);
            }
        }
        
        pParent->_bf = SubL->_bf = 0;
    }

    // 左单旋
	void RotateL(Node* pParent)
    {
        Node* SubR = pParent->_pRight;
        Node* SubRL = SubR->_pLeft;
        Node* parent = pParent->_pParent;

        pParent->_pRight= SubRL;
        pParent->_pParent = SubR;

        if(SubRL)
            SubRL->_pParent = pParent;

        SubR->_pLeft = pParent;
        SubR->_pParent = parent;

        if(pParent == _pRoot)
        {
            _pRoot = SubR;
        }
        else
        {
            if(parent->_pLeft == pParent)
            {
                parent->_pLeft = SubR;
            }
            else if(parent->_pRight == pParent)
            {
                parent->_pRight = SubR;
            }
            else
            {
                assert(false);
            }
        }
        
        pParent->_bf = SubR->_bf = 0;
    }

    // 右左双旋
	void RotateRL(Node* pParent)
    {
        Node* SubR = pParent->_pRight;
        Node* SubRL = SubR->_pLeft;
        int bf = SubRL->_bf;

        RotateR(SubR);
        RotateL(pParent);

        if(0 == bf)
        {
            SubR->_bf = SubRL->_bf = pParent->_bf = 0;
        }
        else if(-1 == bf)
        {
            SubRL->_bf = pParent->_bf = 0;
            SubR->_bf = 1;
        }
        else if(1 == bf)
        {
            SubRL->_bf = SubR->_bf = 0;
            pParent->_bf = -1;
        }
        else
        {
            assert(false);
        }
    }

    // 左右双旋
	void RotateLR(Node* pParent)
    {
        Node* SubL = pParent->_pLeft;
        Node* SubLR = SubL->_pRight;
        int bf = SubLR->_bf;

        RotateL(SubL);
        RotateR(pParent);

        if(0 == bf)
        {
            SubL->_bf = SubLR->_bf = pParent->_bf = 0;
        }
        else if(1 == bf)
        {
            SubLR->_bf = pParent->_bf = 0;
            SubL->_bf = -1;
        }
        else if(-1 == bf)
        {
            SubLR->_bf = SubL->_bf = 0;
            pParent->_bf = 11;
        }
        else
        {
            assert(false);
        }
    }

private:
	Node* _pRoot;
};

三、代码测试

        测试代码如下：

#include "AVLtree.hpp"

int main()
{
    AVLTree<int> avltree;
    for(int i = 0; i < 100; ++i)
    {
        avltree.Insert(i);
    }

    for(int i = 0; i < 10; ++i)
    {
        avltree.Erase(i);
    }
    if(avltree.IsAVLTree())
    {
        cout << "avltree是二叉搜索树" << endl;
    }
    else
    {
        cout << "avltree不是二叉搜索树" << endl;
    }
    return 0;
}

作者结语

        阿巴阿巴。非常绕的代码，是我旋转。删除思路之中左单旋和右单旋、左右双旋和右左双旋思路的重复度很高，只用看一边的就行。这里多讲了一遍就是想写的更清楚，减少思考。

        总之干货还是有点的，下一篇博客应该就进化成红黑树了。都是树，也就难一点点。


http://www.kler.cn/news/327521.html

相关文章：

  • Spring Cloud全解析：服务调用之OpenFeign集成OkHttp
  • 一次阿里云ECS免费试用实践
  • leetcode-链表篇4
  • MATLAB编写的RSSI在三维空间上的定位程序，锚点数量无限制（可自定义），带中文注释
  • 如何获取钉钉webhook
  • docker容器mysql数据备份 mysql容器无法启动备份数据
  • 【docker学习】Linux系统离线方式安装docker环境方法
  • 【Linux系列】CMA (Contiguous Memory Allocator) 简单介绍
  • IP地址与5G时代的万物互联
  • 享元模式
  • 【MATLAB源码-第178期】基于matlab的8PSK调制解调系统频偏估计及补偿算法仿真，对比补偿前后的星座图误码率。
  • 智慧农业案例 （一）- 自动化机械
  • vue2圆形标记（Marker）添加点击事件不弹出信息窗体（InfoWindow）的BUG解决
  • 05-函数传值VS传引用
  • 2.点位管理|前后端如何交互——帝可得后台管理系统
  • 基础漏洞——SSTI（服务器模板注入）
  • leetcode-134. 加油站-贪心策略
  • 数据结构与算法学习（2）
  • 汽车灯光系统详细介绍
  • 【机器学习】---深入探讨图神经网络（GNN）
  • 【STM32】 TCP/IP通信协议（3）--LwIP网络接口
  • 将 Intersection Observer 与自定义 React Hook 结合使用
  • 基于RPA+BERT的文档辅助“悦读”系统 | OPENAIGC开发者大赛高校组AI创作力奖
  • ruoyi-python 若依python版本部署及新增模块
  • 基于springboot+微信小程序社区超市管理系统（超市3）（源码+sql脚本+视频导入教程+文档）
  • 使用 CMake 构建 C 语言项目
  • 《Zeotero的学习》
  • Linux中安装ffmpeg
  • 随手记：牛回速归
  • Simulink仿真中get_param函数用法