前言

在认识红黑树之前，最好你已经认识并掌握了二叉树与平衡二叉树（AVL）。AVL树是高度平衡的二叉树，它的时间复杂度大约是O(log₂n)，即使在最坏的情况下也是。其实AVL树最复杂的地方在于删除节点重新平衡时的处理，有可能需要多次旋转节点。而红黑树相对于AVL树降低了平衡要求，它使用红黑两种颜色来标记节点，并对颜色进行要求（限制），在插入删除操作后对不符合的情况进行调整以满足要求，从而实现自我平衡。这些所谓的要求即是红黑树的特性：

• 每个节点要么是红色要么是黑色。

• 根节点是黑色。

• 叶节点（值为Nil或Null的节点）是黑色。

• 如果一个节点是红色，那么它的子节点是黑色，相当于父子节点之间不能出现连续的红色节点。

• 从任意节点出发到任意叶节点的所有路径上均包含相同数目的黑色节点。

通过上面的要求保证了任意节点到叶节点的所有路径中，没有一条路径会大于其他路径的两倍长（最大是两倍）。可以想象某条路径上有3个连续的黑色节点，而另外一条路径上它能达到的最长也就是红黑相间，所以最长是6个节点，3个黑色3个红色。由于红黑树降低了平衡的要求，也就是说它在插入删除时可能不需要任何的操作，也可能只需要改变下颜色即可，最糟糕的情况下才是旋转，相比AVL树只能通过旋转去达到平衡，所以说红黑树的插入删除效率比AVL树要高，而AVL树对于平衡要求较高导致了它的查询效率比红黑树高，但实际上差别并不是很大！最终看一下红黑树的效果图：

了解旋转

在继续讲解红黑树之前，旋转是必须要掌握的。在上一篇AVL平衡二叉树中我们详细说明了什么是旋转、旋转的几种情况，希望不懂的同学可以先去了解下，毕竟这是前提，这里只是简单帮助同学回忆下。

左旋

节点8左旋之后，由一开始节点8的右子树为节点10变成了节点10的左子树为节点8，同时根节点变成了节点10。

右旋

节点8右旋之后，由一开始节点8的左子树为节点6变成了节点6的右子树为节点8，同时根节点变成了节点6。

红黑树的插入

上面说了节点要么是红色要么是黑色，对于新插入的节点来说也是如此。假设新插入的节点是黑色，那么某条路径上便会多出来一个黑色节点，除了将其改成红色之外其余的方式，包括左旋、右旋，都无法改变会多出来一个黑色节点，所以它完全满足不了红黑树的第五特性，那么留下来的只有红色了，故而新插入的节点颜色是红色的！在想想，若新插入的节点是红色的话，会造成哪里不平衡，也就是说会违背哪些特性：

• 每个节点要么是红色要么是黑色。

• 根节点是黑色。

• 叶节点是黑色。

• 如果一个节点是红色，那么它的子节点是黑色，相当于父子节点之间不能出现连续的红色节点。

• 从任意节点出发到任意叶节点的所有路径上均包含相同数目的黑色节点。

第一条显然没有违背；对于空树来说，新插入的红色节点违背了该条，不过调整起来很简单，并不是关键点；新插入的节点并未来影响到叶节点；新插入的红色节点有可能它的父节点也是红色，故违背了该条，接下来的内容是针对此情况进行重点分析；新插入的节点为红色正是为了不违背该条。

插入情况分析

现在来分析新插入的红色节点可能出现的情况，以及它们的处理措施，这里我们假设新插入的红色节点为X：

• 若X是根节点，将其变成黑色皆可。

• 若X的父节点是黑色，则不需要任何黑色。

• 若X的父节点是红色，叔叔节点（隶属于同一个父节点）也是红色，解决方案如下：

  • 将X的父节点与叔叔节点变成黑色。

  • 将X的爷爷节点变成红色。

  • X的爷爷节点变成红色后，有可能会出现连续红色节点的冲突，若有的话则将X的爷爷节点当作是新插入的节点，继续重复31、32操作，直到当前节点是根节点，最后将根节点变成黑色。

如图所示红黑树：

新插入的红色节点X为125，如图所示红黑树：

节点125和其父节点130都是红色节点，违背了第四点要求，所以将节点125的父节点130与叔叔节点150变成黑色，同时将节点125的爷爷节点140变成红色，如图所示：

节点140和其父节点120都是红色节点，也违背了第四点要求，我们可以将节点140看成是新插入的节点。所以将节点140的父节点120与叔叔节点60变成黑色，同时将节点140的爷爷节点90变成红色，由于节点90是根节点，又将其节点90变成了黑色，如图所示：

