白话：红黑树及源码的套路（上）

上一节聊到HashMap，我们在读源码的过程中，发现HashMap在JDK1.8之后对链表部分的实现进行了改进，从源码不难看出，当HashMap中某一个链表长度超过阈值(TREEIFY_THRESHOLD = 8 )之后，就会将该链表树化。当我们看到内部类TreeNode定义时，会看到该树类型为红黑树——red-black tree。
本节就结合HashMap中红黑树的源码，具体梳理一下红黑树和它如何与HashMap结合。以下为文章路径：

HashMap为什么从链表换成了树
从平衡二叉树到红黑树
红黑树的左旋和右旋（源码解析）
红黑树的插入自平衡（源码解析）
红黑树的删除自平衡（源码解析）
HashMap中的红黑树（源码解析）

HashMap为什么从链表换成了树

上一节我们在阅读源码的时候，发现这样一句话：

 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
       treeifyBin(tab, hash);

当链表节点的计数超过TREEIFY_THRESHOLD - 1则将该链表树化，为什么要这样呢？其实比较一下链表和树的优缺点就能大致明白该优化的目的。我们假设一条链表上有10个节点，在查询时，最坏情况需要查询10次，N(10)。对于树而言不同的树复杂度不同，但是对于最基本的二叉树：左子树一定比root小，右子树一定比root大，相当于是通过二分法在进行查找，查询速度绝大部分时候比链表要快。但是一般人们理解的二叉树（又叫二叉搜索书 BST）会出现一个问题，正常情况它是这样的：

普通BST

但是也有可能出现这样一种情况：树的节点正好从大到小的插入，此时树的结构也类似于链表结构，这时候的查询或写入耗时与链表相同：

特殊BST

为了避免这种特殊的情况发生，引入了平衡二叉树（AVL）和红黑树（red-black tree）。它们都是通过本身的建树原则来控制树的层数和节点位置，因为rbtree是由AVL演变而来，所以我们从了解AVL开始。

从平衡二叉树到红黑树

平衡二叉树
平衡二叉树也叫AVL（发明者名字简写），也属于二叉搜索树的一种，与其不同的是AVL通过机制保证其自身的平衡。
平衡二叉树的原则有以下几点：

对于根结点而言，它的左子树任何节点的key一定比其小而右子树任何节点的key一定比其大；
对于AVL树而言，其中任何子树仍然是AVL树；
每个节点的左右子节点的高度之差的绝对值最多为1；
在插入、删除树节点的时候，如果破坏了以上的原则，AVL树会自动进行调整使得以上三条原则仍然成立。举个例子，下左图为AVL树最长的2节点与最短的8节点高度差为1；当插入一个新的节点后，根据上面第一条原则，它会出现在2节点的左子树，但这样一来就违反了原则3。

AVL树平衡破坏

此时AVL树会通过节点的旋转进行调整，AVL调整的过程称之为左旋和右旋，这里我想说，无论这个树多么复杂，我们聚焦到失去平衡的地方，很多文章在介绍旋转的时候往往忽视了第一步，就是确定旋转点，这个旋转点就是失去平衡这部分树，在自平衡之后的根节点——pivot，因为我们要根据它来进行旋转。
我们在学习AVL树的旋转时，不要将失衡问题扩大到整个树来看，这样会扰乱你的思路，我们只关注失衡子树的根结点及它的子节点和孙子节点即可。事实上，AVL树的旋转，我们权且叫“AVL旋转”是有规律可循的，因为只要聚焦到失衡子树，那么场景就是有限的4个：
场景1 左左结构：

左左结构

场景2 右右结构：

右右结构

场景3 左右结构：

左右结构

场景4 右左结构：

右左结构

可见无论哪种情况的失衡，都可以通过旋转来调整。不难看出，旋转在图上像是将pivot节点向上提（将它提升为root节点），而后两边的节点会物理的分布在新root节点的两边，接下来按照二叉树的要求：左子树小于root，右子树大于root进行调整。从图左左结构可以看出，当右旋时原来pivot（7）的右子树会转变到用root点（9）的左子树处；从图右右结构可见，当左旋时，原来pivot（18）的左子树会分布到原root点（9）的右子树。
对于左右结构和右左结构无非是经过多次旋转达到稳定，旋转的方式并没有区别，所以总结下来：

AVL树平衡总结

既然AVL树可以保证二叉树的平衡，这就意味着它最坏情况的时间复杂度O(logn) 要低于普通二叉树和链表的最坏情况O(n)。那么HashMap就直接使用AVL树来替换链表就好了，为什么选择用红黑树呢？
我们会发现，由于AVL树必须保证Max(最大树高-最小树高) <= 1所以在插入的时候很容易出现不平衡的情况，一旦这样，就需要进行旋转以求达到平衡。正是由于这种严格的平衡条件，导致需要花大量时间在调整上，故AVL树一般使用场景在于查询而弱于增加删除。红黑树继承了AVL可自平衡的优点，同时在查询速率和调整耗时中寻找平衡，放宽了树的平衡条件，在实际应用中，红黑树的使用要多得多。

红黑树（RBTree）
红黑树也是一种自平衡二叉查找树，它与AVL树类似，都在添加和删除的时候通过旋转操作保持二叉树的平衡，以求更高效的查询性能。与AVL树相比，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。
红黑树的原则有以下几点：

节点非黑即红
整个树的根节点一定是黑色
叶子节点（包括空叶子节点）一定是黑色
每个红色节点的两个子节点都为黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
基于上面的原则，我们一般在插入红黑树节点的时候，会将这个节点设置为红色，原因参照最后一条原则，红色破坏原则的可能性最小，如果是黑色很可能导致这条支路的黑色节点比其它支路的要多1。一旦红黑树上述原则有不满足的情况，我们视为平衡被打破，红黑树会通过变色、左旋、右旋的方式恢复平衡。前文已经详细解释过什么是左旋和右旋，这里就不赘述；变色这个概念很好理解，就是红变黑或黑变红。但是我们会好奇，红黑树的平衡会不会和上文的AVL树一样，也有可以归纳的平衡场景呢？答案是肯定的：
场景1 第一次插入：
RBTree第一次插入节点时，新节点会是红色，违背了原则二，直接将颜色变黑即可。
场景2 父节点为黑色：
当插入时节点为红色且父节点为黑色，满足RBTree所有原则，已经平衡。
场景3 父节点为红色且叔叔节点为红色：

父节点叔叔节点都为红色

在平衡的过程中，要注意红黑树的规定原则。插入红节点，不能仅仅将父节点由红变黑，因为这样会增加这条支路的黑节点数，从而违反“从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点”。将父节点和叔叔节点都变黑，再将祖父节点由黑变红，这样一来，以13为root的红黑树对外黑色节点数没变，对内各条支路节点数一致。
场景4 父节点为红色，叔叔节点为黑色且新节点为右子树：

左旋将右子树变为左子树

节点8的父节点为红，叔叔节点为黑且，通过左旋的方式，让整个情况变成下一个场景：父节点红色，叔叔节点为黑色且新节点为左子树。
场景5 父节点为红色，叔叔节点为黑色且新节点为左子树：

完成BRTree平衡

这五个场景就可以涵盖所有的红黑树未平衡的场景，总结起来就是：

红黑树总结

本文从概念上介绍了红黑树及其前辈AVL树，已经它们自平衡的方式和过程，从下一篇开始我们会对红黑树源码进行阅读，加深其理解。