【C++】AVL树的底层以及实现

个人主页

⭐一、AVL树的概念

AVL树是一种高度平衡的平衡二叉树，相比于搜刮二叉树，它的特点在于左右子树都为AVL树且树的高度差的绝对值不高出1。
这里我们会引入一个新的概念叫做平衡因子。平衡因子也就是左右子树的高度差，我们可以通过平衡因子方便我们后续去观察和控制树是否平衡。

🎉二、AVL树的性子

AVL树重要有三大性子：
1.每棵树的左右子树都是AVL树。
2.左子树和右子树的高度之差的绝对值不高出1。
3.每个节点都会有一个平衡因子，且任何一个节点的平衡因子都为1、0、-1。
🏝️三、AVL树的实现

1. 树的根本结构

AVL树的结点包罗了左右节点的指针以及父亲节点的指针，同时另有有key、value以及代表树平衡的平衡因子。

1. template<class K, class V>
2. struct AVLTreeNode
3. {
4.         pair<K, V> _kv;
5.         AVLTreeNode<K, V>* _left;
6.         AVLTreeNode<K, V>* _right;
7.         AVLTreeNode<K, V>* _parent;
8.         //平衡因子
9.         int _bf;
10.         AVLTreeNode(const pair<K, V>& kv)
11.                 :_kv(kv)
12.                 , _left(nullptr)
13.                 , _right(nullptr)
14.                 , _parent(nullptr)
15.                 , _bf(0)
16.         {}
17. };

复制代码

2. 树的插入

树的插入按照搜刮二叉树的规则举行插入。插入节点后更新平衡因子，假如没有违反规则(即没有导致节点的平衡因子酿成2/-2)，则插入竣事；假如违反规则，则树会不平衡，须要举行旋转操纵。
平衡因子的更新规则：
1.平衡因子 = 右子树高度 - 左子树高度。
2.只有子树高度的变革才会影响当前节点的平衡因子。
3.插入节点后会增长数的高度，若新增节点在parent的右子树，则parent的平衡因子++，相反在parent的左子树时，则平衡因子- -。
每更新完一个节点的平衡因子都须要举行以下判断：
1.假如parent的平衡因子便是1/-1时，阐明parent原先的平衡因子为0，插入节点后左子树或右子树的高度增长了，阐明还须要向上更新平衡因子。
2.假如parent的平衡因子便是0，阐明parent原先的平衡因子为1/-1，插入节点后左右两棵子树从不平衡变平衡了，阐明无需更新平衡因子。
3.假如parent的平衡因子便是2/-2时，阐明parent原先的平衡因子便是1/-1，插入节点后插入到了较高的那一棵子树，阐明此时以parent为根节点的子树已经不平衡了，须要举行旋转处置惩罚。

1. bool Insert(const pair<K, V>& kv)
2. {
3.         //如果树为空，则插入的节点就是根节点
4.         if (_root == nullptr)
5.         {
6.                 _root = new Node(kv);
7.                 return true;
8.         }
9.         Node* parent = nullptr;
10.         Node* cur = _root;
11.         while (cur)
12.         {
13.                 if (cur->_kv.first < kv.first)
14.                 {
15.                         parent = cur;
16.                         cur = cur->_right;
17.                 }
18.                 else if (cur->_kv.first > kv.first)
19.                 {
20.                         parent = cur;
21.                         cur = cur->_left;
22.                 }
23.                 else
24.                 {
25.                         return false;
26.                 }
27.         }
28.         cur = new Node(kv);
29.         if (parent->_kv.first < kv.first)
30.         {
31.                 parent->_right = cur;
32.         }
33.         else
34.         {
35.                 parent->_left = cur;
36.         }
37.         cur->_parent = parent;
38.         //更新平衡因子
39.         while (parent)
40.         {
41.                 if (cur == parent->_left)
42.                 {
43.                         parent->_bf--;
44.                 }
45.                 else
46.                         parent->_bf++;
47.                 if (parent->_bf == 0)
48.                 {
49.                         break;
50.                 }
51.                 else if (parent->_bf == 1 || parent->_bf == -1)
52.                 {
53.                         //继续往上进行更新
54.                         cur = parent;
55.                         parent = parent->_parent;
56.                 }
57.                 else if (parent->_bf == 2 || parent->_bf == -2)
58.                 {
59.                         //不平衡，旋转处理
60.                         if (parent->_bf == -2 && cur->_bf == -1)
61.                         {
62.                                 RotateR(parent);
63.                         }
64.                         else if(parent->_bf == 2 && cur->_bf == 1)
65.                         {
66.                                 RotateL(parent);
67.                         }
68.                         else if (parent->_bf == -2 && cur->_bf == 1)
69.                         {
70.                                 RotateLR(parent);
71.                         }
72.                         else if (parent->_bf == 2 && cur->_bf == -1)
73.                         {
74.                                 RotateRL(parent);
75.                         }
76.                         else
77.                         {
78.                                 assert(false);
79.                         }
80.                 }
81.                 else
82.                 {
83.                         assert(false);
84.                 }
85.                 break;
86.         }
87.         return true;
88. }