到这里，新插入的红色节点125一开始不满足红黑树的特性到所作的一系列调整，最终变成了标准的红黑树！

• 若X的父节点是红色，叔叔节点是黑色（空），解决方案如下：

  • X和X的父节点在X的爷爷节点的左子树上（左左情况）。

  • X和X的父节点在X的爷爷节点的右子树上（右右情况）。

  • 以上的两种情况（4142）都是同一个处理措施，只不过旋转的方向不一致。

    • 将X的父节点与X的爷爷节点进行颜色互换。

    • 将X的爷爷节点进行左/右旋，左左情况是右旋，右右情况是左旋。

如图所示红黑树（左左情况）：

新插入的红色节点X为25，如图所示红黑树：

节点25的父节点30为红色，叔叔节点为黑色，且节点25与父节点30都是节点50的左子树，所以将节点30与节点50进行颜色互换，同时将节点50进行右旋，如图所示：

以上是左左情况下该如何处理，右右情况的话只需要左旋即可，很简单！这边提下为啥要进行旋转，单是颜色互换其实你会发现90->60->50->null这条路径上少了一个黑色节点数目，它并不满足第五点要求，所以旋转是必须的。

• 若X的父节点是红色，叔叔节点是黑色（空），该情况与上面的第四点有些类似，解决方案如下：

  • X的父节点在X的爷爷节点的左子树上，X在X的父节点的右子树上（左右情况）。

  • X的父节点在X的爷爷节点的右子树上，X在X的父节点的左子树上（右左情况）。

  • 以上的两种情况（5152）都是同一个处理措施，只不过旋转的方式不一样。

    • 将X的父节点进行左/右旋，左右情况是左旋，右左情况是右旋。

    • 注意旋转后，X将会变化，将X的父节点与X的爷爷节点进行颜色互换。

    • 将X的爷爷节点进行左/右旋，左右情况是右，右左情况是左旋，因为前面已经旋转过一次了，故后面是另外一个旋转，就比如左右，先左旋在右旋。

如图所示红黑树（左右情况）：

新插入的红色节点X为126，如图所示红黑树：

节点126的父节点125为红色，叔叔节点为黑色，且节点125在节点130的左子树上，节点126在节点125的右子树上，所以将节点125进行左旋，如图所示：

不知道发现没有，旋转后的红黑树跟第四点提到的情景是一样的，故处理方式也是一直。此时的X应该是节点125，故将节点126与节点130进行颜色互换，同时将节点130进行右旋，如图所示：

最终也是一颗标准的红黑树！以上是左右情况下该如何处理，右左情况的话也是差不多，不过多介绍了！

插入情况总结

整理下插入节点的情况及措施，假设新插入的节点为X：

• X是根节点：将其变成黑色即可。

• X的父节点为黑色：不需要任何操作。

• X的父节点为红色：

  • 叔叔节点为红色：将X的父节点与叔叔节点变成黑色；将X的爷爷节点变成红色；X的爷爷节点变成红色后，有可能会出现连续红色节点的冲突，若有的话则将X的爷爷节点当作是新插入的节点，继续重复上面的操作，直到当前节点是根节点，最后将根节点变成黑色。

  • 叔叔节点为黑色：

    • X在左子树上，父节点也在左子树上（左左情况） || X在右子树上，父节点也在右子树上（右右情况）：将X的父节点与X的爷爷节点进行颜色互换，将X的爷爷节点进行左/右旋，左左情况是右旋，右右情况是左旋。

    • 父节点在左子树上，X在右子树上（左右情况） || 父节点在右子树上，X在左子树上（右左情况）：将X的父节点进行左/右旋，左右情况是左旋，右左情况是右旋，旋转后会发现与321的情况一样，然后按照321的情况继续处理，因为已经旋转过一次了，所以左右情况是右旋，右左情况是左旋。

了解完以上的所有情况后，不知道你们会不会觉得有点难。实际上每一种情况对应着一种处理方式，你只需对应上即可，不过关键还是要去理解它！

总结

以上只是单纯地列出了红黑树的插入，并未介绍删除的原理，虽然我私底下也做了很多关于这方面的功课，无奈无法总结出一套较为完整且正确的分析流程，个人认为其删除过于复杂，想要挑战的同学可以参考HashMap源码中对这方面的操作。最后推荐个数据结构可视化网站，可调试二叉树、AVL树、红黑树。