目录
前言
一、红黑树概念
二、红黑树的性质
三、红黑树节点定义
四、红黑树的插入
1. 按照二叉搜索树的规则插入新节点
2. 根据红黑树的性质调整树
附录：红黑树实现参考代码
前言
AVL树虽然解决了有序数列插入时二叉树退化的问题，但因AVL树的高度差要求严格导致数据变动时树的旋转频繁，一定程度上降低了运行效率。
为了降低运行效率降低程度，就有了红黑树。
一、红黑树概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
二、红黑树的性质
红黑树满足以下性质：
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
三、红黑树节点定义
enum Color
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _parent;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;std::pair<K, V> _kv;Color _color;RBTreeNode(const std::pair<K, V>& kv = std::pair<K, V>(), Color color = RED):_parent(nullptr),_left(nullptr),_right(nullptr),_kv(kv),_color(color){}
};四、红黑树的插入
红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
1. 按照二叉搜索树的规则插入新节点
2. 根据红黑树的性质调整树
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：
约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点
- cur为红，p为红，g为黑，u存在且为红
直接将p、u节点变黑，g节点变红即可。
如果g的parent为红，则需要继续向上调整。
- cur为红，p为红，g为黑，u不存在/u存在且为黑
p为g的左孩子，cur为p的左孩子，则进行右单旋转；
相反， p为g的右孩子，cur为p的右孩子，则进行左单旋转
p、g变色--p变黑，g变红
- cur为红，p为红，g为黑，u不存在/u存在且为黑
p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；
相反， p为g的右孩子，cur为p的左孩子，则针对p做右单旋转
转换成了情况2
附录：红黑树实现参考代码
RBTree · 梁羽赫/cpp_advanced - 码云 - 开源中国 (gitee.com)
https://gitee.com/yuhe-liang/cpp_advanced/tree/master/RBTree
