devbox
煮酒与君饮
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

平衡二叉树详解及C++实现_平衡二叉树c++

作者：煮酒与君饮 | 2024-08-01 14:30:37

赞

踩

平衡二叉树c++
定义

平衡二叉搜索树：简称平衡二叉树。由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树，根据科学家的英文名也称为 AVL 树。

性质
  1. 可以是空树
  2. 加入不是空树，任何一个节点的左右子树都是平衡二叉树，并且高度差的绝对值不超过 1 1 1
为什么要有平衡二叉树

防止搜索二叉树退化为链表

平衡因子(Balance Factor)

即左右两子树的高度差：

B F = h l e f t − h r i g h t BF=h_{left}-h_{right} BF=hleft​−hright​

平衡二叉树的任何一节点的平衡因子只有三个取值: 0 , 1 , − 1 0,1,-1 0,1,−1，如果绝对值大于 1 1 1，说明该树失衡，就需要进行调整

节点结构
struct treenode
{
    int _val;//键值
    treenode* _parent;//父节点
    treenode* _l, * _r;//左右子树节点
    int _deepth;//树高度
    treenode(int val = 0) :_val(val), _deepth(1),_l(nullptr),_r(nullptr),_parent(nullptr) {}
}; 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
基本接口
class AVLTree
{
    treenode* _root;//根节点
    void _insert(treenode*& , int );//插入
    treenode* _erase(treenode* , int);//删除
    treenode* get_lmax(treenode* );//获取左子树中的最大值
    treenode* LL_roate(treenode*);//左旋
    treenode* RR_roate(treenode*);//右旋
    treenode* LR_roate(treenode*);//左右旋
    treenode* RL_roate(treenode*);//右左旋
    treenode* _find(treenode* , int );//查找
    void _print(treenode* );//打印树节点
    
    void updata_deepth(treenode* root) { //更新树高度
    root ? root->_deepth = max(get_deepth(root->_l),get_deepth(root->_r)) + 1 : 0; 
    }
    
    int get_deepth(treenode* root){//获取树高度
    return root ? root->_deepth : 0; 
    }
    
    int get_balance_factor(treenode* root) { //获取平衡因子
    return root ? get_deepth(root->_l) - get_deepth(root->_r) : 0; 
    }
    
public:
    void insert(int data);//插入
    void erase(int data);//删除
    treenode* find(int data);//查找
    void print() { _print(_root); }//打印
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
AVL树失衡调整

要调整失衡的AVL树，就要找到最小不平衡子树，通过调整不平衡子树，来调整失衡的AVL树

最小不平衡子树：高度最小的失衡树。从插入点开始第一个平衡因子绝对值大于1的节点。

调整方法

通过旋转调整不平衡子树，旋转的类型有四种情况：
L L ， L R ， R R ， R L LL，LR，RR，RL LL，LR，RR，RL，分别对应失衡的四种情况。

  1. 左子树深度高于右子树 ( m a x { h 1 , h 2 } − 2 = m a x { h 3 , h 4 } , 即平衡因子等于 2 ) (max \left \{ h_1,h_2\right \}-2=max\left \{ h_3,h_4\right \},即平衡因子等于2) (max{h1​,h2​}−2=max{h3​,h4​},即平衡因子等于2)

    a.左子树的左子树深度高于左子树的右子树深度 ( h 1 > h 2 , 左子树平衡因子为 1 , R R ) (h_1>h_2,左子树平衡因子为1,RR) (h1​>h2​,左子树平衡因子为1,RR)
    b.左子树的右子树深度高于左子树的左子树深度 ( h 2 > h 1 , 左子树平衡因子为 − 1 , L R ) (h_2>h_1,左子树平衡因子为-1,LR) (h2​>h1​,左子树平衡因子为−1,LR)

  2. 右子树深度高于左子树 ( m a x { h 3 , h 4 } − 2 = m a x { h 1 , h 2 } , 即平衡因子等于 − 2 ) (max \left \{ h_3,h_4\right \}-2=max\left \{ h_1,h_2\right \},即平衡因子等于-2) (max{h3​,h4​}−2=max{h1​,h2​},即平衡因子等于−2)

    a.右子树的右子树深度高于右子树的左子树深度 ( h 4 > h 3 , 右子树平衡因子为 − 1 , L L ) (h_4>h_3,右子树平衡因子为-1,LL) (h4​>h3​,右子树平衡因子为−1,LL)
    b.右子树的左子树深度高于右子树的右子树深度 ( h 3 > h 4 , 右子树平衡因子为 1 , R L ) (h_3>h_4,右子树平衡因子为1,RL) (h3​>h4​,右子树平衡因子为1,RL)

旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。

左旋 ( L L ) (LL) (LL)

