C++从入门到起飞之——AVL树 全方位剖析！
🌈个人主页：秋风起，再归来~
🔥系列专栏：C++从入门到起飞
🔖克心守己，律己则安
目录
1. AVL的概念
• AVL树是最先发明的⾃平衡⼆叉查找树，AVL是⼀颗空树，或者具备下列性质的⼆叉搜索树：它的 左右⼦树都是AV树，且左右⼦树的⾼度差的绝对值不超过1。AVL树是⼀颗⾼度平衡搜索⼆叉树， 通过控制⾼度差去控制平衡。
• AVL树得名于它的发明者G.M.Adelson-Velsky和E.M.Landis是两个前苏联的科学家，他们在1962 年的论⽂《An algorithm or the organization of information》中发表了它。
• AVL树实现这⾥我们引⼊⼀个平衡因⼦(balance factor)的概念，每个结点都有⼀个平衡因⼦，任何 结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度，也就是说任何结点的平衡因⼦等于0/1/-1， AVL树并不是必须要平衡因⼦，但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡， 就像⼀个⻛向标⼀样。
• 思考⼀下为什么AVL树是⾼度平衡搜索⼆叉树，要求⾼度差不超过1，⽽不是⾼度差是0呢？0不是更 好的平衡吗？画画图分析我们发现，不是不想这样设计，⽽是有些情况是做不到⾼度差是0的。⽐ 如⼀棵树是2个结点，4个结点等情况下，⾼度差最好就是1，⽆法作为⾼度差是0
• AVL树整体结点数量和分布和完全⼆叉树类似，⾼度可以控制在 ，那么增删查改的效率也可 以控制在，相⽐⼆叉搜索树有了本质的提升。
2. AVL树的实现
2.1 AVL树的结构
节点的结构：
template<class K,class V> struct AVLTreeNode { pair<K, V> _kv; AVLTreeNode* _parent; AVLTreeNode* _right; AVLTreeNode* _left; int _bf;//平衡因子 AVLTreeNode(const pair<K,V>& kv) :_kv(kv) , _parent(nullptr) , _right(nullptr) ,_left(nullptr) ,_bf(0) {} };树的结构：
template<class K, class V> class AVLTree { public: typedef AVLTreeNode<K,V> Node; //...... private: Node* _root=nullptr; };2.2 AVL树的插⼊
>AVL树插⼊⼀个值的⼤概过程
1. 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊。
2. 新增结点以后，只会影响祖先结点的⾼度，也就是可能会影响部分祖先结点的平衡因⼦，所以更新 从新增结点->根结点路径上的平衡因⼦，实际中最坏情况下要更新到根，有些情况更新到中间就可 以停⽌了，具体情况我们下⾯再详细分析。
3. 更新平衡因⼦过程中没有出现问题，则插⼊结束
4. 更新平衡因⼦过程中出现不平衡，对不平衡⼦树旋转，旋转后本质调平衡的同时，本质降低了⼦树 的⾼度，不会再影响上⼀层，所以插⼊结束
>平衡因⼦更新
更新原则：
• 平衡因⼦=右⼦树⾼度-左⼦树⾼度
• 只有⼦树⾼度变化才会影响当前结点平衡因⼦。
• 插⼊结点，会增加⾼度，所以新增结点在parent的右⼦树，parent的平衡因⼦++，新增结点在 parent的左⼦树，parent平衡因⼦--
• parent所在⼦树的⾼度是否变化决定了是否会继续往上更新
更新停⽌条件：
• 更新后parent的平衡因⼦等于0，更新中parent的平衡因⼦变化为-1->0或者1->0，说明更新前 parent⼦树⼀边⾼⼀边低，新增的结点插⼊在低的那边，插⼊后parent所在的⼦树⾼度不变，不会 影响parent的⽗亲结点的平衡因⼦，更新结束。
• 更新后parent的平衡因⼦等于1或-1，更新前更新中parent的平衡因⼦变化为0->1或者0->-1，说 明更新前parent⼦树两边⼀样⾼，新增的插⼊结点后，parent所在的⼦树⼀边⾼⼀边低，parent所 在的⼦树符合平衡要求，但是⾼度增加了1，会影响arent的⽗亲结点的平衡因⼦，所以要继续向上 更新。
• 更新后parent的平衡因⼦等于2或-2，更新前更新中parent的平衡因⼦变化为1->2或者-1->-2，说 明更新前parent⼦树⼀边⾼⼀边低，新增的插⼊结点在⾼的那边，parent所在的⼦树⾼的那边更⾼ 了，破坏了平衡，parent所在的⼦树不符合平衡要求，需要旋转处理，旋转的⽬标有两个：
1、把 parent⼦树旋转平衡。
2、降低parent⼦树的⾼度，恢复到插⼊结点以前的⾼度。所以旋转后也不 需要继续往上更新，插⼊结束。
>插⼊结点及更新平衡因⼦的代码实现
bool insert(const pair<K, V>& kv) { //如果树为空，直接在根插入 if (_root == nullptr) { _root = new Node(kv); return true; } //树不为空，先按照搜索树规则找到插入位置 Node* parent = nullptr; Node* cur = _root; while (cur) { //插入的key小就往左走 if (kv.first < cur->_kv.first) { parent = cur; cur = cur->_left; } //大就往右走 else if (kv.first > cur->_kv.first) { parent = cur; cur = cur->_right; } else//不支持键值冗余 { return false; } } //找到在parent插入的位置了 cur = new Node(kv); if (kv.first < parent->_kv.first) parent->_left = cur; else parent->_right = cur; //不要忘记链接新增节点的parent cur->_parent = parent; //开始更新平衡因子 while (parent) { if (parent->_left == cur) parent->_bf--; else parent->_bf++; //_bf从1或-1到0,不会影响祖先节点 if (parent->_bf == 0) { break; } //_bf从0到1或-1，会影响祖先节点，继续向上更新 else if (parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = parent->_parent; } //平衡破坏，旋转恢复平衡 else if (parent->_bf == 2 || parent->_bf == -2) { //旋转逻辑 //........ break;//旋转完后，该节点的平衡因子为0，无需向上更新 } else//非预想平衡因子，直接断死 { assert(false); } } return true; }2.3 旋转
2.3.1 旋转的原则
1. 保持搜索树的规则
2. 让旋转的树从不满⾜变平衡，其次降低旋转树的⾼度 旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。
说明：下⾯的图中，有些结点我们给的是具体值，如10和5等结点，这⾥是为了⽅便讲解，实际中是什 么值都可以，只要⼤⼩关系符合搜索树的规则即可。
2.3.2 右单旋
具象图
抽象图
2.3.3 右单旋代码实现
//右单旋 void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; Node* pParent = parent->_parent; parent->_left = subLR; if(subLR)//如果不为空 subLR->_parent = parent; subL->_right = parent; parent->_parent = subL; if (pParent == nullptr) { _root = subL; subL->_parent = nullptr; } else { if (pParent->_left == parent) { pParent->_left = subL; } else { pParent->_right = subL; } subL->_parent = pParent; } parent->_bf = subL->_bf = 0; }2.3.4 左单旋
具象图
抽象图
2.3.5 左单旋代码实现
//左单旋 void RotateL(Node* parent) { Node* pParent = parent->_parent; Node* subR = parent->_right; Node* subRL = subR->_left; subR->_left = parent; parent->_parent = subR; parent->_right = subRL; if (subRL) subRL->_parent = parent; if (pParent == nullptr) { _root = subR; subR->_parent = nullptr; } else { if (pParent->_left == parent) { pParent->_left = subR; } else { pParent->_right = subR; } subR->_parent = pParent; } parent->_bf = subR->_bf = 0; }2.3.6 左右双旋
具象图
抽象图
2.3.7左右双旋代码实现
//左右双旋 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; parent->_bf = 1; subLR->_bf = 0; } else if(bf == 1) { subL->_bf = -1; parent->_bf = 0; subLR->_bf = 0; } else if (bf == 0) { subL->_bf = 0; parent->_bf = 0; subLR->_bf = 0; } else { assert(false); } }2.3.8 右左双旋
2.3.9 右左双旋代码实现
//右左双旋 void RotateRL(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; parent->_bf = 0; subRL->_bf = 0; } else if (bf == 1) { subR->_bf = 0; parent->_bf = -1; subRL->_bf = 0; } else if (bf == 0) { subR->_bf = 0; parent->_bf = 0; subRL->_bf = 0; } else { assert(false); } }2.4 AVL树的查找
按⼆叉搜索树逻辑实现即可，搜索效率为O(logN)
//查找 Node* find(const K& key) { Node* cur = _root; while (cur) { if (cur->_kv.first == key) { return cur; } else if (key < cur->_kv.first) { cur = cur->_left; } else { cur = cur->_right; } } return nullptr; }2.5 AVL树平衡检测
我们实现的AVL树是否合格，我们通过检查左右⼦树⾼度差的的程序进⾏反向验证，同时检查⼀下结点 的平衡因⼦更新是否出现了问题。
//中序遍历 Node* _Inorder(Node* root) { if (root == nullptr) return nullptr; _Inorder(root->_left); cout << "{" << root->_kv.first << "," << root->_kv.second << "}" << endl; _Inorder(root->_right); return root; }//计算树的高度 int _Height(Node* root) { if (root == nullptr) return 0; 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 0; int CountL = _Size(root->_left); int CountR = _Size(root->_right); return CountL + CountR + 1; }//判断是否是AVL树 bool _IsBalanceTree(Node* root) { //空树也是AVL树 if (root == nullptr) return true; int LHeight = _Height(root->_left); int RHeight = _Height(root->_right); int ret = RHeight - LHeight; if (abs(ret) >= 2) { cout << root->_kv.first << "高度差异常" << endl << "高度差为：" << ret << endl; return false; } if (ret != root->_bf) { cout << root->_kv.first << "平衡因子异常" << endl; return false; } return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right); }#include"AVLTree.h" #include<vector> void TestRotate() { AVLTree<int, int> t; // 常规的测试⽤例 //int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; // 特殊的带有双旋场景的测试⽤例 int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; for (auto e : a) { t.insert({ e,e }); } t.Inorder(); cout << t.IsBalanceTree() << endl; } void TestTreeBalance() { const int N = 1000; srand((unsigned int)time(nullptr)); AVLTree<int, int> t; vector<int> v; for (int i = 0; i < N; i++) { v.push_back(rand() + i); } for (auto e : v) { t.insert({ e,e }); } cout << t.Height() << endl;; cout << t.Size() << endl; cout << t.IsBalanceTree() << endl; } int main() { //TestRotate(); TestTreeBalance(); return 0; }
3. 源码
#pragma once #include<assert.h> #include<iostream> using namespace std; template<class K,class V> struct AVLTreeNode { pair<K, V> _kv; AVLTreeNode* _parent; AVLTreeNode* _right; AVLTreeNode* _left; int _bf;//平衡因子 AVLTreeNode(const pair<K,V>& kv) :_kv(kv) , _parent(nullptr) , _right(nullptr) ,_left(nullptr) ,_bf(0) {} }; template<class K, class V> class AVLTree { public: typedef AVLTreeNode<K,V> Node; //插入 bool insert(const pair<K, V>& kv) { //如果树为空，直接在根插入 if (_root == nullptr) { _root = new Node(kv); return true; } //树不为空，先按照搜索树规则找到插入位置 Node* parent = nullptr; Node* cur = _root; while (cur) { //插入的key小就往左走 if (kv.first < cur->_kv.first) { parent = cur; cur = cur->_left; } //大就往右走 else if (kv.first > cur->_kv.first) { parent = cur; cur = cur->_right; } else//不支持键值冗余 { return false; } } //找到在parent插入的位置了 cur = new Node(kv); if (kv.first < parent->_kv.first) parent->_left = cur; else parent->_right = cur; //不要忘记链接新增节点的parent cur->_parent = parent; //开始更新平衡因子 while (parent) { if (parent->_left == cur) parent->_bf--; else parent->_bf++; //_bf从1或-1到0,不会影响祖先节点 if (parent->_bf == 0) { break; } //_bf从0到1或-1，会影响祖先节点，继续向上更新 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 && parent->_left->_bf == -1) { RotateR(parent); } //纯粹右边高进行左单旋 else if (parent->_bf == 2 && parent->_right->_bf == 1) { RotateL(parent); } //不纯粹左边高进行左右双旋 else if (parent->_bf == -2 && parent->_left->_bf == 1) { RotateLR(parent); } //不纯粹右边高进行右左双旋 else if (parent->_bf == 2 && parent->_right->_bf == -1) { RotateRL(parent); } break;//旋转完后，该节点的平衡因子为0，无需向上更新 } else//非预想平衡因子，直接断死 { assert(false); } } return true; } //查找 Node* find(const K& key) { Node* cur = _root; while (cur) { if (cur->_kv.first == key) { return cur; } else if (key < cur->_kv.first) { cur = cur->_left; } else { cur = cur->_right; } } return nullptr; } //中序遍历 void Inorder() { _Inorder(_root); } //计算树的高度 int Height() { return _Height(_root); } //计算树的节点个数 int Size() { return _Size(_root); } //判断是否是AVL树 bool IsBalanceTree() { return _IsBalanceTree(_root); } private: //右单旋 void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; Node* pParent = parent->_parent; parent->_left = subLR; if(subLR)//如果不为空 subLR->_parent = parent; subL->_right = parent; parent->_parent = subL; if (pParent == nullptr) { _root = subL; subL->_parent = nullptr; } else { if (pParent->_left == parent) { pParent->_left = subL; } else { pParent->_right = subL; } subL->_parent = pParent; } parent->_bf = subL->_bf = 0; } //左单旋 void RotateL(Node* parent) { Node* pParent = parent->_parent; Node* subR = parent->_right; Node* subRL = subR->_left; subR->_left = parent; parent->_parent = subR; parent->_right = subRL; if (subRL) subRL->_parent = parent; if (pParent == nullptr) { _root = subR; subR->_parent = nullptr; } else { if (pParent->_left == parent) { pParent->_left = subR; } else { pParent->_right = subR; } subR->_parent = pParent; } parent->_bf = subR->_bf = 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; parent->_bf = 1; subLR->_bf = 0; } else if(bf == 1) { subL->_bf = -1; parent->_bf = 0; subLR->_bf = 0; } else if (bf == 0) { subL->_bf = 0; parent->_bf = 0; subLR->_bf = 0; } else { assert(false); } } //右左双旋 void RotateRL(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; parent->_bf = 0; subRL->_bf = 0; } else if (bf == 1) { subR->_bf = 0; parent->_bf = -1; subRL->_bf = 0; } else if (bf == 0) { subR->_bf = 0; parent->_bf = 0; subRL->_bf = 0; } else { assert(false); } } //中序遍历 Node* _Inorder(Node* root) { if (root == nullptr) return nullptr; _Inorder(root->_left); cout << "{" << root->_kv.first << "," << root->_kv.second << "}" << endl; _Inorder(root->_right); return root; } //计算树的高度 int _Height(Node* root) { if (root == nullptr) return 0; 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 0; int CountL = _Size(root->_left); int CountR = _Size(root->_right); return CountL + CountR + 1; } //判断是否是AVL树 bool _IsBalanceTree(Node* root) { //空树也是AVL树 if (root == nullptr) return true; int LHeight = _Height(root->_left); int RHeight = _Height(root->_right); int ret = RHeight - LHeight; if (abs(ret) >= 2) { cout << root->_kv.first << "高度差异常" << endl << "高度差为：" << ret << endl; return false; } if (ret != root->_bf) { cout << root->_kv.first << "平衡因子异常" << endl; return false; } return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right); } private: Node* _root=nullptr; };4、完结散花
好了，这期的分享到这里就结束了~
如果这篇博客对你有帮助的话，可以用你们的小手指点一个免费的赞并收藏起来哟~
如果期待博主下期内容的话，可以点点关注，避免找不到我了呢~
我们下期不见不散~~
