零、前言
本章主要讲解map和set的底层结构平衡二叉搜索树的一种-AVL树的特性及其实现
一、AVL树的概念
- 引入：
map/multimap/set/multiset其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷
假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)
因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现
概念：
对于数据有序或接近有序二叉搜索树将退化为单支树的情况，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年
发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树或者是具有以下性质的二叉搜索树：
它的左右子树都是AVL
树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
示图：
注：如果一棵二叉搜索树是高度可保持在1(-1/0/1)，则非常接近完全二叉树 ，搜索时间复杂度O(logN)
二、AVL树结点定义
为了方便找到子树对应的父亲节点，这里我们选择使用三叉链结构
- 代码实现：
template<class T> struct AVLTreeNode { //三叉链 AVLTreeNode<T>* _left; AVLTreeNode<T>* _right; AVLTreeNode<T>* _parent; int _bf;//平衡因子 T _kv;//T可以是key也可以是pair<K,V>类型便于封装成map或set AVLTreeNode(const T& t) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) ,_kv(t) {} };
三、AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树
那么AVL树的插入过程：
首先按照二叉搜索树的方式插入新节点
待插入结点的key值比当前结点小就插入到该结点的左子树
待插入结点的key值比当前结点大就插入到该结点的右子树
待插入结点的key值与当前结点的key值相等就插入失败
示例：插入12
插入后则向上调整当前结点到根路径上祖先结点的平衡因子
示图：
平衡因子数值=右子树高度-左子树的高度
平衡因子更新规则：
1.如果新增结点在祖父节点的左子树中，则父节点平衡因子数值减1
2.如果新增结点在祖父节点的右子树中，则父节点平衡因子数值加1
平衡因子更新后处理规则：
1.更新后平衡因子为1或-1，那么说明该平衡因子更新前为0，子树的高度发生变化，则也会影响父亲结点的平衡因子，继续向上更新平衡因子
2.更新后平衡因子为0，那么说明该平衡因子更新前为1或-1，子树的高度未发生变化，则也不会影响父亲结点的平衡因子，停止向上更新平衡因子
3.更新后平衡因子为2或-2，那么当前子树不符合AVL树的规则，需要进行旋转子树进行调节高度
注：更新平衡因子之前，该树本身就满足AVL树的规则，平衡因子为1或0或-1
示图：
实现代码：
pair<Node*, bool> Insert(const pair<K,V>& kv) { if (_root == nullptr)//空树的情况 { _root = new Node(kv); return make_pair(_root, true); } //插入需要链接父子节点，但是插入的位置是空节点，需要另一个指针记录父结点 Node* cur = _root, *parent = _root; while (cur) { if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else//找到了相同的 { return make_pair(cur,false); } } //找到插入位置，创建链接节点 cur = new Node(kv); Node* newnode = cur;//记录新结点地址，便于返回 if (parent->_kv.first > kv.first) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; //向上更新平衡因子 while (cur != _root) { if (parent->_right == cur) { 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) { if (cur->_bf == -1)//右单旋 { RotateR(parent); } else//左右双旋 { RotateLR(parent); } } else { if (cur->_bf == 1)//右单旋 { RotateL(parent); } else//右左双旋 { RotateRL(parent); } } break; } else//已经出错了 { assert(false); } } return make_pair(newnode, true); }