  • 让其右子树代替该节点
  • 并将其右子树的左子树(如果有的话)代替其右子树
  • 让该节点成为右子树的左子树

就是让右儿子当爹。这样操作逻辑上相当于让整棵树向左旋转了。
代码实现时，注意要将父节点(如果有的话)的子树(左子树或右子树，要判断一下)改为该节点的右子树(右旋也同理)。

代码实现
inline treenode* AVLTree::LL_roate(treenode* root)
{
    treenode* s = root->_r;//记录右子树
    
    //调整父节点
    s->_parent = root->_parent;//改变右子树的父节点
    if (root->_parent)    //如果该节点有父节点
    {
        if (root->_parent->_l == root)//判断该节点是父节点的左子树还是右子树
            root->_parent->_l = s;//将父节点的子树改为该节点的右子树
        else
            root->_parent->_r = s;
    }
    root->_parent = s;//将该节点的父节点改为右子树，这个一定要最后调整
    
    //调整子树
    if (s->_l)//如果右子树和有左子树
        s->_l->_parent = root;//就将右子树的左子树父节点改为该节点
    root->_r = s->_l;//将右子树的左子树给该节点的右子树
    s->_l = root;//将右子树的左子树改为该节点
    
    //跟更新树高度
    updata_deepth(root);//必须先更新该节点
    updata_deepth(s);
    
    return s;//返回该树的新的根节点
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
右旋 ( R R ) (RR) (RR)

  • 让其左子树代替该节点
  • 并将其左子树的右子树(如果有的话)代替其左子树
  • 让该节点成为左子树的右子树

就是让左儿子当爹。这样的操作在逻辑上相当于将整棵树向右旋转了。

inline treenode* AVLTree::RR_roate(treenode* root)
{
    treenode* s = root->_l;//记录左子树
    
    //调整父节点
    s->_parent = root->_parent;//改变左子树的父节点
    if (root->_parent)//如果该节点有父节点
    {
        if (root->_parent->_l == root)//判断该节点是父节点的左子树还是右子树
            root->_parent->_l = s;//将父节点的子树改为该节点的左子树
        else
            root->_parent->_r = s;
    }
    root->_parent = s;//将该节点的父节点改为左子树
    
    //调整子树
    if (s->_r)//如果左子树有右子树
        s->_r->_parent = root;//就将左子树的右子树的父节点改为该节点
    root->_l = s->_r;//将该节点的左子树改为左子树的右子树
    s->_r = root;//将左子树的右子树改为该节点
    
    //更新树高度
    updata_deepth(root);
    updata_deepth(s);
    
    return s;//返回该树新的根节点
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
左右旋 ( L R ) (LR) (LR)

当失衡是由于左子树的右子树引起时，单纯的右旋不能解决问题。如下图
在这里插入图片描述

如果直接进行右旋，结果如下,并没有使二叉树回复平衡。
在这里插入图片描述

这时，我就就要先对左子树进行左旋操作，让左子树的左子树变为引起失衡的子树，再进行右旋，就可以将二叉树恢复平衡。
在这里插入图片描述

代码实现
inline treenode* AVLTree::LR_roate(treenode* root)
{
    LL_roate(root->_l);//左旋左子树
    return RR_roate(root);//
}

  • 1
  • 2
  • 3
  • 4
  • 5
右左旋 ( R L ) (RL) (RL)

于左右旋同理，就不过多赘述，直接给出代码

inline treenode* AVLTree::RL_roate(treenode* root)
{
    RR_roate(root->_r);
    return LL_roate(root);
}

  • 1
  • 2
  • 3
  • 4
  • 5

接口的具体实现

插入

插入同搜索二叉树基本相同，但是在每次插入之后要更新树的高度，并且检查树是否失衡，这样就可以在递归回退时找到最小不平衡子树，并且旋转调整他。

代码实现
inline void AVLTree::insert(int data)
{
    if (!_root)//为空树时，直接赋值改变根节点
    {
        _root = new treenode(data);
        return;
    }
    _insert(_root, data);//不为空就插入
}
inline void AVLTree::_insert(treenode*& root, int data)
{
    //插入
    //按照二叉搜索树进行插入
    if (root->_val < data)
    {
        if (root->_r)
            _insert(root->_r, data);
        else
        {
            root->_r = new treenode(data);
            root->_r->_parent = root;
        }
    }
    else
    {
        if (root->_l)
            _insert(root->_l, data);
        else
        {
            root->_l = new treenode(data);
            root->_l->_parent = root;
        }
    }
    //更新深度
    updata_deepth(root);
    //判断是否失衡
    if (get_balance_factor(root) == -2)
    {
        //LL型，左旋一次
        //右子树的右子树插入导致失衡
        if (get_balance_factor(root->_r) == -1)
            root = LL_roate(root);
        //RL型,先让右子树右旋再让根节点左旋
        //右子树的左子树插入导致失衡
        else if (get_balance_factor(root->_r) == 1)
            root = RL_roate(root);
    }
    else if (get_balance_factor(root) == 2)
    {
        //RR型，右旋一次
        //左子树的左子树插入导致失衡
        if (get_balance_factor(root->_l) == 1)
            root = RR_roate(root);
        //LR型，先让左子树左旋再让根节点右旋
        //左子树的右子树导致失衡
        else if (get_balance_factor(root->_l) == -1)
            root = LR_roate(root);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
删除

对于删除，需要考虑三种情况:

  1. 删除节点为叶子节点：直接将删除即可
  2. 删除节点有一个子树：将该节点子树替代该节点的位置
  3. 删除节点有两个子树：用中序遍历的前驱或后继代替该节点位置，用递归将该种情况转化为前两种情况(细节见代码)
前驱和后继

删除有两个子树的节点时，让左子树的最大值(前驱)或是右子树的最小值(后继)替代该节点位置，依然满足搜索二叉树。
实现时，将该节点的值直接改为前驱(后继)，然后要删除节点就变为前驱(后继)，再递归找到前驱(后继)，最后都会转化成前两种情况。

寻找前驱代码的实现(后继类似)
inline treenode* AVLTree::get_lmax(treenode* lroot)
{
    while (lroot->_r)
        lroot = lroot->_r;
    return lroot;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
代码实现
inline void AVLTree::erase(int data)
{
    if (!_root)//空树不能进行删除
        return;
    _root = _erase(_root, data);
}
inline treenode* AVLTree::_erase(treenode* root, int data)
{
    //1.删除节点
    if (root->_val < data)
        if (root->_r)
            _erase(root->_r, data);
        else if (root->_val > data)
            if (root->_l)
                _erase(root->_l, data);
            else
            {
                //删除有三种情况
                //1.删除节点为叶子节点 
                //直接删除
                if (!root->_l && !root->_r)
                {
                    if (root->_parent)
                    {
                        if (root->_parent->_l == root)
                            root->_parent->_l = nullptr;
                        else
                            root->_parent->_r = nullptr;
                    }
                    delete root;
                    root = nullptr;
                }
                //2.删除节点有一个子树
                //将该子树代替掉删除节点的位置
                else if (!root->_l || !root->_r)
                {
                    if (root->_parent)
                    {
                        if (root->_parent->_l == root)
                            root->_parent->_l = root->_l ? root->_l : root->_r;
                        else
                            root->_parent->_r = root->_l ? root->_l : root->_r;
                    }
                    treenode* s = root->_l ? root->_l : root->_r;
                    s->_parent = root->_parent;
                    delete root;
                    root = s;
                }
                // 3.删除节点有两个子树
                //用中序遍历的前驱或后继代替该节点
                else
                {
                    treenode* lmax = get_lmax(root->_l);
                    root->_val = lmax->_val;
                    _erase(root->_l, lmax->_val);
                }
            }
    //2.调整高度
    updata_deepth(root);
    //3.调整最小不平衡子树
    if (get_balance_factor(root) == 2)
    {
        if (get_balance_factor(root->_l) == 1)
            root = RR_roate(root);
        else
            root = LR_roate(root);
    }
    else if (get_balance_factor(root) == -2)
    {
        if (get_balance_factor(root) == -1)
            root = LL_roate(root);
        else
            root = RL_roate(root);
    }
    return root;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
查找

很简单，这里只给出代码

inline treenode* AVLTree::find(int data)
{
    if (!_root)
        return nullptr;
    return _find(_root, data);
}
inline treenode* AVLTree::_find(treenode* root, int data)
{
    if (!root)
        return nullptr;
    if (data < root->_val)
        return _find(root->_l, data);
    else if (data > root->_val)
        return _find(root->_r, data);
    else
        return root;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
总结

平衡二叉树旋转时，交换的变量很多，要时刻记着哪些变量已经交换，哪些还没有，实现时要仔细不然很容易出现问题。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/煮酒与君饮/article/detail/914513
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号