在网上很多博客上面看到有些讲红黑树的文章都不能完整描述它的体系，对于树的调平染色也没有很详细的介绍，因此让很多人觉得红黑树很难理解。但红黑树的应用场景还是很常见的。
JAVA8中HashMap的底层实现，就为了解决过度哈希冲突而造成的长链表，从而将链表转换为红黑树；Linux中的CFS进程调度算法，vruntime利用红黑树来存储；多路复用EPoll核心结构也是采用红黑树和双向链表来存储。
了解红黑树的结构，有助于我们去理解一些底层实现，并且红黑树本身也是对树结构的一种高度应用。包括多叉树、树平衡调整、树节点旋转。其实红黑树的本质就是对2-3-4树的概念模型一种具体实现。
2-3-4树
2-3-4树是阶数为4的B树，B树，全名BalanceTree，平衡树。这种结构主要用来做查找。它最重要的特性在于平衡，这使得我们能够在最坏情况下也保持O(LogN)的时间复杂度实现查找（一个不具备平衡性的查找树可能退化成单链表，时间复杂度会到O（N））。
平衡的定义是说从空链接到根节点距离相等，此处一定要用心理解。（也就是说非叶子节点是不会存在空链接的）
因为2-3-4是一个阶数为4的数，所以他会存在以下几个节点：
- 2结点 2节点中存放着一个key[X]，两个指针，分别指向小于X的子节点和大于X的子节点；
- 3结点 3节点中存放在两个key[X,Y],三个指针，分别指向小于X的子节点，介于X~Y之间的子节点和大于Y的子节点；
- 4结点 4节点中存放在两个key[X,Y,Z],四个指针，理论同上
红黑树
红黑树是对概念模型2-3-4树的一种实现，由于直接进行不同节点间的转化会造成较大的开销，所以选择以二叉树为基础，在二叉树的属性中加入一个颜色属性来表示2-3-4树中不同的节点。
2-3-4树中的2节点对应着红黑树中的黑色节点，而2-3-4树中的非2节点是以红节点+黑节点的方式存在，红节点的意义是与黑色父节点结合，表达着2-3-4树中的3，4节点。
我们先看2-3-4树到红黑树的节点转换。2节点直接转化为黑色节点；3节点这里可以有两种表现形式，左倾红节点或者右倾红节点。而4节点被强制要求转化为一个黑父带着左右两个红色儿子。
本文主要针对2-3树的左倾红黑树进行探讨，也就是说，如果一个树中出现了红色结点，那么这个结点一定是左儿子，这也是算法4中给出的红黑树的实现方式。
- 这种实现方式不用考虑2-3-4树中复杂的4节点分裂
- 这种限定能够很大的减少红黑树调整过程中的复杂性
如果说这样还是比较抽象的话，那下面这个左倾红黑树转2-3树应该能够清晰的描绘他们之间的关系了。
在了解红黑树的插入删除操作之前，我们需要先了解2-3树的插入删除操作，才能理解红黑树中染色和旋转背后的意义。插入操作需要遵循一个原则：
先将这个元素尝试性地放在已经存在的节点中，如果要存放的节点是2节点，那么插入后会变成3节点，如果要存放的节点是3节点，那么插入后会变成4节点（临时）。
然后对可能生成的临时4节点进行分裂处理，使得临时4节点消失。
正对应了红黑树在插入的时候一定会把待插入节点涂成红色，因为红色节点的意义是与父节点进行关联，形成概念模型2-3树中的3节点或者临时4节点。
而红黑树之所以需要在插入后进行调整，正是因为可能存在着概念模型中的临时4节点（反应在红黑树中是双红的情况）。
试想在2-3树中如果待插入节点是个2节点，那么反应在红黑树中，不正好对应着黑色父节点吗，在黑色父节点下面增加一个红色儿子，确实不会违背红黑树的任何规则，这也对应着我们向2-3树中的2节点插入一个元素，只需要简单的把2节点变成3节点。
接下来让我们来看一下对于2-3树的删除。对于2-3树的删除我们主要要考虑待删除元素在2节点这种情况，因为如果待删除元素在3节点，那么可以直接将这个元素删除，而不会破坏2-3树的任何性质（删除这个元素不会引起高度的变化）。
当待删除元素在2节点的时候，由于删除这个元素会导致2节点失去自己唯一的元素，引发2节点自身的删除，会使得树中某条路径的高度发生变化，树变得不平衡。
因此我们有两种方案去解决这个问题：
- 先删除这个2节点，然后对树进行平衡调整。
- 想办法让这个被删除的元素不可能出现在2节点中。
这里选择第二种方案，我们在搜索到这个节点的路径中，不断地判断当前节点是否为2节点，如果是，就从它的兄弟节点或者它的父节点借一个元素，使得当前节点由2节点成为一个3节点或者一个临时4节点（视具体情况而定，在后面的红黑树部分会详细介绍）。
这种操作会产生一种结果：除非当前节点是根节点，否则当前节点的父节点一定是一个非2节点（因为搜索的路径是自上而下，父节点已经进行过了这种操作，所以不可能是2节点），那么我们可以保证到达叶子节点的时候，也能顺利的从父节点或者兄弟节点处借到元素，使得自己成为非2节点。从而能够直接删除某个元素（现在这个元素不在2节点中了）。
再品红黑树
来品一下红黑树的5条定义
红黑树结点颜色的有黑色和红色
2-3树到红黑树的转化已经详细说明
根结点一定是黑色
2-3树中如果根节点为2节点，那么它本来就对应红黑树中黑节点；如果根节点为3节点，也可以用黑色节点表示较大的那个元素，然后较小的元素作为左倾红节点存在于红黑树中
所有叶子节点都是黑色
这里的叶子其实是空链接
任意节点到叶子节点经过的黑色节点数目相同
红黑树中的红节点是和黑色父节点绑定的，在2-3树中本来就是同一层的，只有黑色节点才会在2-3树中真正贡献高度，由于2-3树的任一节点到空链接距离相同，因此反应在红黑树中就是
黑色完美平衡不会有连续的红色节点
2-3树中本来就规定没有4节点，2-3-4树中虽然有4节点，但是要求在红黑树中体现为一黑色节点带两红色儿子，分布左右，所以也不会有连续红节点
现在就能看的出来红黑树的定义背后正浮现着一颗2-3树概念模型。虽然我们已经有了这样的认识，但是红黑树作为真正的实现模型，我们还是要回到这个实现本身来探究它的一系列操作
作为二叉查找树
二叉查找树的节点有一个元素X和两个指针域，左指针指向小于X的元素，右指针指向大于X的元素。
假设我们的插入序列是1~10，那么这颗树会演变成只有右链接的形式，树高会增加到10层，这个时候已经不具备O(LogN)的查找时间复杂度，因为这颗树退化成了链表。
因此对二叉树进行平衡调整是很重要的一个环节，无论是AVL还是红黑树，它们本质上都是希望尽可能保证这颗二叉查找树中的元素尽量均衡的分布在树的两侧。
当我们向一颗二叉查找树中插入一个元素Y的时候，我们会一直与树中的节点进行大小比较，如果Y小于当前元素，就往左走，如果Y大于当前元素，就往右走，直到达到叶子节点，这个时候我们可以把Y插入这颗二叉查找树了。
由于这次的插入动作，整棵树可能会发生一些不平衡，因此我们需要在插入后进行一次平衡调整，使得整棵树恢复到平衡的状态（具体如何调整，要看树是AVL还是红黑树亦或是其他的平衡树）。
二叉查找树的删除是一个很有意思的问题，不同于插入的是，待删除的元素并不能保证一定出现在树中的叶子节点。这将带来一个棘手的情景，即我们需要从树的中间部分取走一个元素，而且在取走后还需要经过调整来使得整颗树满足平衡的性质。从树的中间部分直接取走一个节点的场景实在是太多，也牵扯到了太多相关的节点，这种操作很难实现。
好在有人提出了一个观点，我们对查找树中一个节点的删除，其实可以不必真的改动这个节点的位置。由于查找树的特殊性质，将某个元素节点删除后，它有两个最佳替代者，分别是有序序列中的前驱元素和后继元素。
我们还是以一个包含元素1~10的二叉查找树为例，如果我们希望删除5所在的节点，那么让4或者6替代它的位置都是可行的。作为前驱元素的4，会存放在5所在节点的左子树的最右侧；作为后继元素的6，会存放在5所在节点的右子树的最左侧。
关于这个结论，大家只需稍加思索便可以明白。
现在我们又让问题简化了，也就是说，删除某个节点的时候，我们先找到它的前驱元素或者后继元素（随便选一个），将它的前驱元素直接填到待删除的节点，然后再把它的前驱元素或者后继元素删除。
这个时候问题就转化成了在二叉查找树中删除一个没有左子树的节点（或者是一个没有右子树的节点），我们只需要将这个节点删除再进行对应的平衡调整即可（虽然还是需要调平，但是比直接在树中层删除一个同时具备左右儿子的节点要容易很多）。
注意，此处并没有强调是针对红黑树的操作，因为红黑树和AVL都是二叉查找树，它们都适用这个方法。
树的旋转
为了调平一颗二叉树，使得其左右节点数目分布均匀，通常会选择旋转的手段。你可以把一颗二叉树某节点的左右子树想象成天平上待称量的物品，如果哪边重了，我们就从重的那边拿出一部分，加到轻的那边，以此保持相对的平均。
以X为旋转点的左旋
以X为旋转点的右旋
理解了这些之后，再去看红黑树的插入删除，就能够理解旋转和染色背后的意义了。我们仍然选择算法4中的左倾红黑树作演示：首先看插入
左倾红黑树的插入
对于上述左倾红黑树的插入一共有三种可能的情况：
- 待插入元素比黑父大，插在了黑父的右边，而黑父左边是红色儿子。这种情况会导致在红黑树中出现右倾红节点。
这种情况对应着2-3树中出现了临时4节点，我们在2-3树中的处理是将这个临时4节点分裂，左右元素各自形成一个2节点，中间元素上升到上层跟父节点结合。所以，我们在红黑树中的动作是，将原本红色的左右儿子染黑（左右分裂），将黑父染红（等待上升结合）。
- 待插入元素比红父小，且红父自身就是左倾。听起来有点绕，看图就会明白，其实就是说红父和待插入元素同时靠在了左边，形成了连续的红节点。
这种情况我们需要用两步来调整。由于我们插入的是红色节点，其实不会破坏黑色完美平衡，所以要注意的是在旋转和染色的过程种继续保持这种完美黑色平衡。
首先对红父的父亲进行一次右旋，这次右旋不会破坏黑色平衡，但是也没有解决连续红色的问题。
接下来将12所在节点与15所在节点交换颜色，这样的目的是为了消除连续红色，并且这个操作依旧维持了黑色平衡。现在我们已经得到了情况1的场景，直接按情况1处理即可。
- 待插入元素比红父大，且红父自身就是左倾。
也就是说插入的这个节点形成了一个右倾的红色节点，对右倾的处理很简单，将红父进行一次左旋，就能使得右倾红节点变为左倾，现在出现了连续的左倾红节点，直接按情况2处理即可。
在插入时，可以体会到左倾红黑树对于左倾的限制带来的好处，因为在原树符合红黑树定义的情况下，如果父亲是红的，那么它一定左倾，同时也不用考虑可能存在的右倾兄弟（如果有，那说明原树不满足红黑树定义）。
这种限制消除了很多需要考虑的场景，让插入变得更加简单。
左倾红黑树的删除
左倾红黑树的删除需要借鉴之前提到的二叉查找树通用的删除策略，当我们要删除某个节点的时候选择它的前驱节点或者后继节点元素来替代它，转而删除它的前驱/后继节点。
这里我们用后继节点来替代被删除节点。
假设我们需要删除的节点它的右子树如图所示，那么对该节点的删除实际上转为了对2的删除。
我们从当前的根节点出发，利于2-3树中预合并的策略逐层对红黑树进行调整。具体的做法是，每次都保证当前的节点是2-3树中的非2节点，如果当前节点已经是非2节点，那么直接跳过；如果当前节点是2节点，那么根据兄弟节点的状况来进行调整：
如果兄弟是2节点，那么从父节点借一个元素给当前节点，然后与兄弟节点一起形成一个临时4节点。
如果兄弟是非2节点，那么兄弟上升一个元素到父节点，同时父节点下降一个元素到当前节点，使得当前节点成为一个3节点。
这样的策略能够保证最后走到待删除节点的时候，它一定是一个非2节点，我们可以直接将其元素删除。
接下来要考虑的是修复工作，由于红黑树定义的限制，我们在调整的过程中出现了一些本不该存在的红色右倾节点（因为生成了概念模型中的临时4节点），于是我们顺着搜索的方向向上回溯，如果遇到当前节点具备右倾的红色儿子，那么对当前节点进行一次左旋，这时原本的右儿子会来到当前节点的位置，然后将右儿子与当前节点交换颜色，我们就将右倾红节点修复成了左倾红节点，同时我们并没有破坏黑色节点的平衡。
思考
- 你知道了红黑树的五条定义，如果我构造一颗只有黑色节点的红黑树，这样子可行吗？因为这样子没有破坏任何一条红黑树的规则。
- 那么请问红黑树中要红节点干什么呢？红节点的真实意义是什么呢？
...
...
Copyright by @maybelence.