如何从100亿数据快速找到目标？--红黑树

读者看到这个标题都会觉得不可思议吧，不过这确实是算法的妙处，编程的魅力。像TreeMap、TreeSet、JDK8 HashMap等都使用这种算法，这种算法就是红黑树。红黑树能在O（lgn）的时间内完成查找、插入和删除操作。

红黑树是变种的AVL树(有关AVL树的原理请查看小编的文章《平衡二叉树AVL》)，是一种弱平衡二叉树。什么是强平衡？AVL树保证每个子树的高度差的绝对值都不超过1，这种是强平衡，AVL每次插入数据和删除数据时，为了保持这种特性，得进行不可预算的旋转，极大可能地损耗性能。而红黑树在任何不平衡状态下都会在3次旋转之内解决。

好了，废话不多说，下面小编将通过图文以及代码讲解红黑树的知识点。

注：本文中实现的代码参考了treeMap的源码

红黑树概念

红黑树是每个节点都带有颜色属性并能自平衡的二叉查找树，颜色是红色或黑色。它必须满足如下性质

1. 每个节点要么是黑色，要么是红色
2. 根节点是黑色
3. 每个叶子节点(NIL)是黑色(又被称为黑哨兵)
4. 每个红色节点的两个子节点都是黑色
5. 任意一节点到每个叶子节点的路径都包含数量相同的黑节点

有了这几个性质做为限制，避免了二叉查找树退化成单链表的情况。而且从这几条性质也可以看出：当某条路径最短时，这条路径必然都是由黑色节点构成。当某条路径最长时，这条路径必然是由红色和黑色节点相间构成（由于性质4的限定）。而性质5又规定任意一节点到每个叶子节点的路径都包含数量相同的黑节点，所以在路径最长的情况下，路径上红色节点数量=黑色节点数量，也就是说路径长度为两倍黑色节点数量，换句话就是最长路径是最短路径长度的2倍。

注：红黑色树是一种比较难的数据结构，要完全搞懂非常耗时耗力。而且涉及到的知识点有BT、BST和AVL。如果对这些数据结构不是很熟悉的同学，可以关注下小编的头条号，小编其他文章中有对这些数据结构进行讲解。

自平衡

红黑树能自平衡，靠的是：左旋、右旋和变色

• 左旋：逆时针旋转红黑树的两个节点，使父节点被自己的右孩子取代，而自己成为自己的左孩子

private void rotateLeft(RBTreeNode p) {
 if (p != null) {
 RBTreeNode r = p.right;
 p.right = r.left;
 if (r.left != null)
 r.left.parent = p;
 r.parent = p.parent;
 if (p.parent == null)
 root = r;
 else if (p.parent.left == p)
 p.parent.left = r;
 else
 p.parent.right = r;
 r.left = p;
 p.parent = r;
 }
}
 

• 右旋：顺时针旋转红黑树的两个节点，使父节点被自己的左孩子取代，而自己成为自己的右孩子

private void rotateRight(RBTreeNode p) {
 if (p != null) {
 RBTreeNode l = p.left; 

 p.left = l.right;
 if (l.right != null) l.right.parent = p;
 l.parent = p.parent;
 if (p.parent == null)
 root = l;
 else if (p.parent.right == p)
 p.parent.right = l;
 else p.parent.left = l;
 l.right = p;
 p.parent = l;
 }
}

• 变色：节点颜色由红色变黑色或黑色变红色

插入

---

红黑树的插入过程和二叉查找树(BST)插入过程类似，不过红黑树插入新节点后，需进行自平衡调整，以满足红黑树的的性质。当插入新节点时，我们设置这个新节点为红色，因为插入红色节点后满足性质5，保持红黑树所有路径上的黑色节点数量不变，仅可能破坏性质4，出现两个连续的红色节点的情况。少破会一条性质，插入自平衡操作比较简单。

