0
0

C++数据结构——AVL树

前言：本篇文章将紧随二叉搜索树的节奏，分享一个新的数据结构——AVL树。

一.AVL树概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。

但是当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

所以AVL树即：一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

二.AVL树插入规则

由于AVL树的独特结构，我们给出以下的插入规则：

1.按照搜索树规则插入。

2.更新插入节点的祖先节点的平衡因子：

** a.插入父亲的左边，父亲的平衡因子--。**

** b.插入父亲的右边，父亲的平衡因子++。**

** c.父亲的平衡因子 == 0，父亲所在的子树高度不变，不再往上更新，插入结束。**

** d.父亲平衡因子 == 1 or -1，父亲所在的子树高度变了，往上更新，重复以上步骤。**

** e.父亲平衡因子 == 2 or -2，父亲所在的子树已经不平衡了，需要旋转处理。**

三.AVL树实现

1.基本框架

template<class K,class V>
struct AVLTreeNode
{
    struct AVLTreeNode<K,V>* _left;
    struct AVLTreeNode<K,V>* _right;
    struct AVLTreeNode<K,V>* _parent;
    int _bf;
    pair<K, V> _kv;

    AVLTreeNode(const pair<K,V>& kv)
        :_left(nullptr)
        , _right(nullptr)
        ,_parent(nullptr)
        , _kv(kv)
        ,_bf(0)
    {}
};

template<class K,class V>
class AVLTree
{
    typedef AVLTreeNode<K, V> Node;
private:
    Node* _root;
};

基本框架与平衡二叉树类似，区别在于AVL树的节点为键值对。

同时我们还需增加平衡因子_bf和父节点_parent，方便我们进行调整。

2.插入

    //插入
    bool Insert(const pair<K, V>& kv)
    {
        //判空
        if (_root == nullptr)
        {
            _root = new Node(kv);
            return true;
        }
        //找到插入位置
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
                return false;
        }
        //插入
        cur = new Node(kv);
        if (kv.first < parent->_kv.first)
            parent->_left = cur;
        else
            parent->_right = cur;

        cur->_parent = parent;
        //更新平衡因子

        return true;
    }

基本的插入步骤与平衡二叉树一模一样，需要关注的就是插入的节点变为键值对。

下面我们单独来看如何更新平衡因子：

        while (parent)
        {
            if (cur == cur->_parent->_left)
                parent->_bf--;
            else
                parent->_bf++;

            if (parent->_bf == 0)
                //更新结束
                break;
            else if (parent->_bf == 1 || parent->_bf == -1)
            {
                //往上更新
                cur = parent;
                parent = parent->_parent;
            }
            else if (parent->_bf == 2 || parent->_bf == -2)
            {
                //出现问题，进行旋转
                break;
            }
            else
                assert(false);
        }

按照我们上边的规则其实很好写出上述代码，要注意循环条件为parent，如果没有父亲，也就是到达了根节点，那就无法再进行调整。

下面我们来重点关注，如何进行旋转。

3.旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

  1. ** 新节点插入较高左子树的左侧---左左：右单旋。**
  2. ** 新节点插入较高右子树的右侧---右右：左单旋。**
  3. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋。
  4. 新节点插入较高右子树的左侧---右左：先右单旋再左单旋。

下面我们就一一来看这四种情况。

1）左\右单旋

先来看右单旋，可以抽象理解为，左子树过高，需要向右边旋转拉低。

从上图能够看出，右单旋的步骤为：

  1. 让平衡因子为-2的节点成为它的左子节点的右子节点；
  2. 同时让该左子节点的右子节点成为平衡因子为-2的节点的左子节点。

同时我们需要关注的细节是：

  • 平衡因子为-2的节点是否为根节点。如果不是根节点则需要调整其父节点的指向。
  • 左子节点的右子节点是否为空。

通过这样的调整，就可以实现平衡，同时调整的两个关键节点的平衡因子均归0。

下面来看代码：

    void RotateR(Node* parent)
    {
        //定义左子节点
        Node* subL = parent->_left;
        //定义左子节点的右子节点
        Node* subLR = subL->_right;
        //调整
        parent->_left = subLR;
        //判空
        if (subLR)
            subLR->_parent = parent;
        //调整
        subL->_right = parent;
        Node* ppNode = parent->_parent;
        parent->_parent = subL;
        if (parent == _root)//判断是否为根
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else//不是根节点，调整父节点指向
        {
            if (ppNode->_left == parent)
                ppNode->_left = subL;
            else
                ppNode->_right = subL;

            subL->_parent = ppNode;
        }
        //平衡因子归0
        parent->_bf = subL->_bf = 0;
    }

再来看左单旋：

左单旋则与右单旋完全相反，所以我们不做过多解释，直接给出代码：

    //左单旋
    void RotateL(Node* parent)
    {
        //定义右子节点
        Node* subR = parent->_right;
        //定义右子节点的左子节点
        Node* subRL = subR->_left;
        //调整
        parent->_right = subRL;
        //判空
        if (subRL)
            subRL->_parent = parent;
        //调整
        subR->_left = parent;
        Node* ppNode = parent->_parent;
        parent->_parent = subR;
        if (parent == _root)//判断是否为根
        {
            _root = subR;
            _root->_parent = nullptr;
        }
        else//不是根节点，调整父节点指向
        {
            if (ppNode->_left == parent)
                ppNode->_left = subR;
            else
                ppNode->_right = subR;

            subR->_parent = ppNode;
        }
        //平衡因子归0
        parent->_bf = subR->_bf = 0;
    }

2）左右/右左双旋

如果说树并不是子树的一条斜边独高，而是折线型的一颗子树高，此时单靠单旋是解决不了问题的，因此需要通过双旋来解决。

