【C++】AVL树

简介: AVL树是一种自平衡二叉搜索树,由Georgy Adelson-Velsky和Evgenii Landis提出。它通过确保任意节点的两子树高度差不超过1来维持平衡,支持高效插入、删除和查找操作,时间复杂度为O(log n)。AVL树通过四种旋转操作(左旋、右旋、左-右旋、右-左旋)来恢复树的平衡状态,适用于需要频繁进行数据操作的场景。

前言:

前面讲到了平衡搜索树(BST),但是不能会出现极端情况,出现线性的结构,今天介绍自平衡二叉搜索树(AVL)

AVL树

AVL的介绍

AVL树是一种自平衡二叉搜索树:它以苏联科学家Georgy Adelson-VelskyEvgenii Landis的名字命名。

  • AVL树中,任何节点的两个子树的高度最多相差1,这保证了树的平衡性,从而使得树的操作(如插入、删除和查找)具有良好的最坏情况性能,时间复杂度为O(log n)

  • AVL树的旋转操作是其自平衡机制的核心,包括左旋、右旋、左-右旋和右-左旋。这些旋转调整节点的位置,减少子树的高度差,恢复树的平衡。

AVL树特性

  • 严格的平衡性:AVL树的每个节点的左右子树的高度差的绝对值不超过1,这保证了树的高度最小,从而使得操作(如插入、删除和查找)的时间复杂度保持在对数级别。
  • 旋转调整:当插入或删除操作导致节点的平衡因子超出允许范围时,AVL树会通过单旋转或双旋转来重新平衡树。
  • 高效的搜索、插入和删除操作:由于AVL树的高度平衡,这些操作的时间复杂度通常为O(log n),其中n是树中节点的数量。
  • 节点定义AVL树的节点通常包含数据、指向左右子节点的指针、指向父节点的指针以及记录子树高度差的平衡因子。
  • 高度记录:在AVL树中,每个节点还会记录其子树的高度,这有助于快速计算平衡因子并在需要时进行调整。
  • 适用场景AVL树适用于需要频繁进行数据插入、删除和查找操作的场景,尤其是在数据集合较大时,可以保持较高的效率。

AVL树的核心

AVL树是一种自平衡的二叉查找树,它通过旋转调整机制来维持树的平衡。当树在插入或删除操作后出现不平衡时,AVL树会执行以下四种旋转操作之一来恢复平衡:

  1. 单旋转
    • 左旋(LL型):当插入或删除操作导致某个节点的左子树的高度比右子树高2时,需要执行左旋操作。左旋操作涉及到将这个节点的右子树提升为新的根节点,并将原根节点作为左子节点挂接到新根节点上。
    • 右旋(RR型):与左旋相反,当某个节点的右子树的高度比左子树高2时,执行右旋操作,即将左子树提升为新的根节点。
  2. 双旋转
    • 左-右旋(LR型):当插入或删除操作导致某个节点的左子树的右子树的高度比左子树的右子树高时,先对左子树执行左旋,然后对原节点执行右旋。
    • 右-左旋(RL型):与左-右旋相反,当某个节点的右子树的左子树的高度比右子树的左子树高时,先对右子树执行右旋,然后对原节点执行左旋。

AVL插入实现

  • AVL树是基于BST结构,大主体就是BST
  • 问题的解决就是AVL的单旋和双旋以及需要旋转的条件。

AVL的存贮结构

  • 在这里面利用KV结构进行存储数据
  • 左右节点,还有一个父亲节点
  • 为了保持平衡定义_bf(平衡因子:balance factor)
template<class K, class V>
struct AVLNode
{
   
    pair<K, V> _kv;
    AVLNode<K, V>* _left;
    AVLNode<K, V>* _right;
    AVLNode<K, V>* _parent;
    int _bf;

    AVLNode(const pair<K, V>& kv)
        :_kv(kv)
        , _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _bf(0)
    {
   }
};
template<class K, class V>
class AVL
{
   
    typedef AVLNode<K, V> Node;
    private:
    Node* _root;
};
AI 代码解读

AVL的插入

  1. 如果根节点是nullptr时,进行特殊的判断,直接进行节点的创建
  2. 查找插入的位置,大于在右边,小于在左边
  3. 进行平衡因子的更新,左边插入,父亲节点-1,右边插入,父亲节点+1(可以反向操作)
  4. 在节点更新的时候就要进行判断,只有发大于左右节点不平衡的时候需要旋转
    • 左旋转 、右旋转、左右旋转、右左旋转(下面会详细介绍)
