树形结构——红黑树

1. 前言
   在 JDK1.8 之后，HashMap 的底层是由数组、链表、红黑树来实现的，当数组长度到 64 的时候，或者链表长度到 8 的时候，会调用 treeifyBin 转换为红黑树实现。因为红黑树是小伙伴们面试的时候经常被考到的知识点，因此我们本节就帮大家理解红黑树的性质和操作。充分理解后具体的代码实现就很简单了，大家可以自己去实现，也可以直接参考 java.util.HashMap 中的源码。
   

2. 红黑树的前世今生
   红黑树是一种接近平衡的二叉搜索树，它能够保证任意一个节点左右子树的高度差不会超过较低子树的高度，也就是两棵子树的高度比值不会超过 2 倍。这样我们可以使搜索的时间复杂度更接近 O (logN)。为了保证树的平衡，我们需要在添加或删除元素的时候不断的调整树的结构，使每个节点的左右子树上的节点个数尽可能相等。

3. 红黑树的性质
   红黑树的性质有五点，这里需要大家牢牢记住：

• 每个节点不是红色就是黑色；
• 根节点永远是黑色；
• 红色节点的子节点必须是黑色；
• 任意一个节点到每个叶子节点的路径上都包含相同数量的黑色节点；
• 每次添加新节点都默认为红色。

4. 红黑树调整的方式
   如果每次添加节点都设置为红色，当父节点已经是红色时，会违背上面的第 3 条性质，这时候我们需要按照一定的方法去调整树，调整的方式有三种：改变节点颜色、左旋和右旋。

• 改变节点颜色如下图，我们依次做了以下尝试：
• 

①　默认红色：违反性质 3；
②　默认黑色：违反性质 4；
③　默认红色，将父节点和父节点的兄弟节点改为黑色，满足全部 5 条性质。

• 左旋：拎起左旋节点的右子节点，使左旋节点向左下沉，成为右子节点的左子节点，右子节点上升成为其父节点。

右旋：拎起右旋节点的左子节点，使右旋节点向右下沉，成为左子节点的右子节点，左子节点上升成为其父节点。

5. 红黑树的插入操作
   插入元素会导致原本平衡的红黑树失去平衡，还会导致红黑树五大特性的不满足。因此插入后我们需要做调整，使其重新成为一个红黑树。

5.1 把大象放冰箱的第一步是把冰箱门打开
把元素插进红黑树的第一步是找到要插入的位置。寻找位置的方法其实也比较简单：
①　如果是空树，直接插入到跟节点；
②　如果与当前节点的 key 值相等，则更新当前节点的 value 值；
③　如果比当前节点的 key 值大，则继续寻找当前节点的右子节点；
④　如果比当前节点的 key 值小，则继续寻找当前节点的左子节点；
⑤　如果当前节点为 null（或 nil 节点），则插入在当前节点的父节点下。

5.2 插入后重新调整至平衡状态
前面我们说了调整的方式，那么我们在什么情况下使用什么方式调整呢？
我们可以看 JDK1.8 的 HashMap 中对红黑树的调整源码，来了解在什么情况下使用什么样的调整方式来重新使树恢复平衡。情况略显复杂，我把说明以注释的形式标在源码上，大家可以根据 if 条件来梳理逻辑线。

   static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) {
       x.red = true;
       for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
           //false条件：当前节点存在父节点
           if ((xp = x.parent) == null) {
               //父节点为空，当前节点是根节点，直接设置根节点为黑色后返回
               x.red = false;
               return x;
           }
           //false条件：且父节点是红色，且存在爷爷节点
           else if (!xp.red || (xpp = xp.parent) == null)
               return root;
           if (xp == (xppl = xpp.left)) {
               //false条件：且叔叔节点为空，或者是黑色；
               if ((xppr = xpp.right) != null && xppr.red) {
                   xppr.red = false;
                   xp.red = false;
                   xpp.red = true;
                   x = xpp;
               }
               else {
                   //true条件：当前节点是其父节点的右子节点；
                   if (x == xp.right) {
                       // 左旋父节点
                       root = rotateLeft(root, x = xp);
                       // 爷爷节点不存在则结束，存在则将指针指向父节点
                       xpp = (xp = x.parent) == null ? null : xp.parent;
                   }
                   // true条件：父节点不为空
                   if (xp != null) {
                       // 父节点变为黑色
                       xp.red = false;
                       // true条件：祖父节点不为空
                       if (xpp != null) {
                           // 祖父节点变为红色
                           xpp.red = true;
                           // 右旋祖父节点
                           root = rotateRight(root, xpp);
                       }
                   }
               }
           }
           else {
               //false条件：且叔叔节点为空，或者是黑色；
               if (xppl != null && xppl.red) {
                   // 当前节点的父节点以及左叔父节点都是红色 则颜色变为黑色
                   xppl.red = false;
                   xp.red = false;
                   // 黑节点的父节点必须红色
                   xpp.red = true;
                   x = xpp;
               }
               else {
                   //true条件：当前节点是其父节点的左子节点；
                   if (x == xp.left) {
                       // 右旋父节点
                       root = rotateRight(root, x = xp);
                       // 指针指向父节点
                       xpp = (xp = x.parent) == null ? null : xp.parent;
                   }
                   // true条件：父节点不为空
                   if (xp != null) {
                       // 父节点变为黑色
                       xp.red = false;
                       // true条件：祖父节点不为空
                       if (xpp != null) {
                           // 祖父节点变为红色
                           xpp.red = true;
                           //  右旋祖父节点
                           root = rotateLeft(root, xpp);
                       }
                   }
               }
           }
       }
   }

6. 红黑树的删除操作
   删除操作可能触发的情况分为有子节点和无子节点，没有子节点的情况非常简单，直接删除后执行自平衡即可。有子节点的时候我们要先找到替换节点，如果只有一个子节点，这个节点就是替换节点；如果有两个子节点，要找到左子树的最大节点或右子树的最小节点作为替换节点。感兴趣的小伙伴可以通过源码中的 removeTreeNode 方法梳理一下，这里我们不做展开了。

7. 小结
   本节我们学习了重要的树形结构——红黑树，我们要牢记红黑树五大特性，结合动图了解变色、左旋和右旋的思路和方法，再去了解红黑树插入和删除操作的再平衡过程。学习红黑树一定要先理解再动手写代码，依据红黑树的五大特性，在插入和删除操作中来调整结构使树尽量保持平衡，来确保对整个数据结构的插入、删除和查找效率。
   在学习过程中，我们也可以更多的借助 JDK 源码来帮助我们梳理思路，从而帮助我们更快速、清晰、准确的理解红黑树。