红黑树
红黑树
原文链接：https://my.oschina.net/hosee/blog/618828
一、红黑树的介绍
先来看下算法导论对R-B Tree的介绍： 红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
红黑树，作为一棵二叉查找树，满足二叉查找树的一般性质。下面，来了解下二叉查找树的一般性质。
二叉查找树
二叉查找树，也称有序二叉树（ordered binary tree），或已排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
- 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 任意节点的左、右子树也分别为二叉查找树。
- 没有键值相等的节点（no duplicate nodes）。
因为一棵由n个结点随机构造的二叉查找树的高度为lgn，所以顺理成章，二叉查找树的一般操作的执行时间为O(lgn)。但二叉查找树若退化成了一棵具有n个结点的线性链后，则这些操作最坏情况运行时间为O(n)。
红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。
但它是如何保证一棵n个结点的红黑树的高度始终保持在logn的呢？这就引出了红黑树的5个性质：
- 每个结点要么是红的要么是黑的。
- 根结点是黑的。
- 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
- 如果一个结点是红的，那么它的两个儿子都是黑的。
- 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。
正是红黑树的这5条性质，使一棵n个结点的红黑树始终保持了logn的高度（红黑树的高度至多为2log(n+1)证明略），从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论成立的原因。
此图忽略了叶子和根部的父结点。同时，上文中我们所说的 "叶结点" 或"NULL结点"，如上图所示，它不包含数据而只充当树在此结束的指示，这些节点在绘图中经常被省略，望看到此文后的读者朋友注意。
二、树的旋转知识
当在对红黑树进行插入和删除等操作时，对树做了修改可能会破坏红黑树的性质。为了继续保持红黑树的性质，可以通过对结点进行重新着色，以及对树进行相关的旋转操作，即通过修改树中某些结点的颜色及指针结构，来达到对红黑树进行插入或删除结点等操作后继续保持它的性质或平衡的目的。
树的旋转分为左旋和右旋，下面借助图来介绍一下左旋和右旋这两种操作。
1.左旋
如上图所示，当在某个结点pivot上，做左旋操作时，我们假设它的右孩子y不是NIL[T]，pivot可以为任何不是NIL[T]的左子结点。左旋以pivot到Y之间的链为“支轴”进行，它使Y成为该子树的新根，而Y的左孩子b则成为pivot的右孩子。
2.右旋
右旋与左旋差不多，再此不做详细介绍。
对于树的旋转，能保持不变的只有原树的搜索性质，而原树的红黑性质则不能保持，在红黑树的数据插入和删除后可利用旋转和颜色重涂来恢复树的红黑性质。
三、红黑树的插入
将一个节点插入到红黑树中，需要执行哪些步骤呢？首先，将红黑树当作一颗二叉查找树，将节点插入；然后，将节点着色为红色；最后，通过旋转和重新着色等方法来修正该树，使之重新成为一颗红黑树。详细描述如下：
第一步: 将红黑树当作一颗二叉查找树，将节点插入。 红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉查找树的事实。 好吧？那接下来，我们就来想方设法的旋转以及重新着色，使这颗树重新成为红黑树！
第二步：将插入的节点着色为"红色"。
由于性质的约束：插入点不能为黑节点，应插入红节点。因为你插入黑节点将破坏性质5，所以每次插入的点都是红结点，但是若他的父节点也为红，那岂不是破坏了性质4？对啊，所以要做一些“旋转”和一些节点的变色。
第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。
第二步中，将插入节点着色为"红色"之后，不会违背"特性(5)"。那它到底会违背哪些特性呢？
对于"特性(1)"，显然不会违背了。因为我们已经将它涂成红色了。
对于"特性(2)"，显然也不会违背。在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。
对于"特性(3)"，显然不会违背了。这里的叶子节点是指的空叶子节点，插入非空节点并不会对它们造成影响。
对于"特性(4)"，是有可能违背的！
那接下来，想办法使之"满足特性(4)"，就可以将树重新构造成红黑树了。
首先来看下伪代码描述：
根据被插入节点的父节点的情况，可以将"当节点z被着色为红色节点，并插入二叉树"划分为三种情况来处理。
① 情况说明：被插入的节点是根节点。 处理方法：直接把此节点涂为黑色。 ② 情况说明：被插入的节点的父节点是黑色。 处理方法：什么也不需要做。节点被插入后，仍然是红黑树。 ③ 情况说明：被插入的节点的父节点是红色。 处理方法：那么，该情况与红黑树的“特性(5)”相冲突。这种情况下，被插入节点是一定存在非空祖父节点的；进一步的讲，被插入节点也一定存在叔叔节点(即使叔叔节点为空，我们也视之为存在，空节点本身就是黑色节点)。理解这点之后，我们依据"叔叔节点的情况"，将这种情况进一步划分为3种情况(Case)。
上面三种情况(Case)处理问题的核心思路都是：将红色的节点移到根节点；然后，将根节点设为黑色。下面对它们详细进行介绍。
1. (Case 1)叔叔是红色
插入的节点标为N（红色），父节点为P，祖父节点为G，叔节点为U，下同
N、P都为红，违反性质4；若把P改为黑，符合性质4，显然左边少了一个黑节点，违反性质5；所以我们把G，U都改为相反色，这样一来通过G的路径的黑节点数目没变，即符合4、5，但是G变红了，若G的父节点又是红的不就有违反了4，是这样，所以经过上边操作后未结束，需把G作为起始点，即把G看做一个插入的红节点继续向上检索----属于哪种情况，按那种情况操作~要么中间就结束，要么知道根结点（此时根结点变红，一根结点向上检索，那木有了，那就把他变为黑色吧）。
注意核心思路就是将红色的节点移到根节点。
2. (Case 2)叔叔是黑色，且当前节点是右孩子
case1中我们不考虑当前节点是左孩子还是右孩子，因为情况都相同。但是当叔叔节点为黑色时，则要考虑节点是左孩子还是右孩子。
case2很简单，通过旋转生成右边的图，而右边的情况就是case3。
总之case2就是通过一次旋转，然后进行case3的判断
3. (Case 3)叔叔是黑色，且当前节点是左孩子
操作：先旋转再变色
经过P、G变换（旋转），变换后P的位置就是当年G的位置，所以红P变为黑，而黑G变为红都是为了不违反性质5，而维持到达叶节点所包含的黑节点的数目不变！还可以理解为：也就是相当于（只是相当于，并不是实事，只是为了更好理解；）把红N头上的红节点移到对面黑U的头上；这样即符合了性质4也不违反性质5，这样就结束了。
删除操作和插入操作差不多本文就不提了，请大家参看Reference。
总结：
红黑树的插入操作，当父节点为黑时，很好理解。主要是当父节点是红色时，需要区分成3种case。
case1时，发生一次着色操作，然后不断循环，每次完成case1操作后，把G赋给N，直到循环到根节点或者父节点为黑，跳出case1的情况。由于红黑树的高度至多为2log(n+1)。所以case1至多发生log(n+1)次。
case2时，发生一次旋转操作，跳到case3情形。
case3时，发生一次旋转操作，再一次着色操作。完成操作。
所以红黑树的选择操作很少。局部至多2次（插入最多两次旋转，删除最多三次旋转）。大部分都是着色操作。
少量的旋转操作使得再添加节点时，大部分节点是可以被查询/修改的（因为旋转时为了数据安全，会锁住某些节点不能被修改，而着色操作并不影响这些）。在很多底层的实现上，有大量红黑树的实现。
四、红黑树与AVL树的区别
红黑树旋转操作非常局部化，而且次数极少（插入最多两次旋转，删除最多三次旋转），而改变颜色的操作不会影响到用户对树的query操作（即不要lock），另外很多树，如AVL树，2-3树,2-4树都可以转化成红黑树，红黑树能达到O(logn)高度，但是不像AVL树那样严格要求左右子树高度差必需相差不超过1。可以说RB树是目前为止高度要求最灵活的准平衡BST。准平衡是相对完全二叉树来说的，AVL树(比如Fibonacci树)也不是完美平衡的。
红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。
当然，红黑树并不适应所有应用树的领域。如果数据基本上是静态的，那么让他们待在他们能够插入，并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的，做一个哈希表，性能可能会更好一些。
红黑树是一个更高效的检索二叉树，因此常常用来实现关联数组（“关联数组”是一种具有特殊索引方式的数组。不仅可以通过整数来索引它，还可以使用字符串或者其他类型的值（除了NULL）来索引它。）。
五、Java中的红黑树
TreeMap 和 TreeSet 是 Java Collection Framework 的两个重要成员，其中 TreeMap 是 Map 接口的常用实现类，而 TreeSet 是 Set 接口的常用实现类。虽然 HashMap 和 HashSet 实现的接口规范不同，但 TreeSet 底层是通过 TreeMap 来实现的，因此二者的实现方式完全一样。而 TreeMap 的实现就是红黑树算法。
对于 TreeMap 而言，由于它底层采用一棵“红黑树”来保存集合中的 Entry，这意味这 TreeMap 添加元素、取出元素的性能都比 HashMap 低：当 TreeMap 添加元素时，需要通过循环找到新增 Entry 的插入位置，因此比较耗性能；当从 TreeMap 中取出元素时，需要通过循环才能找到合适的 Entry，也比较耗性能。
但 TreeMap、TreeSet 比 HashMap、HashSet 的优势在于：TreeMap 中的所有 Entry 总是按 key 根据指定排序规则保持有序状态，TreeSet 中所有元素总是根据指定排序规则保持有序状态。