[TOC] ### **什么是红黑树** ***** 红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。 `红黑树`，是一棵二叉查找树，满足二叉查找树的一般性质。 ` ` **红黑树的5个性质** 1. **每个结点要么是红的要么是黑的。**   2. **根结点是黑的。**   3. **每个叶节点(nil节点, 空节点)是黑色的。 注意： 这里的叶子节点是`nil叶子`**   4. **每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）** 5.  **从任一节点到其每个`叶子`的所有路径都包含相同数目的黑色节点**。 >注意： 性质 3 中指定红黑树的每个叶子节点都是空节点，而且并叶子节点都是黑色。但 Java 实现的红黑树将使用 null 来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，反而看到每个叶子节点都是红色的。 ` ` 性质 4 的意思是：从每个根到节点的路径上不会有两个连续的红色节点，但黑色节点是可以连续的。 因此若给定黑色节点的个数 N，最短路径的情况是连续的 N 个黑色，树的高度为 N - 1;最长路径的情况为节点红黑相间，树的高度为 2(N - 1) 。 ` ` 性质 5 是成为红黑树最主要的条件，后序的插入、删除操作都是为了遵守这个规定。 ` `  ### 红黑树的应用 红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。 例如，Java集合中的[TreeSet](http://www.cnblogs.com/skywang12345/p/3311268.html)和[TreeMap](http://www.cnblogs.com/skywang12345/p/3310928.html)，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。 ` ` ### 红黑树基本操作 #### **红黑树的左旋右旋** ***** 红黑树的基本操作是**添加**、**删除**。在对红黑树进行添加或删除之后，都会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转，可以使这颗树重新成为红黑树。简单点说，旋转的目的是让树保持红黑树的特性。 旋转包括两种：**左旋**和**右旋**。下面分别对它们进行介绍。 ` `  对x进行左旋，意味着"将x变成一个左节点"。 ##### **左旋** 左旋的伪代码《算法导论》：参考上面的示意图和下面的伪代码，理解“红黑树T的节点x进行左旋”是如何进行的： ``` LEFT-ROTATE(T, x) y ← right[x] // 前提：这里假设x的右孩子为y。下面开始正式操作 right[x] ← left[y] // 将 “y的左孩子” 设为 “x的右孩子”，即 将β设为x的右孩子 p[left[y]] ← x // 将 “x” 设为 “y的左孩子的父亲”，即 将β的父亲设为x p[y] ← p[x] // 将 “x的父亲” 设为 “y的父亲” if p[x] = nil[T] then root[T] ← y // 情况1：如果 “x的父亲” 是空节点，则将y设为根节点 else if x = left[p[x]] then left[p[x]] ← y // 情况2：如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子” else right[p[x]] ← y // 情况3：(x是它父节点的右孩子) 将y设为“x的父节点的右孩子” left[y] ← x // 将 “x” 设为 “y的左孩子” p[x] ← y // 将 “x的父节点” 设为 “y” ``` 理解左旋之后，看看下面一个更鲜明的例子。你可以先不看右边的结果，自己尝试一下。  ` ` ##### **右旋**  对x进行左旋，意味着"将x变成一个左节点"。 ` ` 右旋的伪代码《算法导论》：参考上面的示意图和下面的伪代码，理解“红黑树T的节点y进行右旋”是如何进行的。 ``` RIGHT-ROTATE(T, y) x ← left[y] // 前提：这里假设y的左孩子为x。下面开始正式操作 left[y] ← right[x] // 将 “x的右孩子” 设为 “y的左孩子”，即 将β设为y的左孩子 p[right[x]] ← y // 将 “y” 设为 “x的右孩子的父亲”，即 将β的父亲设为y p[x] ← p[y] // 将 “y的父亲” 设为 “x的父亲” if p[y] = nil[T] then root[T] ← x // 情况1：如果 “y的父亲” 是空节点，则将x设为根节点 else if y = right[p[y]] then right[p[y]] ← x // 情况2：如果 y是它父节点的右孩子，则将x设为“y的父节点的左孩子” else left[p[y]] ← x // 情况3：(y是它父节点的左孩子) 将x设为“y的父节点的左孩子” right[x] ← y // 将 “y” 设为 “x的右孩子” p[y] ← x // 将 “y的父节点” 设为 “x” ``` 理解右旋之后，看看下面一个更鲜明的例子。你可以先不看右边的结果，自己尝试一下:  **旋转总结**： (01) 左旋 和 右旋 是相对的两个概念，原理类似。理解一个也就理解了另一个。 (02) 下面谈谈如何区分 左旋 和 右旋。 在实际应用中，若没有彻底理解 左旋 和 右旋，可能会将它们混淆。下面谈谈我对如何区分 左旋 和 右旋 的理解。 ` ` ##### **区分 左旋 和 右旋** 仔细观察上面"左旋"和"右旋"的示意图。我们能清晰的发现，它们是对称的。无论是左旋还是右旋，被旋转的树，在旋转前是二叉查找树，并且旋转之后仍然是一颗二叉查找树。  **左旋示例图**(以x为节点进行左旋)： ``` z x / / \ --(左旋)--> x y z / y ``` 对x进行左旋，意味着，将“x的右孩子”设为“x的父亲节点”；即，将 x变成了一个左节点(x成了为z的左孩子)！。 因此，**左旋中的“左”，意味着“被旋转的节点将变成一个左节点”**。 ` ` **右旋示例图**(以x为节点进行右旋)： ``` y x \ / \ --(右旋)--> x y z \ z ``` 对x进行右旋，意味着，将“x的左孩子”设为“x的父亲节点”；即，将 x变成了一个右节点(x成了为y的右孩子)！ 因此，**右旋中的“右”，意味着“被旋转的节点将变成一个右节点”**。 ` ` #### 红黑树基本操作-添加 将一个节点插入到红黑树中，需要执行哪些步骤呢？ **第一步: 将红黑树当作一颗二叉查找树，将节点插入。** ``` 红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。 也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。 这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉查找树的事实。 ``` **第二步：将插入的节点着色为"红色"。**        将插入的节点着色为红色，不会违背"特性(5)"！少违背一条特性，就意味着我们需要处理的情况越少。接下来，就要努力的让这棵树满足其它性质即可；满足了的话，它就又是一颗红黑树了。 **第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。** ``` 第二步中，将插入节点着色为"红色"之后，不会违背"特性(5)"。那它到底会违背哪些特性呢？    对于"特性(1)"，显然不会违背了。因为我们已经将它涂成红色了。    对于"特性(2)"，显然也不会违背。在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。   对于"特性(3)"，显然不会违背了。这里的叶子节点是指的空叶子节点，插入非空节点并不会对它们造成影响。   对于"特性(4)"，是有可能违背的！    那接下来，想办法使之"满足特性(4)"，就可以将树重新构造成红黑树了。 ``` 添加操作的伪代码《算法导论》: ``` RB-INSERT(T, z) y ← nil[T] // 新建节点“y”，将y设为空节点。 x ← root[T] // 设“红黑树T”的根节点为“x” while x ≠ nil[T] // 找出要插入的节点“z”在二叉树T中的位置“y” do y ← x if key[z] < key[x] then x ← left[x] else x ← right[x] p[z] ← y // 设置 “z的父亲” 为 “y” if y = nil[T] then root[T] ← z // 情况1：若y是空节点，则将z设为根 else if key[z] < key[y] then left[y] ← z // 情况2：若“z所包含的值” < “y所包含的值”，则将z设为“y的左孩子” else right[y] ← z // 情况3：(“z所包含的值” >= “y所包含的值”)将z设为“y的右孩子” left[z] ← nil[T] // z的左孩子设为空 right[z] ← nil[T] // z的右孩子设为空。至此，已经完成将“节点z插入到二叉树”中了。 color[z] ← RED // 将z着色为“红色” RB-INSERT-FIXUP(T, z) // 通过RB-INSERT-FIXUP对红黑树的节点进行颜色修改以及旋转，让树T仍然是一颗红黑树 ``` 结合伪代码以及为代码上面的说明，先理解RB-INSERT。理解了RB-INSERT之后，我们接着对 RB-INSERT-FIXUP的伪代码进行说明。 添加修正操作的伪代码《算法导论》 ``` RB-INSERT-FIXUP(T, z) while color[p[z]] = RED // 若“当前节点(z)的父节点是红色”，则进行以下处理。 do if p[z] = left[p[p[z]]] // 若“z的父节点”是“z的祖父节点的左孩子”，则进行以下处理。 then y ← right[p[p[z]]] // 将y设置为“z的叔叔节点(z的祖父节点的右孩子)” if color[y] = RED // Case 1条件：叔叔是红色 then color[p[z]] ← BLACK ▹ Case 1 // (01) 将“父节点”设为黑色。 color[y] ← BLACK ▹ Case 1 // (02) 将“叔叔节点”设为黑色。 color[p[p[z]]] ← RED ▹ Case 1 // (03) 将“祖父节点”设为“红色”。 z ← p[p[z]] ▹ Case 1 // (04) 将“祖父节点”设为“当前节点”(红色节点) else if z = right[p[z]] // Case 2条件：叔叔是黑色，且当前节点是右孩子 then z ← p[z] ▹ Case 2 // (01) 将“父节点”作为“新的当前节点”。 LEFT-ROTATE(T, z) ▹ Case 2 // (02) 以“新的当前节点”为支点进行左旋。 color[p[z]] ← BLACK ▹ Case 3 // Case 3条件：叔叔是黑色，且当前节点是左孩子。(01) 将“父节点”设为“黑色”。 color[p[p[z]]] ← RED ▹ Case 3 // (02) 将“祖父节点”设为“红色”。 RIGHT-ROTATE(T, p[p[z]]) ▹ Case 3 // (03) 以“祖父节点”为支点进行右旋。 else (same as then clause with "right" and "left" exchanged) // 若“z的父节点”是“z的祖父节点的右孩子”，将上面的操作中“right”和“left”交换位置，然后依次执行。 color[root[T]] ← BLACK ``` ` ` 根据被插入节点的父节点的情况，可以将"当节点z被着色为红色节点，并插入二叉树"划分为**三种情况来处理**。 ① 情况说明：**被插入的节点是根节点**。     处理方法：直接把此节点涂为黑色。 ② 情况说明：**被插入的节点的父节点是黑色**。     处理方法：什么也不需要做。节点被插入后，仍然是红黑树。 ③ 情况说明：**被插入的节点的父节点是红色**。     处理方法：那么，该情况与红黑树的“特性(5)”相冲突。这种情况下，被插入节点是一定存在非空祖父节点的；进一步的讲，被插入节点也一定存在叔叔节点(即使叔叔节点为空，我们也视之为存在，空节点本身就是黑色节点)。理解这点之后，我们依据"叔叔节点的情况"，将这种情况进一步划分为3种情况(Case)。  3.1 **被插入的节点的父节点是红色+叔叔节点也是红色** * **处理策略** (01) 将“父节点”设为黑色。 (02) 将“叔叔节点”设为黑色。 (03) 将“祖父节点”设为“红色”。 (04) 将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作。  3.2 **被插入的节点的父节点是红色,叔叔节点是黑色，且当前节点是其父节点的右孩子** * **处理策略** (01) 将“父节点”作为“新的当前节点”。 (02) 以“新的当前节点”为支点进行左旋。 ` ` 变化前\[当前节点为7节点\]：  变化后：  3.3 **被插入的节点的父节点是红色,叔叔节点是黑色，且当前节点是其父节点的左孩子** * **处理策略** (01) 将“父节点”设为“黑色”。 (02) 将“祖父节点”设为“红色”。 (03) 以“祖父节点”为支点进行右旋。 ` ` 变化前\[当前节点为2节点\]：  变化后：  ` ` #### **红黑树基本操作-删除** 将红黑树内的某一个节点删除。需要执行的操作依次是：首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；然后，通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。详细描述如下： **第一步：将红黑树当作一颗二叉查找树，将节点删除。**        这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况：        ① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。        ② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。        ③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给"被删除节点"之后，再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了，下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然"的后继节点"不可能双子都非空，就意味着"该节点的后继节点"要么没有儿子，要么只有一个儿子。若没有儿子，则按"情况① "进行处理；若只有一个儿子，则按"情况② "进行处理。 **第二步：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。**        因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，使之重新成为一棵红黑树。 ` ` 删除操作的伪代码《算法导论》: ``` RB-DELETE(T, z) if left[z] = nil[T] or right[z] = nil[T] then y ← z // 若“z的左孩子” 或 “z的右孩子”为空，则将“z”赋值给 “y”； else y ← TREE-SUCCESSOR(z) // 否则，将“z的后继节点”赋值给 “y”。 if left[y] ≠ nil[T] then x ← left[y] // 若“y的左孩子” 不为空，则将“y的左孩子” 赋值给 “x”； else x ← right[y] // 否则，“y的右孩子” 赋值给 “x”。 p[x] ← p[y] // 将“y的父节点” 设置为 “x的父节点” if p[y] = nil[T] then root[T] ← x // 情况1：若“y的父节点” 为空，则设置“x” 为 “根节点”。 else if y = left[p[y]] then left[p[y]] ← x // 情况2：若“y是它父节点的左孩子”，则设置“x” 为 “y的父节点的左孩子” else right[p[y]] ← x // 情况3：若“y是它父节点的右孩子”，则设置“x” 为 “y的父节点的右孩子” if y ≠ z then key[z] ← key[y] // 若“y的值” 赋值给 “z”。注意：这里只拷贝z的值给y，而没有拷贝z的颜色！！！ copy y's satellite data into z if color[y] = BLACK then RB-DELETE-FIXUP(T, x) // 若“y为黑节点”，则调用 return y ``` 结合伪代码以及为代码上面的说明，先理解RB-DELETE。理解了RB-DELETE之后，接着对 RB-DELETE-FIXUP的伪代码进行说明: ``` RB-DELETE-FIXUP(T, x) while x ≠ root[T] and color[x] = BLACK do if x = left[p[x]] then w ← right[p[x]] // 若 “x”是“它父节点的左孩子”，则设置 “w”为“x的叔叔”(即x为它父节点的右孩子) if color[w] = RED // Case 1: x是“黑+黑”节点，x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。 then color[w] ← BLACK ▹ Case 1 // (01) 将x的兄弟节点设为“黑色”。 color[p[x]] ← RED ▹ Case 1 // (02) 将x的父节点设为“红色”。 LEFT-ROTATE(T, p[x]) ▹ Case 1 // (03) 对x的父节点进行左旋。 w ← right[p[x]] ▹ Case 1 // (04) 左旋后，重新设置x的兄弟节点。 if color[left[w]] = BLACK and color[right[w]] = BLACK // Case 2: x是“黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。 then color[w] ← RED ▹ Case 2 // (01) 将x的兄弟节点设为“红色”。 x ← p[x] ▹ Case 2 // (02) 设置“x的父节点”为“新的x节点”。 else if color[right[w]] = BLACK // Case 3: x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。 then color[left[w]] ← BLACK ▹ Case 3 // (01) 将x兄弟节点的左孩子设为“黑色”。 color[w] ← RED ▹ Case 3 // (02) 将x兄弟节点设为“红色”。 RIGHT-ROTATE(T, w) ▹ Case 3 // (03) 对x的兄弟节点进行右旋。 w ← right[p[x]] ▹ Case 3 // (04) 右旋后，重新设置x的兄弟节点。 color[w] ← color[p[x]] ▹ Case 4 // Case 4: x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的。(01) 将x父节点颜色 赋值给 x的兄弟节点。 color[p[x]] ← BLACK ▹ Case 4 // (02) 将x父节点设为“黑色”。 color[right[w]] ← BLACK ▹ Case 4 // (03) 将x兄弟节点的右子节设为“黑色”。 LEFT-ROTATE(T, p[x]) ▹ Case 4 // (04) 对x的父节点进行左旋。 x ← root[T] ▹ Case 4 // (05) 设置“x”为“根节点”。 else (same as then clause with "right" and "left" exchanged) // 若 “x”是“它父节点的右孩子”，将上面的操作中“right”和“left”交换位置，然后依次执行。 color[x] ← BLACK ``` ` ` ### **红黑树相对于哈希表，在选择使用的时候有什么依据？** ***** 权衡三个因素: 查找速度, **数据量, 内存使用，可扩展性**。 　　总体来说，hash查找速度会比map快，而且查找速度基本和数据量大小无关，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n) 小，hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash。但若你对内存使用特别严格， 希望程序尽可能少消耗内存，那么一定要小心，hash可能会让你陷入尴尬，特别是当你的hash对象特别多时，你就更无法控制了，而且 hash的构造速度较慢。 红黑树并不适应所有应用树的领域。如果数据基本上是静态的，那么让他们待在他们能够插入，并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的，例如，做一个哈希表，性能可能会更好一些。 在实际的系统中，例如，需要使用动态规则的防火墙系统，使用红黑树而不是散列表被实践证明具有更好的伸缩性。Linux内核在管理vm\_area\_struct时就是采用了红黑树来维护内存块的。 红黑树通 过扩展节点域可以在不改变时间复杂度的情况下得到结点的秩。 ### **红黑树时间复杂度** ***** 红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了**红黑树的查找、插入、删除的时间复杂度最坏为O(log n)**。