在复习红黑树的实现时，被网上的一些讲解绕很晕，比如说：这篇。
红黑树本身是一颗二叉查找树，其查询、插入、删除等操作的时间复杂度都在O(lgn)，其检索流程与二叉查找树流程无二，与普通二叉查找树的区别就在于它通过不同着色来进行约束，在插入、删除过程中通过旋转及重新着色来重新满足约束，这句话说这比较绕，下面通过流程图来诠释这句话。不列举任何代码，通过图形来描述整个红黑树插入时的调整过程。
红黑树基本特性及操作
首先列举红黑树的五个特性：
1. 节点是红色或黑色。
2. 根节点是黑色。
3. 每个叶节点（NIL节点，空节点）是黑色的。
4. 不能有相邻接的两个红色节点
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
红黑树的左旋右旋操作：
右旋即将当前节点调转至其左孩子节点的右节点，左旋则为右孩子的左节点，红黑树旋转只此两种，注意旋转操作可能会导致部分叶子节点至根节点的黑色节点的数量与其他不同，即违背特性5，可以通过重新着色来重新满足特性5，下面在描述状态23的调整时会提及。
红黑树的插入
红黑树的插入操作分为两个步骤，
- 第一找到插入节点位置，即需要替换的叶子节点位置
- 第二针对插入后的红黑树进行调整，对于不满足特性的节点进行迭代调节，以便插入后的红黑树仍能保持这五项特性
为了避免每次插入都重新进行平衡，红黑树插入的新节点染色成红色(插入黑色节点必然会破坏特性5)。
但是当其父节点为红色时，则需要进行调节来保证红黑树的完备性。要想能够用最少的调整次数完成红黑树的平衡，整个流程还是比较复杂的。
插入节点为红色，那么会出现以下几种情况：
- 父节点为黑色(状态1)，没有违背5项特性，完成插入
-
父节点为红色，此时又分为四种情况(实际为两种，状态2、状态3，另外两种为状态2、3的镜像状态)：
image.png
调节过程的主要思想为：将红色节点向上调节至根节点，当调整至根节点后，通过将红色染成黑色以完成最终的平衡。当根节点的左右子节点分别满足特性1-5时，根节点为黑色自然也不会破坏5项特性。
[重申]红黑树的左旋右旋操作：
右旋即将当前节点调转至其左孩子节点的右节点，左旋则为右孩子的左节点，红黑树旋转只此两种，注意旋转操作可能会导致部分叶子节点至根节点的黑色节点的数量与其他不同，即违背特性5，可以通过重新着色来重新满足特性5，下面在描述状态23的调整时会提及。
状态2调整：
经过调整后，红色节点上移，后继续遍历P节点。
镜像操作：
状态3调整
调整后，变为状态2(可以与上文中状态2的初始状态比较一下)。再根据状态2的调整方式进行调整。
镜像操作：
结论
因为发生冲突只会存在于两个邻接节点为红色时，冲突的场景被归纳为状态2与状态3，状态而可以通过旋转将红色节点上级，并完成下游节点的冲突处理，而状态三则可以通过旋转+染色变成状态2，从而根据状态2的调整策略完成红色节点的上移。红黑树插入的策略就是：
1. 当前节点是否为状态1->是。无需调整，结束
否->
2. 是否为根节点->是。重新着色为黑色。结束
否->
3. 是否为状态2->是。调整，节点上移，继续步骤1
否->
4. 为状态3-> 旋转+着色，继续步骤2