复制代码

3. 树的旋转

旋转的目标就是让树从失衡到平衡，低沉树的高度。
旋转重要分为四种，分别为左单旋、右单旋、左右双旋和右左双旋。下面我们具体讲讲每一种旋转的内部逻辑。
• 左单旋

条件：新节点插入到子树较高的右侧。
我们用图来感受一下其旋转的过程：

1.先将15的左子树的节点12酿成10的右子树。
2.再将10酿成15的左子树，15成为新树的根节点。
3.更新平衡因子
由于左单旋的情况许多，我们也可以用一张抽象图来体现：

代码所示：

1. //左单旋
2. void RotateL(Node* parent)
3. {
4.         Node* subR = parent->_right;
5.         Node* subRL = subR->_left;
6.         parent->_right = subR;
7.         if (subRL)
8.                 subRL->_parent = parent;
9.         Node* pparent = parent->_parent;
10.         if (pparent == nullptr)
11.         {
12.                 _root = subR;
13.                 subR->_parent = nullptr;
14.         }
15.         else
16.         {
17.                 if (pparent == parent->_right)
18.                 {
19.                         parent->_right = subR;
20.                 }
21.                 else
22.                 {
23.                         parent->_left = subR;
24.                 }
25.                 subR->_parent = pparent;
26.         }
27.         parent->_bf = subR->_bf = 0;
28. }

复制代码

• 右单旋

条件：新节点插入到子树较高的左侧
用图来感受旋转的过程：

我们会发现和左单旋和相似
1.先将5的右子树的值b酿成10的左子树。
2.再将10酿成5的右子树，旋转完后5成为整棵树的根节点。
3.更新平衡因子。
代码所示：

1. //右单旋
2. void RotateR(Node* parent)
3. {
4.         Node* subL = parent->_left;
5.         Node* subLR = subL->_right;
6.         parent->_left = subLR;
7.         if(subLR)
8.                 subLR->_parent = parent;
9.         Node* pparent = parent->_parent;
10.         subL->_right = parent;
11.         parent->_parent = subL;
12.         if (pparent == nullptr)
13.         {
14.                 _root = subL;
15.                 subL->_parent = nullptr;
16.         }
17.         else
18.         {
19.                 if (pparent == parent->_left)
20.                 {
21.                         parent->_left = subL;
22.                 }
23.                 else
24.                 {
25.                         parent->_right = subL;
26.                 }
27.                 subL->_parent = pparent;
28.         }
29.         parent->_bf = subL->_bf = 0;
30. }

复制代码

• 左右双旋

条件：新节点插入到较高左子树的右侧。
下面我们用图来演示一下其旋转过程：
1.插入新节点

2.以节点5为旋转点举行左单旋

3.以节点为10举行右单旋

4.旋转完后更新平衡因子。
平衡因子又分为三种情况：
1.当subLR的平衡因子为-1时，左右双旋后parent、subL,subLR的平衡因子分别为1、0、0。
2.当subLR的平衡因子为1时，左右双旋后parent、subL,subLR的平衡因子分别为0、-1、0。
3.当subLR的平衡因子为0时，左右双旋后parent、subL,subLR的平衡因子分别为0、0、0。
代码所示：

1.         //左右双旋
2.         void RotateLR(Node* parent)
3.         {
4.                 Node* subL = parent->_left;
5.                 Node* subLR = subL->_right;
6.                 int bf = subLR->_bf;
7.                 RotateL(parent->_left);
8.                 RotateR(parent);
9.                 if (bf == -1)
10.                 {
11.                         subLR->_bf = 0;
12.                         subL->_bf = 0;
13.                         parent->_bf = 1;
14.                 }
15.                 else if (bf == 1)
16.                 {
17.                         subLR->_bf = 0;
18.                         subL->_bf = -1;
19.                         parent->_bf = 0;
20.                 }
21.                 else if (bf == 0)
22.                 {
23.                         subLR->_bf = 0;
24.                         subL->_bf = 0;
25.                         parent->_bf = 0;
26.                 }
27.                 else
28.                 {
29.                         assert(false);
30.                 }
31.         }

