由于面试被问到红黑树，特意查阅资料，并做此笔记。
谈到红黑树，首先需要了解二叉搜索树，其特点主要有： 1、有序的，或排序的，二叉树； 2、节点可以有2个子树； 3、左子树的值比较小； 4、右子树的值比较大 下面是一个二叉搜索树的例子： 当一个搜索二叉树变成下面这样，有会怎样呢 可想而知，如果想搜索值为1 的节点，需要遍历所有的节点。他的时间复杂度也就是O(n)。解决这个问题就需要用到平衡搜索树，他的时间复杂度是O(log n)，红黑树是特殊的一种平衡二叉树，其性质有：
1、其节点是红色或黑色。 2、根节点和叶子节点都是黑色（叶子是NIL节点）。 3、每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点） 4、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
额外注释： 1、节点需要一个存储位来跟踪颜色。 2、最长路径（从根到最远的零）不超过最短路径长度的两倍（从根到最近的零）。 -最短路径：所有黑色节点 -最长路径：红黑相间 下面是一个红黑树方便理解：
操作及时间复杂度 1、查询 O(log n) 2、插入 O(log n) 3、删除 O(log n) 空间复杂度为O(n) 其中插入和删除一个节点有可能改变树的结构，可能会违背了红黑树的性质，为了防止出现这一问题，我们需要用到旋转。
1、通过重新排列子树来改变树的结构 2、目标是降低树的高度。 - 红黑树：最大高度 O(log n) - 较大的子树向上，较小的子树向下 3、不影响元素的顺序（较小的节点仍在左边，较大的节点仍在右边）
先不把树分为黑白两色，这样容易理解如何旋转 1、左旋： 向左旋转值为 5 的节点： 5 变成左孩子节点；10 变成父节点；8 变成 5 的右孩子节点；依次画出新的红黑树。下图为旋转之后的样子： 2、右旋： 向右旋转值为 10 的节点： 10 的左孩子 5 变成其父节点；10 变成 5 的右孩子节点；8 变成 10 的左孩子节点；依次画出新的红黑树，如下图： 可以发现：旋转之后的红黑树依旧保持其属性，值较小的节点在左边，值较大的节点在右边。
前面我们已经发现，红黑树是一种自平横的二叉树，当我们插入时也必须保证新树保持平衡。 步骤： 1、插入 Z 节点并将其涂成红色 2、重新着色和旋转节点以修复冲突(维持红黑树的性质) *对于第二步，又分为四种情况： case 1：Z 为根节点 case 2：Z 的叔叔节点为红色 case 3：Z 的叔叔节点为黑色(triangle) case 4：Z 的叔叔节点为黑色(line) case 1：Z 为根节点 只有一个点，直接将节点颜色变为黑色。如下图：
case 2：Z 的叔叔节点为红色 当 Z 父节点的兄弟节点为红色这种情况下，需要改变 Z 节点的父节点、叔叔节点以及 Z 节点的祖父节点的颜色，如下图： case 3：Z 的叔叔节点为黑色(triangle) 如下图，插入 Z 时，Z 节点的叔叔节点为黑色，且 Z节点与 Z 的父节点及Z 的祖父节点的连线为三角形： 在这种情况下，需要旋转A节点和Z节点，如下图： case 4：Z 的叔叔节点为黑色(line) 如下图，插入 Z 时，Z 节点的叔叔节点为黑色，且 Z节点与 Z 的父节点及Z 的祖父节点的连线为直线型： 这种情况下，首先需要旋转B和A，用A替换掉B作为新的根节点，B变成A的左子树，依次建立新的红黑树，如下图： 然后改变颜色，如下图：
总结： 1、Z 为根节点 => 直接变为黑色 2、Z 的叔叔节点为红色 => 改变相应节点的颜色 3、Z 的叔叔节点为黑色(三角型) => 旋转Z与Z的父节点 4、Z 的叔叔节点为黑色(l直线型) => 旋转Z的祖父节点与Z的父节点；并改变相应节点的颜色。
如上图，有一棵红黑树(为了方便，叶子结点没有画出)，现将要插入值为10的节点，具体操作如下所述： 1、10节点需要插在9的右子树上，这时需要旋转红黑树，Z为值为10的节点，uncle为值为13的节点，这时即为上述case 2，改变Z父节点、叔叔节点及祖父节点的颜色，如下图： 2、继而发现，12与15节点的颜色同时为红色，违背了红黑树的性质，则将12看做新插入的Z节点，继续修改，容易发现现在便是case 3 [Z 的叔叔节点为黑色(三角型)]，根据上述改变规则，将12旋转为15的父节点，15旋转为12的右子树根节点，依次建立新的红黑树，如下图： 此时，可以发现，12与15两个节点同时为红色，即为case 4 [Z 的叔叔节点为黑色(line)]，根据上述改变规则，将12旋转为8的父节点，8旋转为12 的左子树根节点，并依次建立新的红黑树，如下图： 最后重新着色： 完毕。
