红黑树详解，理解红黑树的每个细节_哔哩哔哩_bilibili
最常用的平衡2叉树
不具备严格的平衡熟悉
查找、插入、删除的平均使用性能非常好
每个节点有一个专门的属性记录自己是黑还是红，是维护平衡的重要属性
各种不同的平衡2叉树，区别就是维护平衡的方式不同
红黑树就是按颜色维护
AVL 根据左右子树的高度差
树堆 根据结点的优先级
红黑树的5条性质
节点要么红要么黑
根是黑的
叶节点是黑色的空节点
所有的红色节点的2跟孩子都是黑的
任意节点到其可到达的叶节点之间有相同数量的黑节点
黑色高度一致性
(一个节点到所有他能到的叶节点的路径，每条路径黑色节点数相同)
时间复杂度
旋转规则
插入
按正常搜索树加入节点
新节点染红
双红颜色修正
为什么新节点要染红而不是染黑？
这样更容易使加入新节点的树更快恢复红黑树的性质
双红修正
节点左右旋转
改变颜色
自底向上的过程
三种场景
情况1
父和叔双红的情况：
让他们变黑，让祖父变红
循环，把祖父当node节点重复双红修正，自底向上不断循环（如果循环后祖父节点满足红黑树则停止，否则向上循环判定，若是根节点，则根节点变黑）
情况2
没有叔叔，再分2个情况，分别是node为左孩子，node为右孩子
左孩子时：让父黑，祖父红，对祖父右旋
右孩子时：node染黑，祖父染红，对父节点左旋，再对祖父节点右旋
情况3：
是情况2的对称情况