前言

希望面对面试官的各种红黑树的灵魂拷问时，也能像标题一般，优雅地娓娓道来。

一、红黑树的基本性质

先简单地说一下红黑树的规则： 

1、根节点为黑色

 2、叶子节点（值为NULL的节点）为黑色

 3、红色节点的子节点为黑色

 4、新插入的节点为红色

5、从一个节点访问到叶子节点，任意一条路径上黑色节点的数量相同

二、为什么要用红黑二叉树

 面试官也会有其他的问法：“为什么有了BST和AVL，还要用红黑树呢？”想要清楚地回答这些问题，就要先了解二叉搜索树和二叉平衡搜索树。

1、 二叉搜索树（Binary Search Trees）

所谓二叉搜索树，可提供对数时间的元素插入和访问。二叉搜索树的节点放置规则是：任何节点的键值一定大于去其左子树中的每一个节点的键值，并小于其右子树的每一个节点的键值。 

可以看到，二叉树的插入、查询数据时，只需要和每一层的一个数据比较就行了，这就说明，插入和查询的时间复杂度取决于树的高度。 

缺点： 当插入的数据有序时，二叉树会退化为一个链表，查询或插入的时间复杂度降为logN

2、二叉平衡搜索树（Balanced binary search trees） 

为了解决BST的缺点，AVL应运而生。        

 AVL的性质：

1、拥有二叉树的全部特性；

2、每个节点的左子树和右子树的高度差不超过1；

3、左右两个子树都是一棵平衡二叉树

为了满足第二点性质，平衡二叉树的节点不会出现一边倒的情况，但是需要做大量的操作（左旋、右旋等）来满足这一条件，使得其最坏情况下查找的时间复杂度也还是为O(logn)。

AVL树的构建这里就不多赘述了，我们主要来讲红黑树。

 3、 总结：为什么要用红黑树

用一句话来概括就是：BST会退化为链表，AVL太麻烦，红黑树是一个折中的办法。 

虽然AVL树解决了二叉搜索树退化了近似链表的缺点，但是由于每个节点的左子树和右子树的高度差不超过1这个要求实在是太严苛了，导致每次插入和删除节点的时候很容易就破坏了这条规则，之后就需要左大量的左旋和右旋来进行调整时期再次符合AVL树的要求。

所以如果在插入和删除很频繁的场景中，AVL树需要很频繁地进行调整，这样的话效率就大大降低了，为了解决这个问题所以出现了红黑树。（如果在面试中接下来这里就可以说出红黑树的那5个特点）。

正由于红黑树的这些特点，使其最坏情况下不仅还能维持用O(logn)的时间复杂度找到某个节点，而且与AVL树相比，优势就在于不会那么频繁地破坏红黑树的规则，从而不用那么频繁地进行调整，这就是我们大多数情况下使用红黑树的原因。

所以红黑树是一种相对AVL树来说不那么严格的平衡树，也就是一种折中的方案，介于普通的二叉搜索树和AVL树之间。极端情况下左右子树的节点数（也就是深度）相差一倍，也就是左边都有黑节点，右边都是红黑相间，右子树的节点数或者说深度就也是左子树的2倍，这个要求就比AVL树的相差最多只能为1宽松多了，因此调整也就更少，效率也就更高。

三、红黑树的插入 

插入的节点为红色节点，而要满足红黑树的那5个性质，就需要旋转和变色，先说一下旋转和变色的规则，表格来自B站UP主free-coder（尊重一下知识产权）： 

可能乍一看表格还看不太懂，那么我们来根据表格把所有的情况都解释一下：

1、父节点为黑色

直接插入即可

2、父节点为红色，叔叔节点为红色 

先看一下完整过程，再分解步骤

（1）原树 

（2）加入新节点 

（3）父、叔变黑，祖父变红 

（4）将祖父节点看作新插入节点，递归表格中的规则（这里祖父节点为根节点，所以变为黑节点了）

3、父节点为红、叔叔节点为黑，新节点是祖父节点的右子节点的右子节点（上表中的：右右）

新增节点的父节点为20，红色；叔叔节点为null叶子节点，黑色。 

4、 父节点为红、叔叔节点为黑，新节点是祖父节点的左子节点的左子节点（上表中的：左左）

其实和3是对称的。 

5、 父节点为红、叔叔节点为黑，新节点是祖父节点的右子节点的左子节点（上表中的：右左）

在第一次右旋之后，就变成了3中的情况。 

6、 父节点为红、叔叔节点为黑，新节点是祖父节点的左子节点的右子节点（上表中的：左右）

和5中对称。经过一次左旋之后，变成4中情况，再进行一次右旋后，变色。 

四、删除节点

等我强大一点再来吧（肝不动了~~~~）

五、红黑树的应用场景 

1、JDK的HashMap、TreeMap和TreeSet

2、Linux内核的虚拟内存管理

 3、Nginx的Timer管理

4、C++的STL

这里要注意，如果面试官问到这个问题，你回答HashMap中用过，那下一步多半是要问问你HashMap中怎么用的，接下来可能就是问HashMap的原理……。所以回答这些名词的时候一定要确保自己顶得住接下来可能出现的夺命连环问，千万不要贪多只背这些名字。  

六、结尾 

种下的不仅是红黑树，更是对offer的憧憬。 

参考：红黑树，这次终于拿下了