bool insert(const pair<K, V>& kv)
{
   
    //step 1
    if (_root == nullptr)
    {
   
        _root = new Node(kv);
        return true;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    //step 2
    while (cur)
    {
   
        if (kv.first > cur->_kv.first)
        {
   
            parent = cur;
            cur = cur->_right;
        }
        else if (kv.first < cur->_kv.first)
        {
   
            parent = cur;
            cur = cur->_left;
        }
        else
        {
   
            //key 存在
            return false;
        }
    }

    cur = new Node(kv);
    if (kv.first > parent->_kv.first)
    {
   
        parent->_right = cur;
    }
    else
    {
   
        parent->_left = cur;
    }

    cur->_parent = parent;
    //step 3
    //更新平衡因子
    while (parent)
    {
   
        if (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)
        {
   
            if (cur->_bf == 1 && parent->_bf == 2)
            {
   
                RotateL(parent);
            }
            else if (cur->_bf == -1 && parent->_bf == -2)
            {
   
                RotateR(parent);
            }
            else if (cur->_bf == -1 && parent->_bf == 2)
            {
   
                RotateRL(parent);
            }
            else if (cur->_bf == 1 && parent->_bf == -2)
            {
   
                RotateLR(parent);
            }
            break;
        }
        else
        {
   
            assert(false);
        }    
    }
AI 代码解读

AVL左旋

AVL树左旋的条件是:

  1. 当前节点的平衡因子(右子树的高度减去左子树的高度)为2,这意味着当前节点的左子树的高度至少比右子树高2。
  2. 当前节点的右子树必须是一个有效的AVL子树,即它的两个子树的高度差不超过1。
  3. 当前节点的左子树的右子节点(即当前节点的孙子节点)不为空
  • b节点摘下,放在30这个节点的右边
  • 将30这个整体放在60的左边
  • 更改父亲节点的关系,同时要注意的是B子树不为空,如果为空,就不要更新父亲节点。
void RotateL(Node* parent)
{
   
    Node* cur = parent->_right;
    Node* curleft = cur->_left;

    parent->_right = curleft;
    if (curleft)
    {
   
        curleft->_parent = parent;
    }

    cur->_left = parent;

    Node* ppnode = parent->_parent;

    parent->_parent = cur;

    if (ppnode == nullptr)
    {
   
        _root = cur;
        cur->_parent = nullptr;
    }
    else
    {
   
        if (ppnode->_left == parent)
        {
   
            ppnode->_left = cur;
        }
        else
        {
   
            ppnode->_right = cur;
        }

        cur->_parent = ppnode;
    }

    parent->_bf = cur->_bf = 0;
}
AI 代码解读

AVL右旋

AVL树进行右旋操作的条件

  1. 当一个节点的平衡因子(BF)为-2时,表示该节点的左子树的高度至少比右子树高2,这违反了AVL树的平衡性要求。
  2. 同时,该节点的左子节点的平衡因子必须为-1,这意味着左子节点的右子树存在,且其高度至少为1。

右旋的操作和左旋的操作成镜像

void RotateR(Node* parent)
{
   
    Node* cur = parent->_left;
    Node* curright = cur->_right;

    parent->_left = curright;
    if (curright)
    {
   
        curright->_parent = parent;
    }

    cur->_right = parent;
    Node* ppnode = parent->_parent;
    parent->_parent = cur;

    if (ppnode == nullptr)
    {
   
        _root = cur;
        cur->_parent = nullptr;
    }
    else
    {
   
        if (ppnode->_left == parent)
        {
   
            ppnode->_left = cur;
        }
        else
        {
   
            ppnode->_right = cur;
        }
        cur->_parent = ppnode;
    }

    cur->_bf = parent->_bf = 0;

}
AI 代码解读

AVL左-右旋

  1. 首先,找到需要旋转的节点,该节点的左子树的左子树高度大于右子树高度,导致平衡因子绝对值为2。
  2. 对该节点的左子树执行左旋操作,这会使得原节点成为左子树新的右子节点,并且原节点的左子树的右子节点成为新的左子树根节点。
  3. 接着,对原节点执行右旋操作,这会使得原节点成为整个子树的新根节点,并且原节点的左子节点(即之前左子树的右子节点)成为新根节点的左子节点。
  4. 旋转后,更新所有相关节点的父节点指针,并重新计算平衡因子,确保树重新平衡。
void RotateLR(Node* parent)
{
   
    Node* cur = parent->_left;
    Node* curright = cur->_right;
    int bf = curright->_bf;

    RotateL(parent->_left);
    RotateR(parent);

    if (bf == 0)
    {
   
        curright->_bf = 0;
        parent->_bf = 0;
        cur->_bf = 0;
    }
    else if (bf == 1)
    {
   
        parent->_bf = 0;
        cur->_bf = -1;
        curright->_bf = 0;
    }
    else if (bf == -1)
    {
   
        parent->_bf = 1;
        cur->_bf = 0;
        curright->_bf = 0;
    }
    else
    {
   
        assert(false);
    }
}
AI 代码解读

AVL右-左旋

  1. 首先对该节点的左子节点进行右旋操作,这会使得原本的左子节点成为新的根节点,而原来的右子节点成为左子节点的右孩子。
  2. 接着对原来的节点(现在是右子节点的左孩子)进行左旋操作,这会使得原本的右子节点成为新的根节点,原来的节点成为右子节点的左孩子。
  3. 注意更新三者的关系
void RotateRL(Node* parent)
{
   
    Node* cur = parent->_right;
    Node* curleft = cur->_left;
    int bf = curleft->_bf;

    RotateR(parent->_right);
    RotateL(parent);

    //解偶
    if (bf == 0)
    {
   
        parent->_bf = 0;
        cur->_bf = 0;
        curleft->_bf = 0;
    }
    else if (bf == -1)
    {
   
        parent->_bf = 0;
        cur->_bf = 1;
        curleft->_bf = 0;
    }
    else if (bf == 1)
    {
   
        cur->_bf = 0;
        parent->_bf = -1;
        curleft->_bf = 0;
    }
    else
    {
   
        assert(false);
    }
}
AI 代码解读

AVL树的检查

  • 根据AVL的特性,左右子树之间的相差的值小于2.
  • 这就需要进行根节点的高度的计算。
//计算高度
int Height(Node* root)
{
   
    if (root == nullptr)
    {
   
        return 0;
    }

    int leftHeight = Height(root->_left);
    int rightHeight = Height(root->_right);

    return max(leftHeight, rightHeight) + 1;

}
//判断平衡
bool  is_balance(Node* root)
{
   
    if (root == nullptr)
        return true;

    int leftHeight = Height(root->_left);
    int rightHeight = Height(root->_right);

    if (rightHeight - leftHeight != root->_bf)
    {
   
        cout << "balance id abnormal" << endl;
        return false;
    }

    return abs(leftHeight - rightHeight) < 2 && is_balance(root->_left) &&                                  is_balance(root->_right);
}
AI 代码解读

源码

#pragma once


#include<vector>
#include<iostream>
#include<utility>
#include<assert.h>

using namespace std;

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

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

    template<class K, class V>
    class AVL
    {
   
        typedef AVLNode<K, V> Node;
    public:
        AVL()
            :_root(nullptr)
        {
   }

        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 (kv.first > cur->_kv.first)
                {
   
                    parent = cur;
                    cur = cur->_right;
                }
                else if (kv.first < cur->_kv.first)
                {
   
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
   
                    //key 存在
                    return false;
                }
            }

            cur = new Node(kv);
            if (kv.first > parent->_kv.first)
            {
   
                parent->_right = cur;
            }
            else
            {
   
                parent->_left = cur;
            }

            cur->_parent = parent;

            //更新平衡因子
            while (parent)
            {
   
                if (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)
                {
   
                    if (cur->_bf == 1 && parent->_bf == 2)
                    {
   
                        RotateL(parent);
                    }
                    else if (cur->_bf == -1 && parent->_bf == -2)
                    {
   
                        RotateR(parent);
                    }
                    else if (cur->_bf == -1 && parent->_bf == 2)
                    {
   
                        RotateRL(parent);
                    }
                    else if (cur->_bf == 1 && parent->_bf == -2)
                    {
   
                        RotateLR(parent);
                    }
                    break;
                }
                else
                {
   
                    assert(false);
                }    
            }

            return true;
        }


        int Height(Node* root)
         {
   
            if (root == nullptr)
            {
   
                return 0;
            }

            int leftHeight = Height(root->_left);
            int rightHeight = Height(root->_right);

            return max(leftHeight, rightHeight) + 1;

        }

        bool is_balance()
        {
   
            return is_balance(_root);
        }



        bool  is_balance(Node* root)
        {
   
            if (root == nullptr)
                return true;

            int leftHeight = Height(root->_left);
            int rightHeight = Height(root->_right);

            if (rightHeight - leftHeight != root->_bf)
            {
   
                cout << "balance id abnormal" << endl;
                return false;
            }

            return abs(leftHeight - rightHeight) < 2 && is_balance(root->_left) && is_balance(root->_right);
        }

        void RotateLR(Node* parent)
        {
   
            Node* cur = parent->_left;
            Node* curright = cur->_right;
            int bf = curright->_bf;

            RotateL(parent->_left);
            RotateR(parent);

            if (bf == 0)
            {
   
                curright->_bf = 0;
                parent->_bf = 0;
                cur->_bf = 0;
            }
            else if (bf == 1)
            {
   
                parent->_bf = 0;
                cur->_bf = -1;
                curright->_bf = 0;
            }
            else if (bf == -1)
            {
   
                parent->_bf = 1;
                cur->_bf = 0;
                curright->_bf = 0;
            }
            else
            {
   
                assert(false);
            }
        }

        void RotateRL(Node* parent)
        {
   
            Node* cur = parent->_right;
            Node* curleft = cur->_left;
            int bf = curleft->_bf;

            RotateR(parent->_right);
            RotateL(parent);

            //解偶
            if (bf == 0)
            {
   
                parent->_bf = 0;
                cur->_bf = 0;
                curleft->_bf = 0;
            }
            else if (bf == -1)
            {
   
                parent->_bf = 0;
                cur->_bf = 1;
                curleft->_bf = 0;
            }
            else if (bf == 1)
            {
   
                cur->_bf = 0;
                parent->_bf = -1;
                curleft->_bf = 0;
            }
            else
            {
   
                assert(false);
            }
        }


        void RotateR(Node* parent)
        {
   
            Node* cur = parent->_left;
            Node* curright = cur->_right;

            parent->_left = curright;
            if (curright)
            {
   
                curright->_parent = parent;
            }

            cur->_right = parent;
            Node* ppnode = parent->_parent;
            parent->_parent = cur;

            if (ppnode == nullptr)
            {
   
                _root = cur;
                cur->_parent = nullptr;
            }
            else
            {
   
                if (ppnode->_left == parent)
                {
   
                    ppnode->_left = cur;
                }
                else
                {
   
                    ppnode->_right = cur;
                }
                cur->_parent = ppnode;
            }

            cur->_bf = parent->_bf = 0;

        }


        void RotateL(Node* parent)
        {
   
            Node* cur = parent->_right;
            Node* curleft = cur->_left;

            parent->_right = curleft;
            if (curleft)
            {
   
                curleft->_parent = parent;
            }

            cur->_left = parent;

            Node* ppnode = parent->_parent;

            parent->_parent = cur;

            if (ppnode == nullptr)
            {
   
                _root = cur;
                cur->_parent = nullptr;
            }
            else
            {
   
                if (ppnode->_left == parent)
                {
   
                    ppnode->_left = cur;
                }
                else
                {
   
                    ppnode->_right = cur;
                }

                cur->_parent = ppnode;
            }

            parent->_bf = cur->_bf = 0;
        }

    private:
        Node* _root;
    };
}
AI 代码解读

