一、前言
在上一篇文章中对 set、multiset、map、multimap 进行了简单的介绍，在其文档介绍中发现，这几个容器都有一个共同点：其底层都是借助二叉搜索树来实现的。但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成为单支树，时间复杂度会退化成 O ( N ) O(N)O(N)，因此 set、map 等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。那么今天就让我们对 set 和 map 的底层结构一探究竟。
二、AVL 树的概念
二叉搜索树虽然可以缩短查找的效率，但是如果数据有序或者接近有序，二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率就会变得低下。因此，两位俄罗斯的数学家 G.M.Adelson-Velskii 和E.M.Landis 在 1962 年发明了一种解决上述问题的方法：当向二叉搜索树中插入新节点后，如果能保证每个节点的左右子树高度之差的绝对值不超过 1（超过 1 需要对树中的结点进行调整），即可降低树的高度，从而减少平均搜索长度。一颗 AVL 树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是 AVL 树。
- 左右子树高度之差（简称平衡因子）的绝对值不超过 1（-1、0、1）。
小Tips：如果一颗二叉搜索树是高度平均的，它就是 AVL 树。如果它有 n 个结点，其高度可保持在 O ( l o g 2 n ) O(log2^n)O(log2n)，搜索时间复杂度为 O ( l o g 2 n ) O(log2^n)O(log2n)。平衡二叉搜索树中平衡并不是说要让平衡因子始终保持 0，这是做不到的，以两个结点为例，根节点的平衡因子只可能是 1 或者 -1，不可能是 0。二叉搜索树在实际中基本不太可能实现完全平衡，但是理论上可以，即满二叉树。后面我们学的多叉平衡搜索树在现实中可以做到完全平衡。
三、AVL 树结点的定义
template<class K, class V> struct AVLTreeNode { AVLTreeNode(const pair<K, V>& kv = pair<K, V>()) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) {} pair<K, V> _kv;//存储key和value AVLTreeNode<K, V>* _left = nullptr;//指向左孩子 AVLTreeNode<K, V>* _right = nullptr;//指向右孩子 AVLTreeNode<K, V>* _parent = nullptr;//指向父亲结点 int _bf = 0;//平衡因子 };
四、AVL 树的框架
template<class K, class V> class AVLTree { typedef AVLTreeNode<K, V> Node; private: Node* _root = nullptr; };
五、AVL 树的插入
AVL 树就是在二叉搜索树的基础上引入平衡因子，因此 AVL 树也可以看成是二叉搜索树。那么 AVL 树的插入过程可以分为两步：
- 按照二叉搜索树的方式插入新节点。
- 调整结点的平衡因子。
5.1 平衡因子的更新
新结点插入后，AVL 树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了 AVL 树的平衡性。假设新插入的结点为 cur，那么 cur 的平衡因子一定是 0，因为它的左后孩子都是 nullptr。但是 cur 的双亲结点 parent 的平衡因子一定需要调整，在插入之前，parent 的平衡因子分为三种情况：-1、0、1。对 parent 平衡因子的调整分为以下两种情况：
- 如果
cur插入到parent的左侧，只需要给parent的平衡因子 − 1 -1−1 即可。 - 如果
cur插入到parent的右侧，只需要给parent的平衡因子 + 1 +1+1 即可。
此时更新后 parent 的平衡因子有以下三种情况：0 00、± 1 ±1±1、± 2 ±2±2
- 如果
parent的平衡因子为 0 00，说明插入前parent的平衡因子一定为 ± 1 ±1±1，即左右孩子中一定有一个是nullptr，并且新结点就插入在为空的一侧，插入后平衡因子被调整成 0 00，整棵树的高度任然不变，满足 AVL 树的性质，插入成功。 - 如果
parent的平衡因子是 ± 1 ±1±1，说明插入前parent的平衡因子一定是 0 00，即插入前parent的左右孩子都为nullptr，并未新结点就插入在parent的任意一侧，所以插入后平衡因子被调整成了 ± 1 ±1±1，此时以parent为跟的树的高度增加了，需要继续沿着祖先结点向上更新，知道某一个祖先节点的平衡因子变成了 0 00，此时更新结束，插入成功。 - 如果
parent的平衡因子为 ± 2 ±2±2，则parent的平衡因子违反了平衡树的性质，需要对其进行旋转处理。
情况一：
情况二：
情况三：
5.2 AVL 树的旋转
如果在一颗原本是平衡的 AVL 树中插入一个新结点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据结点插入位置的不同，AVL 树的旋转分为四种：
5.2.1 左单旋
新结点插入在较高右子树的右侧----右右：即 parent 的平衡因子是 2 22，cur 的平衡因子是 1 11，此时就需要左单旋。下面举两个左单旋的例子。
例一：
例二：
抽象图：
小Tips：无论是这四种旋转中的哪一个，都要保证以下两点：首先在旋转的过程中要保证这棵树是搜索树，其次经过旋转后，这棵树应该变成平衡树，且降低这个子树的高度。这两点就决定了左旋的核心操作就是将 cur 的左子树给 parent 的右子树，再让 parent 成为 cur 的左子树。
void RotateL(Node* parent) { Node* cur = parent->_right; Node* curleft = cur->_left; parent->_right = curleft; cur->_left = parent; if (curleft) { curleft->_parent = parent; } Node* ppnode = parent->_parent; parent->_parent = cur; if (parent == _root) { _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; }
5.2.2 右单旋
新结点插入在较高左子树的左侧----左左：即 parent 的平衡因子是 − 2 -2−2，cur 的平衡因子是 − 1 -1−1，此时就需要右单旋。
抽象图：
//右单旋 void RotateR(Node* parent) { Node* cur = parent->_left; Node* curright = cur->_right;//此时的情况是curright比cur大，比parent小 parent->_left = curright; cur->_right = parent; if (curright) { curright->_parent = parent; } Node* ppnode = parent->_parent; parent->_parent = cur; if (ppnode) { cur->_parent = ppnode; if (ppnode->_left == parent) { ppnode->_left = cur; } else { ppnode->_right = cur; } } else { _root = cur; cur->_parent = nullptr; } parent->_bf = cur->_bf = 0; }
5.2.3 先右单旋再左单旋
新结点插入在较高右子树的左侧----右左：即 parent 的平衡因子是 2 22，cur 的平衡因子是 − 1 -1−1。此时就需要先以 cur 为旋转点进行一个右单旋，再以 parent 为旋转点进行一个左单旋。下面给大家举两个例子。
例一：
例二：
抽象图：
小Tips：右左双旋的本质是把 60 结点的右边给了 90 结点的左边，把 60 结点的左边给了 30 结点的右边，然后 60 结点变成了这颗子树的跟结点。进行右左双旋后，平衡因子的更新有以下三种情况：
- 插入后 60 结点的平衡因子是 0 00，说明 60 自己就是新增节点，此时
parent和cur的平衡因子都是 0 00。 - 插入后 60 结点的平衡因子是 − 1 -1−1，说明是在 60 结点的左侧插入，此时
parent的平衡因子是 0 00，cur的平衡因子是 − 1 -1−1。 - 插入后 60 结点的平衡因子是 1 11，说明是在 60 结点的右侧插入，此时
parent的平衡因子是 − 1 -1−1，cur的平衡因子是 0 00。
//右左双旋 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 = cur->_bf = curleft->_bf = 0; } else if (bf == 1) { cur->_bf = 0; parent->_bf = -1; curleft->_bf = 0; } else if (bf == -1) { cur->_bf = 1; parent->_bf = 0; curleft->_bf = 0; } }
5.2.4 先左单旋再右单旋
新结点插入在较高左子树的右侧----左右：即 parent 的平衡因子是 − 2 -2−2，cur 的平衡因子是 1 11。此时就需要先以 cur 为旋转点进行一个左单旋，然后再以 parent 为旋转点进行一个右单旋。下面为大家举两个具体的实例。
例一：
例二：
抽象图：
5.3 AVL 树插入完整代码
/*AVLTree.h*/ public: bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true;//插入成功 } //找插入位置 Node* cur = _root; Node* parent = nullptr; while (cur) { 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; } } //找到待插入位置了，进行插入 cur = new Node(kv); if (kv.first < parent->_kv.first) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; //控制平衡 //更新衡因子 while (parent)//我们这里始终更新的是parent的平衡银子，当parent为nullptr说明根节点_root的平衡因子已经被我们更新过了 { //更新平衡因子 if (cur == parent->_left) { --(parent->_bf); } else if (cur == parent->_right) { ++(parent->_bf); } //判断更新后parent的平衡因子 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; } private: //左单旋 void RotateL(Node* parent) { Node* cur = parent->_right; Node* curleft = cur->_left; parent->_right = curleft; cur->_left = parent; if (curleft) { curleft->_parent = parent; } Node* ppnode = parent->_parent; parent->_parent = cur; if (parent == _root) { _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; } //右单旋 void RotateR(Node* parent) { Node* cur = parent->_left; Node* curright = cur->_right;//此时的情况是curright比cur大，比parent小 parent->_left = curright; cur->_right = parent; if (curright) { curright->_parent = parent; } Node* ppnode = parent->_parent; parent->_parent = cur; if (ppnode) { cur->_parent = ppnode; if (ppnode->_left == parent) { ppnode->_left = cur; } else { ppnode->_right = cur; } } else { _root = cur; cur->_parent = nullptr; } parent->_bf = cur->_bf = 0; } //右左双旋 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 = cur->_bf = curleft->_bf = 0; } else if (bf == 1) { cur->_bf = 0; parent->_bf = -1; curleft->_bf = 0; } else if (bf == -1) { cur->_bf = 1; parent->_bf = 0; curleft->_bf = 0; } } //左右双旋 void RotateLR(Node* parent) { Node* cur = parent->_left; Node* curright = cur->_right; int bf = curright->_bf; RotateL(cur); RotateR(parent); if (bf == 0) { parent->_bf = cur->_bf = curright->_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; } }
5.4 AVL 树的验证
AVL 树是在二叉搜索树的基础上加入了平衡的限制，因此要验证 AVL 树，可以分为两步：
- 验证其为二叉搜索树。如果中序遍历可以得到一个有序的序列，就说明为二叉搜索树。
- 验证其为平衡树。每个结点左右子树高度差的绝对值不超过 1 11。其次检查结点的平衡因子是否计算正确。
public: //中序 void Inorder() { return _Inorder(_root); } //检测平衡因子 bool IsBlance() { return _IsBalance(_root); } private: //中序 void _Inorder(Node* root) { if (root == nullptr) { return; } _Inorder(root->_left); cout << root->_kv.first << ' '; _Inorder(root->_right); return; } //求树的高度 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; } //检测平衡因子 bool _IsBalance(Node* root) { if (root == nullptr) { return true; } int leftHeight = Height(root->_left); int rightHeight = Height(root->_right); if (rightHeight - leftHeight != root->_bf) { cout << "平衡因子异常:" << root->_bf << endl; return false; } return abs(leftHeight - rightHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right); }
/*test.c*/ int main() { int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; wcy::AVLTree<int, int> t; for (auto e : a) { t.Insert(make_pair(e, e)); t.Inorder(); cout << endl; if (t.IsBlance()) { cout << "成功插入:" << e << endl; } else { cout << e << "插入失败" << endl; } } return 0; }
六、AVL 树的删除
因为 AVL 树也是二叉搜索树，可以按照二叉搜索树的方式将结点删除，然后再更新平衡因子，只不过与删除插入不同的是，删除结点后的平衡因子更新，最差情况下一直要调整到根结点的位置。具体的实现感兴趣的小伙伴可以参考《算法导论》或者《数据结构-用面向对象方法与C++描述》殷人昆版。
七、AVL 树的性能
AVL 树是一颗绝对平衡的二叉搜索树，其要求每个结点的左右子树高度差的绝对值都不超过 1 11，这样在查询时可以保证高效的时间复杂度，即 O ( l o g 2 n ) O(log2^n)O(log2n)。但是如果要对 AVL 树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此，如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑 AVL 树，但一个结构经常修改，就不太适合。
八、结语
今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，春人的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是春人前进的动力！
