目录
接下来的日子会顺顺利利，万事胜意，生活明朗-----------林辞忧
一：AVL树
1.AVL树的概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查
找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii
和E.M.Landis在1962年
发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右
子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均
搜索长度。
AVL树满足的性质：
1. 它的左右子树都是AVL树
2. 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) (平衡因子=右子树高度-左子树高度)
3. 如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在
O(log_2 n)，搜索时间复杂度O(log_2 n)
2.AVL树插入数据后平衡因子及更新的情况
插入节点时，会影响部分祖先节点的平衡因子，此时就需要更新平衡因子
插入在左树，平衡因子-- 插入在右树，平衡因子++
此时就需要考虑是否继续往上更新祖先，要看当前节点的parent节点所在子树的高度是否发生变化
3.AVL树节点的定义
template<class K,class V>
class AVLTreeNode
{
public:
AVLTreeNode(const pair<K,V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{}
private:
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int bf;//平衡因子
};4.AVL树的插入及旋转
旋转的原则:保持搜索树的规则;控制平衡，降低高度
对于AVL树的旋转分为四种情况:
1.新节点插入较高右子树的右侧---左单旋(单纯右边高)
abc是高度为h(h>=0)的AVL子树
这里画的是抽象图，为了方便理解，这里可以画一些具象图
2.新节点插入较高左子树的左侧--右单旋(单纯左边高)
3.新节点插入较高左子树的右侧---左右：先左单旋再右单旋
具象图分析：
4.新节点插入较高右子树的左侧---右左：先右单旋再左单旋
相关插入及旋转代码
https://gitee.com/lin-ciyu/cplusplus/tree/master/AVLTree/AVLTree
双旋平衡因子的更新情况
二：红黑树
1.红黑树的概念及性质
1.红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或
Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍，因而是接近平衡的
2.红黑树的性质
1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 (一条路径中没有连续的红色节点)
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点(每条路径的黑色节点数量是相等的)
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点(NIL节点))
思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点
个数的两倍
此时考虑极端情况: 最短路径为全黑(高度为h),最长路径为一黑一红(高度为2*h),
一定满足最短路径*2>=最长路径，其它的情况下都是满足最短路径*2>最长路径
但在实际当中最短路径和最长路径不一定存在
2.红黑树节点的定义
enum Colour
{
RED,
BLACK
};
template<class K,class V>
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Colour _col;
RBTreeNode(const pair<K,V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
{}
};对于这里新插入节点的颜色是给红色的，给黑色的话，就会违反性质4，并且会更麻烦，而给红色的话，可能会违反性质3，但通过调整就可以改变
3.红黑树的插入操作情况
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何
性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连
在一起的红色节点，此时需要对红黑树分情况来讨论：
约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点
情况一: cur为红，p为红，g为黑，u存在且为红
如果g是根节点的话，在调整完成后，将g改为黑色
如果g是子树，g一定有双亲，且g的双亲如果为红色，需要继续网上调整
解决方式:将p,u改为黑，g改为红，然后把g当成cur，继续向上调整
部分具象图分析:
情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑
解决方式:p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，
p为g的右孩子，cur为p的右孩子，则进行左单旋转
p、g变色--p变黑，g变红
p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，
p为g的右孩子，cur为p的左孩子，则针对p做右单旋转，转换成上面的情况
部分具象图分析:
相关实现及测试代码
https://gitee.com/lin-ciyu/cplusplus/tree/master/RBTree/RBTree
4.红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O($log_2 N$)，红黑树不追
求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，
所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红
黑树更多