接下来，将分析插入红色节点后红黑树的情况。这里做下规定：插入的新节点为N，N的父节点为P，祖父节点为G，叔叔节点为U。

情况1

---

插入的新节点N是红黑树的根节点，比如插入节点12，这种情况下，我们把节点12的颜色由红色变为黑色，性质2被满足。也没有破坏其他的性质。

情况2

---

N的父节点是黑色，比如在情况1下插入节点1，性质4和性质5都没有受到影响，不需要调整。

以下情况N的父节点P都是红色，主要区分叔叔节点U的情况，节点U有可能是黑色，有可能是红色。

情况3

---

N的父节点P是红色，叔叔节点U也是红色。由于P和N均为红色，性质4被打破，此时需要调整。如下图所示，假设节点7是新插入的节点。先将节点0和节点2染成黑色，再把节点9染成红色。此时经过9-1-0和9-1-2-7路径上的黑色节点数量相等，性质5仍然满足。但需要注意的是G（节点9）被染成红色后，可能会和它的父节点形成连续的红色节点，此时需要递归向上调整。图中节点9是根节点，所以只需要把9染成黑色，就能完成平衡。

情况4

---

N的父节点P为红色，叔叔节点U为黑色。N是P的左孩子。如下图所示，假设节点4是新插入的节点，节点7是父节点，叔叔节点Nil默认为黑色。先将节点4右旋，然后再变色，把节点4染黑，祖父节点2染红。此时2-4-7满足红黑树的性质。但需要注意的是节点2被染成红色后，与父节点1形成连续红色节点，所以需要递归向上调整。

情况5

---

N的父节点P为红色，叔叔节点U为黑色。N是P的右孩子。也就是情况4最右图的变种。把N当做节点2-4-7这个路径，叔叔节点0为黑色，节点N是节点1的右孩子。现在对这种情况进行分析：我们只要把N中的节点4左旋，这个时候就可以满足红黑树的性质，达到平衡。

情况3，情况4和情况5是针对N节点的父节点是祖父节点G的右孩子这种情况来分析的，也就是说存在N节点的父节点是祖父节点G的左孩子这种情况，由于这种情况与上面分析的类似，这里不再赘述。有兴趣的同学可以开动脑筋思考下，动动手，这样红黑树知识掌握得就透彻啦。

下面我将通过图来演示数据12、1、9、2、0、11、7、19、4、15、18插入到红黑树中的情况，大家拿好板凳，认真跟着小编一步一步来哈。

插入12，建立根节点

---

插入节点1

---

插入节点9

---

插入节点2

---

插入节点0

---

插入节点11

---

插入节点7

---

插入节点19

---

插入节点4

---

插入节点15

---

插入节点18

---

数据12、1、9、2、0、11、7、19、4、15、18插入到红黑树中演示完毕了，最终的红黑树数据结构如下

好啦看到这里是不是感觉有点疲劳了，那就休息下，伸伸懒腰，回忆回忆之前的内容，如果有受益，不妨给小编点点赞。

休息差不多了，现在我们开始讲讲红黑树的删除操作啦

删除

---

删除操作首先要确定待删除节点有几个孩子，如果有两个孩子，要先找到该节点的前驱(该节点左子树中最大的节点)或者后继(该节点右子树中最小的节点)，将前驱或者后继的值替换到待删除节点的值。由于前驱和后继至多只有一个孩子节点，这样我们就把问题转化为只有一个孩子节点的情况了。问题被简化了一些。

注：本文中使用后继做为待删除节点替换的值。想要了解前驱和后继的话，请参考二叉查找树BST文章中第4点和第5点的内容。

红黑树待删除的节点，如果为红色，性质5(任意一节点到每个叶子节点的路径都包含数量相同的黑节点)不会被破坏，这时候直接用其孩子节点替换空位即可；如果为黑色，那么就破坏了性质5，需要自平衡处理。如果待删除节点的孩子节点为红色，直接用孩子节点替换待删除的节点，并将孩子节点染成黑色。这样就达到了平衡。如果待删除节点的孩子节点为黑色，处理就比较复杂。

