目录
gitee对应仓库
红黑树的概念
红黑树的规则
红黑树如何保证最长路径不超过最短路径的2倍？
红黑树的效率分析O(logN)
红黑树的节点
插入
左右判别：
仅变色
旋转
旋转过程
单旋+变色
↓子树推断(在原本的c为黑色的情况下)
变色推断
双旋+变色
额外NIL节点
gitee对应仓库
红黑树的概念
红黑树是一棵二叉搜索树，每个节点增加一个存储位来表示节点颜色，可以是红色或者黑色。通过对任何一条根到叶子的路径上各个节点的颜色进行约束，红黑树确保没有一条路径比其他路径长度过于两倍。
红黑树的规则
1.每个节点不是红色就是黑色
2.根节点是黑色的
3.如果一个节点是红色的，则它的两个节点必须的黑色的。也就是说任意一条路径不会有连续的红色节点。
4.从任一根节点节点到其所有null节点的黑色节点个数相等。
红黑树如何保证最长路径不超过最短路径的2倍？
引入b：根节点到nullptr的黑色节点个数。
极端情况：
最长：黑红间隔分布长度2b。
最短：全为黑色长度为b。
所以最长路径不超过最短路径的2倍。
红黑树的效率分析O(logN)
假设N为节点个数，h为最短路径的长度，那么2^h - 1 <= N <= 2^(2*h) - 1
完全二叉树 完全二叉树
取对数得h ≈ logN N个节点即最多查找次数为2logN次 O(logN)
红黑树的节点
enum Colour { RED, BLACK }; // 这里我们默认按key/value结构实现 template<class K, class V> struct RBTreeNode { // 这里更新控制平衡也要加入parent指针 std::pair<K, V> _kv; RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; Colour _col; RBTreeNode(const std::pair<K, V>& kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) { } };插入
1.插入一个值按二叉搜索树的规则进行插入，插入后我们只需要观察是否符合红黑树的四条规则。
2.如果是非空树擦入，新增节点必须是红色。如果是空树插入，新增节点是黑色节点。
※3.非空树插入后如果父节点是黑色则插入完成。
※4.明显继续探究的前提是插入后f是红色的情况，则g节点必须为黑色(原树无连续红色)又有c为红色所以其三者的的颜色已经确定。 因此我们进行"变色、旋转的依据主要是u的存在与否和颜色"。
因此进入插入循环的条件是：while (parent && parent->_col == RED)
左右判别：
参考对象为u与p的相对位置 // p的位置下为c
决定因素是parent == grandfa->left。 ucl为后定义因素
仅变色
ucl存在且为红
无论x的来源是什么
g变红 p u变黑
c = g p = c->parent 继续向上更新
旋转
单旋+变色 u不存在 或 u存在为黑
c是新插入的 c是更新得来的
若c不是新插入的则是更新来的 不满足p为红的事实 为什么？c只有两种途径形成 若c是新增来的那么新增前：
不符合规则
旋转过程
单旋+变色
g作单旋点
↓子树推断(在原本的c为黑色的情况下)
假设a为hb 则b为hb
d为hb+1
e、f为hb
变色推断
//err g不能为红 因为为红p必定为红出现连续红 所以g为黑
①p变为黑 承接上与下
②g变为红
双旋+变色
双旋+变色 u不存在 或 u存在为黑
c是新插入的 c是更新得来的
若c不是新插入的则是更新来的 不满足p为红的事实 为什么？c只有两种途径形成 若c是新增来的那么新增前：
不符合规则
g p c呈现折线型
额外NIL节点
部分书籍在红黑树的末端(nullptr)处补充一叫作NIL的外部节点该节点为黑色。 //作用于标记支路结束。