上图所示为先左后右的折线型，所以我们需要进行左右双旋，步骤为：

  1. 先从折线的折点位置，即上图的30位置，进行左单旋，使树变为左边一条斜边独高的树。
  2. 在从折线起点位置进行右单旋。
  3. 更新平衡因子。

其中更新平衡因子也分为不同的情况，以上图为例：

  • 如果新节点插入位置为60的左，那么旋转后60为0,30为0,90为1。
  • 如果新节点插入位置为60的右，那么旋转后60为0,30为-1,90为0。
  • 如果新节点就是60，那么三者的平衡因子均为0。

下面上代码：

    //左右双旋
    void RotateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        int bf = subLR->_bf;
        RotateL(parent->_left);
        RotateR(parent);
        if (bf == -1)
        {
            subL->_bf = 0;
            subLR->_bf = 0;
            parent->_bf = 1;
        }
        else if (bf == 1)
        {
            subL->_bf = -1;
            subLR->_bf = 0;
            parent->_bf = 0;
        }
        else if (bf == 0)
        {
            subL->_bf = 0;
            subLR->_bf = 0;
            parent->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

注意更新平衡因子是通过初始时折线末点的平衡因子判断的，所以要提前记录。

再来看右左双旋：

与左右双旋相反，右左双旋是先右后左的折线，所以其操作步骤与之相反：

  1. 先从折线的折点位置，即上图的90位置，进行右单旋，使树变为右边一条斜边独高的树。
  2. 在从折线起点位置进行左单旋。
  3. 更新平衡因子。

其中更新平衡因子也同样分为不同的情况，以上图为例：

  • 如果新节点插入位置为60的左，那么旋转后60为0,30为0,90为1。
  • 如果新节点插入位置为60的右，那么旋转后60为0,30为-1,90为0。
  • 如果新节点就是60，那么三者的平衡因子均为0。

代码如下：

    //右左双旋
    void RotateLR(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        int bf = subRL->_bf;
        RotateR(parent->_right);
        RotateL(parent);
        if (bf == -1)
        {
            subR->_bf = 1;
            subRL->_bf = 0;
            parent->_bf = 0;
        }
        else if (bf == 1)
        {
            subR->_bf = 0;
            subRL->_bf = 0;
            parent->_bf = -1;
        }
        else if (bf == 0)
        {
            subL->_bf = 0;
            subLR->_bf = 0;
            parent->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

根据父节点及其左右子节点的平衡因子，即可判断对应的旋转方式，下面补充插入步骤：

            else if (parent->_bf == 2 || parent->_bf == -2)
            {
                //出现问题，进行旋转
                //左单旋
                if (parent->_bf == -2 && parent->_left->_bf == -1)
                {
                    RotateL(parent);
                }
                //右单旋
                else if (parent->_bf == 2 && parent->_right->_bf == 1)
                {
                    RotateR(parent);
                }
                //左右单旋
                else if (parent->_bf == -2 && parent->_left->_bf == 1)
                {
                    RotateLR(parent);
                }
                //右左单旋
                else
                {
                    RotateRL(parent);
                }
                break;
            }

4.遍历

遍历操作与二叉搜索树类似，需要修改的是我们需要将键值对均打印出来：

    //遍历
    void InOrder()
    {
        inOrder(_root);
        cout << endl;
    }
    void inOrder(const Node* root)
    {
        if (root == nullptr)
        {
            return;
        }
        inOrder(root->_left);
        cout << root->_kv.first << ':' << root->_kv.second << " ";
        inOrder(root->_right);
    }

为了方便调用函数而无需传参，我们采用如上方式进行代码编写。

5.求树高度

求树高度我们前边在讲解二叉树的时候已经分享过了，只需求出左右子树高度的最大值＋1即可，通过递归计算：

    //求树高度
    int Height(const Node* root)
    {
        if (root == nullptr)
            return 0;
        return max(Height(root->_left), Height(root->_right)) + 1;
    }

6.判断平衡

判断树是否平衡，即判断两棵子树的高度差是否大于等于2：

    //判断平衡
    bool IsBalance()
    {
        return isBalance(_root);
    }
    bool isBalance(const Node* root)
    {
        if (root == nullptr)
            return true;

        int leftHeight = Height(root->_left);
        int rightHeight = Height(root->_right);
        if (abs(leftHeight - rightHeight) >= 2)
            return false;
        //检查平衡因子
        if (rightHeight - leftHeight != root->_bf)
            return false;

        return isBalance(root->_left) && isBalance(root->_right);
    }

同时还需要通过递归来判断各个子树是否平衡。

7.求树高度

求树的大小，通过递归即求左子树的大小+右子树的大小+根节点：

    //求树大小
    int Size()
    {
        return size(_root);
    }
    int size(const Node* root)
    {
        if (root == nullptr)
            return 0;
        return size(root->_left) + size(root->_right) + 1;
    }

总结

关于AVL树的基本内容就分享这么多，喜欢本篇文章的小伙伴记得一键三连，我们下期再见！

标签： 数据结构
本文转载自: https://blog.csdn.net/2303_78442132/article/details/138415903
版权归原作者 很楠不爱 所有， 如有侵权，请联系我们删除。
登录后发布评论

“C++数据结构——AVL树”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

Linux：指尖上的进度，流转如诗的进度条

每天一个Mac小技巧之查看电池的健康度

window11安装Docker Desktop和docker使用

大数据新视界 -- 大数据大厂之 Hive 数据导入：多源数据集成的策略与实战（上）（3/ 30）

华三防火墙开启web登录访问配置

PostgreSQL内核源码分析 逻辑复制基本流程，发布订阅创建背后的故事

MySQL系列之远程管理（安全）

文章导航