复制代码

• 右左双旋

条件：插入到较高右子树的左侧
其旋转过程和左右双旋雷同，这就不逐一枚举了。
旋转完过后也是须要更新平衡因子，平衡因子也是跟左右双旋一样有三种情况。
代码所示：

1. //右左双旋
2. void RotateRL(Node* parent)
3. {
4.         Node* subR = parent->_right;
5.         Node* subRL = subR->_left;
6.         int bf = subRL->_bf;
7.         RotateR(parent);
8.         RotateL(parent);
9.         if (bf == 0)
10.         {
11.                 subR->_bf = 0;
12.                 subRL->_bf = 0;
13.                 parent->_bf = 0;
14.         }
15.         else if (bf == 1)
16.         {
17.                 subR->_bf = 0;
18.                 subRL->_bf = 0;
19.                 parent->_bf = -1;
20.         }
21.         else if (bf == -1)
22.         {
23.                 subR->_bf = 1;
24.                 subRL->_bf = 0;
25.                 parent->_bf = 0;
26.         }
27.         else
28.         {
29.                 assert(false);
30.         }
31. }

复制代码

🎡四、AVL树的别的功能

1. 树的查找

界说一个cur指针从树的根节点开始查找，按一下规则举行查找：
1.当key的值小于当前节点的值时，则在该节点的左边举行查找。
2.当key的值大于当前节点的值时，则在该节点的右边举行查找。
3.若key的值便是当前节点的值时，则阐明查找乐成，返回true。
4.若遍历完还没查找到该节点的值，则阐明没有此节点，返回false。
代码所示：

1.         Node* Find(const K& key)
2.         {
3.                 Node* cur = _root;
4.                 while (cur)
5.                 {
6.                         if (cur->_kv.first < key)
7.                         {
8.                                 cur = cur->_right;
9.                         }
10.                         else if (cur->_kv.first > key)
11.                         {
12.                                 cur = cur->_left;
13.                         }
14.                         else
15.                         {
16.                                 return cur;
17.                         }
18.                 }
19.                 return nullptr;
20.         }

复制代码

2. 树的遍历

我们遍历方式有前序、中序、后序、层序等方式，我们在这就采取中序遍历的方式来遍历树的每一节点。
代码所示：

1. void _Inorder(Node* root)
2. {
3.         if (root == nullptr)
4.         {
5.                 return;
6.         }
7.         _Inorder(root->_left);
8.         cout << root->_kv.first << ":" << root->_kv.second << endl;
9.         _Inorder(root->_right);
10. }

复制代码

3. 树的高度

1. int _Height(Node* root)
2. {
3.         if (root == nullptr)
4.         {
5.                 return;
6.         }
7.         int leftHeight = _Height(root->_left);
8.         int rightHeight = _Height(root->_right);
9.         return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
10. }

复制代码

4. 树的巨细

返回左子树+右子树再加上根节点即可。

1. int _Size(Node* root)
2. {
3.         if (root == nullptr)
4.         {
5.                 return;
6.         }
7.         return _Size(root->_left) + _Size(root->_right) + 1;
8. }

复制代码

🚀五、总结

1. AVL树的优缺点

优点：
**1.查找服从高：**由于AVL树总是保持平衡，其高度相对较低，因此查找操纵的时间复杂度为O(log2N)，服从较高。
2.结构稳固： AVL树的平衡性使得其结构相对稳固，不会出现非常不平衡的情况，从而包管了操纵的稳固性和可靠性。
缺点：
1.插入和删除复杂： AVL树在插入和删除节点时，大概须要通过旋转操纵来保持树的平衡，比力复杂。
2.大概导致性能降落： 在频仍插入和删除的场景下，AVL树须要不停地举行旋转操纵来保持平衡，这就有大概导致性能低沉。
2. 完备代码

