继上一篇的23树，红黑二叉树实质上就是一个23树，在《算法》第四版开篇彩页中，将一颗红黑树展开（未展示nil节点），就是一个23树。
红黑树还是遵循了二叉树的约束，主要就将23树中变异的3-节点恢复成了二叉树中的标准节点——实际上是将3-节点中的左key提取折叠到右key的左子树位置并用红色链接表示；黑色链接代表是普通的1-节点。
对-3连接的折叠
一个红链接，实际上，就是一个-3连接节点中，前两个节点的折叠；比如一个-3节点，有BF两个键，红黑树中规定，左边的键需要降级成为右键的左子节点；
而原本-3节点的左和中节点，转变为了B的左子节点和右子节点。
原书对红黑树的一种等价定义（网上一搜红黑树出来的五个定义，是结论上的定义，这里的定义是从实现角度出发的）：
红链接均为左链接；
没有任何一个节点同时和两条红链接相连；
该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。
对于以上第一条，是一个约定，就像1+1为什么等于2；如果设定红链接都是右链接也没啥关系；
对于第二条，想想把红链接打开的情况：红链接连接的连个节点，在23树中本是平级的存在；如果存在两个连续的红链接，代表有三个节点在同一个级别；这违反了23树的定义；
红黑树既要 保证23树的定义也要保证二叉树的定义。
对于第三条，黑色节点，也就是普通节点，为了保证局部与整体的平衡，需要选装和变色来处理。
红黑树的旋转与变色
关于一二点、在红黑树中需要特别的去维护、如果红链接出现在了右链接，就需要左旋；如果出现了一个节点上有两个红链接，需要变色或是旋转
- 变色
如果一个节点有两个子节点，其链接都是红色，那么其子节点都转为黑色，自身转为红色并将其父链接转为红链接。 - 旋转
如果一个节点其与父节点和子节点的链接有两条红链接，需要视以下情况旋转：
/或\字形，如果两条红链接是这种形状，对其右旋或左旋即可；
>或<字形，如果是这种形状，需要先对中间层节点旋转；
旋转过程同AVL，大概说一说行了。
插入和删除
以上强调的是红链接，原书中也是以链接来解释，能更好提现折叠，但是网上很多都上来直接说红节点和黑节点；
至于插入和删除；插入过程会不断出现违反上述 1,2性质的过程，需要不断旋转和变色，在AVL的旋转上再加些自身逻辑判断即可；
而删除的话，参考RedBlack.pdf吧……
对于删除的补充概括，删除一个节点，难处理的情况主要有两种：
- 删除的节点有子节点并且为红色（这里都不说nil），那么过程和AVL中的删除是一样的，寻找继任者复制待删除元素位置，再删除继任者即可；
- 删除的节点是黑色就恶心了，因为会违反上述第三条原则，红黑树的删除，主要是借鉴了23树的删除：删除3-或4-链接上的节点不会影响树的高度~
之前已经说过，红黑树中的红链接（不说红节点避免晕菜）上的两个节点，对应23树中的3-节点；所以删除红链接上的节点，不会影响树的平衡；
但是如果删除的是一个黑链接上的元素，会影响树的性质，能想到的方法就是将黑链接转为红链接，麻烦的是，红链接代表23数中的3-节点，黑链接代表2-节点，那么就得列举可能出现的情况，对之处理
根据Java的TreeMap的fixAfterDeletion方法，熟悉23树与红黑树后这里使用红节点的说法，将转换时对应的23树画出来：
以下情况，试待删除节点的左节点为current（当然也可以是右节点，这里先讨论待删除节点的左节点为current的情况），待删除节点的右节点为sibling；在变色和旋转之后，要保证current和sibling一直是兄弟关系——指的是对应23树中的兄弟关系；
对于如何移动current和sibling，就像那种早年的九宫格拼图游戏，有一个空白的，努力利用空白将拼图拼完整；这里就是利用红节点；sibling和current围绕红节点来移动保证平衡
- 情况一 sibling为红色：
看到上述结构在23树中，C和E是一个3-节点， 只不过在红黑树中，将E节点描绘成了红色，这里先想办法将C转成红色，如果在23树中，其实很简单，只要将C往X上归并，C就可以变成红黑树中的红节点，如图：
在红黑树中，需要如何操作： 将E变为黑色普通节点，C变为红色节点即可。完整对应关系如下：
然后再对current的parent进行左旋，再将sibling移到current父节点的右节点。
- 情况二 sibling为黑色，且其两个子节点为黑色：
待删除节点C的两个节点AE都是黑色，并且右节点E的两个节点都是黑色，那就好说了，对应23树中可以将DEF提取到一个4-节点~ 如图：
在红黑树中只要将sibling染红即可，然后将current移到current的父节点；这里解释一下为啥要将current往他的父节点移动：因为sibling变红了，代表sibling与其父节点在23树中是一个3-节点，是红黑中同级的的存在！所以要将current往他的父节点移动，以保证current和sibling还是兄弟不会乱伦。
虽然对应的红黑树中他们的关系变了，但是无所谓，红黑树只要保证平衡即可
- 情况三 sibling为黑色，且sibling的右节点为黑色，也叫double black：
- 先将sibling的左节点染黑
- 将sib染红
- 对sib做右旋
- 将sibling移到current的parent的右节点 即可进入情况四
- 情况四 sibling为红色，sibling的右节点为红色：
- 将sibling染成与父节点一样的颜色
- 将current的parent染成黑色
- 将sibling的右节点染黑
- 将current的parent进行左旋
- 将current移到root（即终止循环结束调整）
以上是将要删除的节点的左节点视为current，如果将右节点视为current操作与上述的是对称的。 在上述各种情况中，最终需要的形态是4，与RedBlack.pdf的deleteMax情况相似；
- sibling与current的关系如何保持 在上述的操作中，保持sibling和current是兄弟的操作：首先得看sibling是否为红色，如果是，那么current需要变为sibling的父节点，理由在上面有说；如果sibling是黑色，那么看current的，将sibling移到current的父节点的右节点上（这里是先视current为待删除节点的左节点而言）；
- 旋转 左旋和右旋何时需要？在一二三情况中：当sibling已经是红色了，需要再进一步转为情况4时；需要视情况将其进行旋转，使得情况能接近第四形态
- 为啥要将123形态尽量转为第四形态
第四形态，就是待删除节点的局部deleteMax标准形态，这种情况下删除不会影响整个树的平衡，所以123只是一个过渡，就像拼图过程中的一些技巧。
终上所述，delete就像是一个九宫格拼图，红色节点就是那一块空白，如何围绕这个空白，拼好这个拼图，前人都已经总结好了……