cur;
}
cur->_parent = ppnode;
}

        cur->_bf = parent->_bf = 0;

    }


    void RotateL(Node* parent)
    {
        Node* cur = parent->_right;
        Node* curleft = cur->_left;

        parent->_right = curleft;
        if (curleft)
        {
            curleft->_parent = parent;
        }

        cur->_left = parent;

        Node* ppnode = parent->_parent;

        parent->_parent = cur;

        if (ppnode == nullptr)
        {
            _root = cur;
            cur->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = cur;
            }
            else
            {
                ppnode->_right = cur;
            }

            cur->_parent = ppnode;
        }

        parent->_bf = cur->_bf = 0;
    }

private:
    Node* _root;
};
AI 代码解读

}
~~~

目录
打赏
0
2
2
0
36
分享
相关文章
|
23天前
|
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
56 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
23天前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
40 12
|
23天前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
40 10
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
41 2
|
5月前
|
【C++】AVL树
AVL树是一种自平衡二叉搜索树:它以苏联科学家Georgy Adelson-Velsky和Evgenii Landis的名字命名。
45 2
|
6月前
|
【C++航海王:追寻罗杰的编程之路】关联式容器的底层结构——AVL树
【C++航海王:追寻罗杰的编程之路】关联式容器的底层结构——AVL树
57 5
|
7月前
|
C++
【C++】手撕AVL树(下)
【C++】手撕AVL树(下)
68 1
【C++高阶】掌握AVL树:构建与维护平衡二叉搜索树的艺术
【C++高阶】掌握AVL树:构建与维护平衡二叉搜索树的艺术
47 2
|
7月前
|
【C++】手撕AVL树(上)
【C++】手撕AVL树(上)
69 0
|
23天前
|
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
62 19