红黑树---简单易懂

红黑树，对于很多人来讲都是既熟悉又陌生，每次提到红黑树都会令人头大。我们知道jdk1.8中，hashMap的底层使用了红黑树，那么到底什么是红黑树呢？红黑树的算法又是什么样的呢？

我们平时都会遇到遇到别人买了东西，然后让你猜价格的问题
甲：你猜我买的这个多少钱？
乙：1000
甲： 高了
乙：500
甲：低了:
乙：750
...... 直到最后猜中

这样说呢，可能大家也猜到了是【二分查找法】，通过这个例子呢，主要想引出的是树，看下面的图片：

树.jpg

程序中的树呢，其实是我们日常看到的树的倒影，或者发挥一下想象，倒影也可以是树根

二叉查找树

二叉查找树，Binary Search Tree 「BST」，要想了解二叉查找树呢，首先我们需要了解一下二叉查找树都有哪些特性呢？

1. 某节点的左子树节点值仅包含小于该节点值
2. 某节点的右子树节点值仅包含大于该节点值
3. 左右子树每个也必须是二叉查找树

看个图就轻松理解上面三句话的意思了:

图1.jpg

上图，结合二叉查找树的三条约束来看，非常好，没有什么问题。再来看一个图，依旧符合上面三条约束，感觉有问题吗？

图2.jpg

这是一个走路一米六，一米八的树
这是一个畸形的树，大风一挂很可能被折断的树
从程序的角度来说这个树不够平衡，查找次数或时间复杂度 O(h)可能会随着一条腿长无限增长

理科生在高中学习生物时学过一个关键字「去除顶端优势」，通过去除植物顶端优势，侧芽会迅速生长，慢慢变得强壮和平衡， 红黑树其实就是去除二叉查找树顶端优势的解决方案，从而达到树的平衡

红黑树

红黑树，Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)，树上的每个节点都遵循下面的规则:

1. 每个节点都有红色或黑色
2. 树的根始终是黑色的(根节点始终是黑色的)
3. 没有两个相邻的红色节点(红色节点不能有红色父节点或者红色子节点，并没有说不能出现连续的黑色节点)
4. 从节点(包括根节点)到其任何后代NULL节点的每条路径都具有相同数量的黑色节点
   (叶子节点下方挂的两个空节点，并且认为他们是黑色的)

可能大家还是很懵逼，不过没事，多练习几次就熟悉了。
红黑树有两大操作：

1. recolor (重新标记黑色或红色)
2. rotation (旋转，这是树达到平衡的关键)

我们会先尝试recolor，如果recolor不能达到红黑树的四个要求，然后我们尝试rotation，其实红黑树的关键玩法就是弄清楚recolor和rotation的规则，接下来我们看一下详细的算法公式吧。

假设我们插入的新节点为X

1. 将新插入的节点标记为红色
2. 如果X为根节点，则标记为黑色
3. 如果X的parent不是黑色，并且X也不是root
   3.1 如果X的uncle是红色
   3.1.1 将parent和uncle标记为黑色
   3.1.2 将grand parent(祖父)标记为红色
   3.1.3 将X节点的颜色标记为与X祖父相同

接下来看下图：

图3.jpg

跟着上面的公式走：

1. 将新节点X标记为红色
2. 发现X的parent(P)同样为红色，这样违反了红黑树第三条规则[不能有两个连续相邻的红色节点]
3. 发现X的uncle(U)也是红色的
4. 将X的parent(P)和uncle(U)标记为黑色
5. 将X和X的grand parent(G)标记为相同的颜色，即红色，继续重复公式2,3
6. 发现X的grand parent(G)是根节点，标记为黑色
7. 结束

上面说的是X的uncle为红色的情况，接下来我们看一下X的uncle为黑色的情况

3. 如果X的parent不是黑色，并且X也不是root
   3.2 如果X的uncle是黑色，我们要分四种情况处理
   3.2.1 左左情况(P是G的左孩子，X是P的左孩子)
   3.2.2 左右情况(P是G的左孩子，X是P的右孩子)
   3.2.3 右右情况(和 3.2.1 镜像过来，恰好相反，P是G的右孩子，X是P的右孩子)
   3.2.4 右左情况(和 3.2.2 镜像过来，恰好相反，P是G的右孩子，X是P的左孩子)

当uncle节点为黑色的时候，我们第一步考虑的是旋转，这里呢我们可以先不关注红黑树的4个规则，主要是演示如何旋转的。

左左情况

这种情况很简单，想象这是一根绳子，手提起P节点，然后变色即可，如下图：

左左.jpg

变色：X是当前节点，P是X的parent节点，U是X的uncle节点，G是grand parent节点。P节点是根节点变黑色，G变成和X一样的颜色，也就是红色。完成

左右情况

先进行左旋：使X的父节点P被X取代，同时父节点P成为X的左孩子，然后在应用左左情况，如下图：

左右.jpg

右右情况

像左左一样，看成一根绳子。手提起P节点，然后变色即可，如下图：

右右.jpg

右左情况

先右旋：使 X 的父节点 P 被 X 取代，同时父节点 P 成为 X 的右孩子，然后再应用右右情况，如下图：

右左.jpg

通过上述过程，想必大家对红黑树有了一定的了解。以后在提到红黑树的时候，就不会那么头大了。本文参照日拱一兵公众号中的文章"红黑树，超强动静图详解，简单易懂".
参考文章