前言
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一、AVL树的概念
AVL树的名字来源于它的发明作者G.M. Adelson-Velsky 和 E.M. Landis。AVL树是最先发明的自平衡二叉查找树（Self-Balancing Binary Search Tree,简称平衡二叉树）。
AVL树的定义：它或者是一颗空树，或者具有以下性质的二叉排序树：它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。
AVL树的性质：
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O ( l o g 2 n ) O(log_2 n)O(log 2 n)，搜索时间复杂度O ( l o g 2 n ) O(log_2 n)O(log 2 n)。
二、AVL树节点的定义
AVL树节点的定义：
template<class K, class V> struct AVLTreeNode { pair<K, V> _kv; AVLTreeNode<K, V>* _left; //该节点的左孩子 AVLTreeNode<K, V>* _right; //该节点的右孩子 AVLTreeNode<K, V>* _parent; //该节点的双亲 int _bf; //平衡因子 AVLTreeNode(const pair<K,V>& kv) //构造函数 :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) {} };
三、AVL树的插入操作
AVL树就是在二叉搜索树的基础之上引入了平衡因子，因此AVL树也可以看出是二叉搜索树。那么AVL树的插入过程可以分成两部分：
- 按照二叉搜索树的方式插入新节点
- 调整平衡因子，若遇到平衡因子不符合AVL树的规则，则需要进行旋转操作
bool Insert(const pair<K, V>& kv) { // 1、搜索树的插入规则 // 2、看是否违反平衡规则，若违反则需要“旋转”处理 if (_root == nullptr) { _root = new Node(kv); _root->_bf = 0; 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) //最远更新到parent { if (cur == parent->_right) { parent->_bf++; } else { parent->_bf--; } //判断是否继续更新 if (parent->_bf == 0) { break; } else if (parent->_bf == -1 || parent->_bf == 1) // 此时插入结点的那边变高了 { //继续更新祖先 cur = cur->_parent; parent = parent->_parent; } else if (parent->_bf == -2 || parent->_bf == 2) // 插入结点使得本来高的一边又变高了 -> 旋转 { if (parent->_bf == 2 && cur->_bf == 1) // 左单旋 { // 左单旋 } else if (parent->_bf == -2 && cur->_bf == -1) // 右单旋 { // 右单旋 } else if (parent->_bf == -2 && cur->_bf == 1) // 左右双旋 { // 左右双旋 } else if (parent->_bf == 2 && cur->_bf == -1) // 右左双旋 { // 右左双旋 } else { assert(false); } break; } else { assert(false); // 树本来就存在问题 } } return true; }
四、AVL树的旋转
如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种。
1. 左单旋
新节点插入较高右子树的右侧—右右，即需要左单旋。
图示：
左单旋代码;
void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if(subRL) subRL->_parent = parent; Node* grandParent = parent->_parent; subR->_left = parent; parent->_parent = subR; if (parent == _root) { _root = subR; subR->_parent = nullptr; } else { if (parent == grandParent->_left) { grandParent->_left = subR; } else { grandParent->_right = subR; } subR->_parent = grandParent; } subR->_bf = parent->_bf = 0; //更新平衡因子 }
2. 右单旋
新节点插入较高左子树的左侧—左左，即需要右单旋。
图示:
右单旋代码：
void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; Node* grandParent = parent->_parent; subL->_right = parent; parent->_parent = subL; if (parent == _root) { _root = subL; subL->_parent = nullptr; } else { if (parent == grandParent->_left) { grandParent->_left = subL; } else { grandParent->_right = subL; } subL->_parent = grandParent; } subL->_bf = parent->_bf = 0; }
3. 左右双旋
新节点插入较高左子树的右侧—左右，即需要先左单旋再右单旋。
图示：
此时在60的子树插入一个新节点就会引起左右双旋，插入分为左子树插入和右子树插入。这两种情况的插入完成之后对其平衡因子的更新有所不同，因此旋转完成后需要讨论更新其平衡因子。
当60结点不存在时也需要单独讨论
实现代码：复用左、右单旋。
void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(parent->_left); RotateR(parent); //更新平衡因子 if (1 == bf) subL->_bf = -1; else if (-1 == bf) parent->_bf = 1; else { assert(false); } }
4. 右左双旋
新节点插入较高右子树的左侧—右左，即需要先右单旋再左单旋。
右左双旋与左右双旋类似。
代码实现：
void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent->_right); RotateL(parent); //更新平衡因子 if (1 == bf) { parent->_bf = -1; } else if(-1 == bf) { subR->_bf = 1; } else { assert(false); } }
5. 总结
假如以parent为根的子树不平衡，即parent的平衡因子为2或者-2，分以下情况考虑
- parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为subR，当subR的平衡因子为1时，执行左单旋；当subR的平衡因子为-1时，执行右左双旋。
- parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为subL，当subL的平衡因子为-1是，执行右单旋；当subL的平衡因子为1时，执行左右双旋。
- 旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新。
五、AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：
1、验证其为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树。
验证代码如下：
void InOrder() { _InOrder(_root); cout << endl; } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << " "; _InOrder(root->_right); }
2、验证其为平衡树
验证规则：
- 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子的情况)
- 节点的平衡因子是否计算正确
验证代码如下：
bool IsBalanceTree() { return _IsBalanceTree(_root); } bool _IsBalanceTree(Node* root) { // 空树也是AVL树 if (nullptr == root) return true; // 计算root节点的平衡因子：即root左右子树的高度差 int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); int diff = rightHeight - leftHeight; // 如果计算出的平衡因子与root的平衡因子不相等，或者 // root平衡因子的绝对值超过1，则一定不是AVL树 if (abs(diff) >= 2) //每个节点子树高度差的绝对值不超过1 { cout << root->_kv.first << "节点平衡因子异常" << endl; return false; } if (diff != root->_bf) //节点的平衡因子是否计算正确 { cout << root->_kv.first << "节点平衡因子不符合实际" << endl; return false; } // root的左和右如果都是AVL树，则该树一定是AVL树 return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right); }
六、AVL树的性能分析
- AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即O ( l o g 2 n ) O(log_2 n)O(log 2 n)。
- 但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。
实现AVL树的完整代码
#pragma once #include<assert.h> #include<iostream> #include<vector> #include<queue> using namespace std; template<class K, class V> struct AVLTreeNode { pair<K, V> _kv; AVLTreeNode<K, V>* _left; //该节点的左孩子 AVLTreeNode<K, V>* _right; //该节点的右孩子 AVLTreeNode<K, V>* _parent; //该节点的双亲 int _bf; //平衡因子 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) { // 1、搜索树的插入规则 // 2、看是否违反平衡规则，若违反则需要“旋转”处理 if (_root == nullptr) { _root = new Node(kv); _root->_bf = 0; 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) //最远更新到parent { if (cur == parent->_right) { parent->_bf++; } else { parent->_bf--; } //判断是否继续更新 if (parent->_bf == 0) { break; } else if (parent->_bf == -1 || parent->_bf == 1) // 此时插入结点的那边变高了 { //继续更新祖先 cur = cur->_parent; parent = parent->_parent; } else if (parent->_bf == -2 || parent->_bf == 2) // 插入结点使得本来高的一边又变高了 -> 旋转 { if (parent->_bf == 2 && cur->_bf == 1) // 左单旋 { RotateL(parent); } else if (parent->_bf == -2 && cur->_bf == -1) // 右单旋 { RotateR(parent); } else if (parent->_bf == -2 && cur->_bf == 1) // 左右双旋 { RotateLR(parent); } else if (parent->_bf == 2 && cur->_bf == -1) // 右左双旋 { RotateRL(parent); } else { assert(false); } break; } else { assert(false); // 树本来就存在问题 } } return true; } void InOrder() { _InOrder(_root); cout << endl; } bool IsBalanceTree() { return _IsBalanceTree(_root); } vector<vector<int>> levelOrder() { vector<vector<int>> vv; if (_root == nullptr) return vv; queue<Node*> q; int levelSize = 1; q.push(_root); while (!q.empty()) { // levelSize控制一层一层出 vector<int> levelV; while (levelSize--) { Node* front = q.front(); q.pop(); levelV.push_back(front->_kv.first); if (front->_left) q.push(front->_left); if (front->_right) q.push(front->_right); } vv.push_back(levelV); for (auto e : levelV) { cout << e << " "; } cout << endl; // 上一层出完，下一层就都进队列 levelSize = q.size(); } return vv; } int Height() { return _Height(_root); } private: bool _IsBalanceTree(Node* root) { // 空树也是AVL树 if (nullptr == root) return true; // 计算root节点的平衡因子：即root左右子树的高度差 int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); int diff = rightHeight - leftHeight; // 如果计算出的平衡因子与root的平衡因子不相等，或者 // root平衡因子的绝对值超过1，则一定不是AVL树 if (abs(diff) >= 2) // 每个节点子树高度差的绝对值不超过1 { cout << root->_kv.first << "节点平衡因子异常" << endl; return false; } if (diff != root->_bf) // 节点的平衡因子是否计算正确 { cout << root->_kv.first << "节点平衡因子不符合实际" << endl; return false; } // root的左和右如果都是AVL树，则该树一定是AVL树 return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right); } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << " "; _InOrder(root->_right); } int _Height(Node* root) { if (root == nullptr) return 0; int lh = _Height(root->_left); int rh = _Height(root->_right); return lh > rh ? lh + 1 : rh + 1; } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if(subRL) subRL->_parent = parent; Node* grandParent = parent->_parent; subR->_left = parent; parent->_parent = subR; if (parent == _root) { _root = subR; subR->_parent = nullptr; } else { if (parent == grandParent->_left) { grandParent->_left = subR; } else { grandParent->_right = subR; } subR->_parent = grandParent; } subR->_bf = parent->_bf = 0; //更新平衡因子 } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; Node* grandParent = parent->_parent; subL->_right = parent; parent->_parent = subL; if (parent == _root) { _root = subL; subL->_parent = nullptr; } else { if (parent == grandParent->_left) { grandParent->_left = subL; } else { grandParent->_right = subL; } subL->_parent = grandParent; } subL->_bf = parent->_bf = 0; } void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(parent->_left); RotateR(parent); //更新平衡因子 if (1 == bf) subL->_bf = -1; else if (-1 == bf) parent->_bf = 1; 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 (1 == bf) { parent->_bf = -1; } else if(-1 == bf) { subR->_bf = 1; } else { assert(false); } } private: Node* _root = nullptr; };