1. #include<iostream>#include<assert.h>using namespace std;template<class K, class V>struct AVLTreeNode{        // 须要parent指针，后续更新平衡因子可以看到        pair<K, V> _kv;        AVLTreeNode<K, V>* _left;        AVLTreeNode<K, V>* _right;        AVLTreeNode<K, V>* _parent;        //平衡因子        int _bf; // balance factor        AVLTreeNode(const pair<K, V>& kv)                :_kv(kv)                , _left(nullptr)                , _right(nullptr)                , _parent(nullptr)                , _bf(0)        {}};template<class K,class V>class AVLTree{        typedef        AVLTreeNode<K, V> Node;public:        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 (parent->_kv.first < 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 (parent->_bf == -2 && cur->_bf == -1)                                {                                        RotateR(parent);                                }                                else if(parent->_bf == 2 && cur->_bf == 1)                                {                                        RotateL(parent);                                }                                else if (parent->_bf == -2 && cur->_bf == 1)                                {                                        RotateLR(parent);                                }                                else if (parent->_bf == 2 && cur->_bf == -1)                                {                                        RotateRL(parent);                                }                                else                                {                                        assert(false);                                }                        }                        else                        {                                assert(false);                        }                        break;                }                return true;        }                //右单旋        void RotateR(Node* parent)        {                Node* subL = parent->_left;                Node* subLR = subL->_right;                parent->_left = subLR;                if(subLR)                        subLR->_parent = parent;                Node* pparent = parent->_parent;                subL->_right = parent;                parent->_parent = subL;                if (pparent == nullptr)                {                        _root = subL;                        subL->_parent = nullptr;                }                else                {                        if (pparent == parent->_left)                        {                                parent->_left = subL;                        }                        else                        {                                parent->_right = subL;                        }                        subL->_parent = pparent;                }                parent->_bf = subL->_bf = 0;        }        //左单旋        void RotateL(Node* parent)        {                Node* subR = parent->_right;                Node* subRL = subR->_left;                parent->_right = subR;                if (subRL)                        subRL->_parent = parent;                Node* pparent = parent->_parent;                if (pparent == nullptr)                {                        _root = subR;                        subR->_parent = nullptr;                }                else                {                        if (pparent == parent->_right)                        {                                parent->_right = subR;                        }                        else                        {                                parent->_left = subR;                        }                        subR->_parent = pparent;                }                parent->_bf = subR->_bf = 0;        }        //左右双旋
2.         void RotateLR(Node* parent)
3.         {
4.                 Node* subL = parent->_left;
5.                 Node* subLR = subL->_right;
6.                 int bf = subLR->_bf;
7.                 RotateL(parent->_left);
8.                 RotateR(parent);
9.                 if (bf == -1)
10.                 {
11.                         subLR->_bf = 0;
12.                         subL->_bf = 0;
13.                         parent->_bf = 1;
14.                 }
15.                 else if (bf == 1)
16.                 {
17.                         subLR->_bf = 0;
18.                         subL->_bf = -1;
19.                         parent->_bf = 0;
20.                 }
21.                 else if (bf == 0)
22.                 {
23.                         subLR->_bf = 0;
24.                         subL->_bf = 0;
25.                         parent->_bf = 0;
26.                 }
27.                 else
28.                 {
29.                         assert(false);
30.                 }
31.         }
32.         //右左双旋        void RotateRL(Node* parent)        {                Node* subR = parent->_right;                Node* subRL = subR->_left;                int bf = subRL->_bf;                RotateR(parent);                RotateL(parent);                if (bf == 0)                {                        subR->_bf = 0;                        subRL->_bf = 0;                        parent->_bf = 0;                }                else if (bf == 1)                {                        subR->_bf = 0;                        subRL->_bf = 0;                        parent->_bf = -1;                }                else if (bf == -1)                {                        subR->_bf = 1;                        subRL->_bf = 0;                        parent->_bf = 0;                }                else                {                        assert(false);                }        }        void Inorder()        {                _Inorder(_root);                cout << endl;        }        void Hight()        {                return _Hight(_root);        }        void Size()        {                return _Size(_root);        }private:        void _Inorder(Node* root)        {                if (root == nullptr)                {                        return;                }                _Inorder(root->_left);                cout << root->_kv.first << ":" << root->_kv.second << endl;                _Inorder(root->_right);        }        int _Height(Node* root)        {                if (root == nullptr)                {                        return;                }                int leftHeight = _Height(root->_left);                int rightHeight = _Height(root->_right);                return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;        }        int _Size(Node* root)        {                if (root == nullptr)                {                        return;                }                return _Size(root->_left) + _Size(root->_right) + 1;        }        Node* Find(const K& key)
33.         {
34.                 Node* cur = _root;
35.                 while (cur)
36.                 {
37.                         if (cur->_kv.first < key)
38.                         {
39.                                 cur = cur->_right;
40.                         }
41.                         else if (cur->_kv.first > key)
42.                         {
43.                                 cur = cur->_left;
44.                         }
45.                         else
46.                         {
47.                                 return cur;
48.                         }
49.                 }
50.                 return nullptr;
51.         }
52. private:        Node* _root = nullptr;};

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金