之前我们在学习set和map的时候说，他们的底层数二叉搜索树，其实这是不准确的，准确的来说他应该是AVL树
那么什么事AVL树呢啊？
但是二叉搜索树有其自身的缺陷，假如往树中 插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此>map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。
如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下：
棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1
如果一棵二叉搜索树是高度平衡的，它就是AVL树。
AVL树节点的定义
template<class K,class V>
struct AVLTreeNOde
{
AVLTreeNOde<K, V>* _left;
AVLTreeNOde<K, V>* _right;
AVLTreeNOde<K, V>* _parent;
int _bf;//平衡因子
pair<K, V> _kv;
AVLTreeNOde(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, parent(nullptr)
, _bf(0)
, _kv(kv);
{}
};
插入：
先按照二叉搜索树的规则插入，当插入到不满足AVL树（平衡因子=-2||==2）的规则的时候进行旋转调整:
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)//插入比较的值是kv里面的key值
{
parent = cur;
cur = cur->right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->left;
}
else//如果有相等的值，那么不插入直接返回false
{
return false;
}
}
//找到了要插入的那个节点的位置 cur==nullpter
cur = new Node(kv);//先构造一个节点
//然后判断是插入在父节点的做还是右
if (parent->_kv.first<kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;//从新更新父节点指针
以上的插入代码和二叉搜索树一样
不一样的是之后的判断调整代码：
平衡因子的更新：
右单旋：
模型特点：
旋转：
代码书写原理：
左单旋，原理和右旋转相同
代码：
//左单旋函数 ： parent=2； 说明右边高 用左旋转法
void rotateL(Node* parent)
{
Node* subR = parent->right;
Node* subRL = subR->left;
parent->right = subRL;
if (subRL)//subR也可能是空，那么他就不存在_parent指针
{
subRL->_parent = parent;
}
Node* pparent = parent->_parent;//记录parent的上一个节点
subR->left = parent;
parent->_parent = subR;
if (parent == _root)//如果是根
{
_root = subR;
subR->_parent = nullptr;
}
else//如果不是根，就要判断翻转的那个子树是右子树还是左子树
{
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->right = subR;
}
subR->_parent = pparent;
}
//翻转完成后还需要改变节点的平衡因子
parent->_bf = 0;
subR->_bf = 0;
}
//右单旋函数 ： parent=-2； 说明左边高 用右旋转法
void rotateR(Node* parent)
{
Node* cuL = parent->_left;
Node* cuLR = cuL->_right;
parent->_left = cuLR;
Node* pparent = parent->_parent;
cuL->right = parent;
if (cuLR)
{
cuLR->_parent = parent;
}
parent->_parent = cuL;
if (parent == _root)
{
_root = cuL;
cul->_parent = nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = cuL;
}
else
{
pparent->_right = cuL;
}
cuL->_parent = pparent;
}
parent->_bf = 0;
cuL->bf = 0;
}
上面螚用左单旋的条件是：插入的节点是在parent的右节点的右节点上
单旋的条件是：插入的节点是在parent的左节点的左节点上
他们具有方向一致性，但是如果插入的节点不一致呢
1、插入的节点在parent的左节点的右节点上
那么先对30（把30这个节点看做parent）进行左单旋，然后再对90进行右单旋，旋转完成后再考虑平衡因子的更新。
左旋和右旋的代码可以直接调用之前的，但是平衡因子是如何更新的呢？
先左旋在右旋的插入有三种情况：
2、插入的节点在parent的右节点的左节点上
那么先对90（把90这个节点看做parent）进行左单旋，然后再对30进行右单旋，旋转完成后再考虑平衡因子的更新。
代码原理和先左旋再右旋相同
void rotateLR(Node* parent)//先左后右
{
Node* subL = parent->_left;
Node* subLR = subL->right;
rotateL(parent->_left);
rotateR(parent->_right);
int bf = subLR->_bf;
if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->bf = 1;
}else if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->bf = 0;
}else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->bf = 0;
}
}
void rotateRL(Node* parent)//先右后左
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
rotateR(parent->_right);
rotateL(parent->_left);
int bf = subRL->_bf;
if (bf == -1)
{
subRL->_bf = 0;
subR->_bf = 1;
parent->_bf = 0;
}
else if (bf == 1)
{
ubRL->_bf = 0;
subR->_bf = 0;
parent->_bf = -1;
}
else if (bf == 0)
{
ubRL->_bf = 0;
subR->_bf = 0;
parent->_bf = 0;
}
}
综上就已经把旋转的所有条件的都囊括了
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);
}
}