下面我们将对待删除节点的孩子节点为黑色进行分析，先做下规定：待删除节点为X，X的孩子节点为N(至多只有一个孩子节点)，X的父节点为P，X的兄弟节点为B，B的左孩子为BL，右孩子为BR。

情况1

---

兄弟节点B是黑色，节点B的两个子孩子BL、BR也是黑色。比如下图中：待删除节点13是黑色，节点13的父节点16是黑色，兄弟节点17是黑色，兄弟节点的两个子孩子为Nil，也都是黑色。处理操作是设置兄弟节点17为红色，并向上递进判断父节点16的平衡情况，直到待操作的节点是红色为止。最后断掉节点13，达到平衡。图中还需要递进一次，才能达到平衡。这里不列出来了，同学们自己动动手哈。

情况2

---

兄弟节点B是红色，节点B的两个子孩子BL、BR都是黑色。比如下图中：待删除节点16是黑色，由于待删除节点16有两个非空子孩子，后继寻找替换的节点17，把节点17的值替换到节点16上，此后待删除的节点转化成节点17。由节点17可知，兄弟节点6是红色，节点6的两个孩子是黑色，改变兄弟节点6为黑色，父节点17位红色，并右旋。这时候待删除的节点17，转换成情况1。

情况3

---

兄弟节点B是黑色，节点B的两个子孩子BL、BL都是红色。比如下图：待删除节点19是黑色，父节点18是红色，兄弟节点16是黑色，兄弟节点的两个孩子节点15和节点17是红色，这个时候先进行变色，父节点18变黑，兄弟节点16变红，兄弟节点的左孩子15变黑，再进行右旋，并切断节点19就达到了平衡。

情况4

---

兄弟节点B是黑色，节点B的左孩子BL是红色，右孩子BR是黑色。比如下图：待删除节点15是黑色，父节点16是红色，兄弟节点18是黑色，节点17是红色。先对节点17染黑，对节点18染红，再对节点18右旋。这些步骤后，树变成兄弟节点左孩子BL是黑色，右孩子BR是红色这种情况，接着对节点17染红，节点18染黑，父节点16染黑，再对父节点16左旋并断链节点15，从而达到了平衡。

情况1和情况4针对的是待删除节点是父节点左孩子的情况，情况2和情况3针对的是待删除节点是父节点右孩子的情况，也就是说还存在：情况1和情况4待删除节点是父节点右孩子的情况；情况2和情况3待删除节点是父节点左孩子的情况。由于这些情况与上面介绍的情况类似，这里就不在赘述了。有兴趣的同学，自己动动手，巩固下学到的知识点。

下面我将通过图来演示将数据12、1、9、2、0、11、7、19、4、15依次从红黑树中删除的情况，大家拿好板凳，认真跟着小JIA一步一步来哈。

红黑树初始数据结构

---

删除节点12

---

删除节点1

---

删除节点9

---

删除节点2

---

删除节点0

---

删除节点11

---

删除节点7

---

删除节点19

---

删除节点4

---

删除节点15

---

最后只剩下节点18，也就是只剩下根节点。数据12、1、9、2、0、11、7、19、4、15依次从红黑树中删除的情况演示完毕！

遍历

---

红黑树的遍历同二叉树的遍历，小编在《二叉树》文章中已经介绍过啦，这里不在赘述。

查找

---

红黑树的遍历同AVL的遍历，小编在《平衡二叉树AVL》文章中已经介绍过啦，这里不在赘述。

花了几天时间，终于把红黑树整理完毕啦，由于红黑树涉及太多，一下子可能看不过来，小编建议：各位同学关注下小编的头条号，有时间再慢慢看哈。

这篇文章实现的完整代码，如果有需要的同学可以私聊找小编获取。