红黑树底层详解

1 红黑树的性质

1. 每个节点要么是黑色，要么是红色。
2. 根节点是黑色。
3. 每个叶子节点（NIL）是黑色。
4. 每个红色节点的两个子节点一定都是黑色。不能有两个红色节点相连。
5. 任意一节点到每个叶子节点的路径都包含数量相同的黑结点。俗称：黑高！

从性质5又可以推出：性质5.1：如果一个节点存在黑子节点，那么该结点肯定有两个子节点。

红黑树并不是一个完美平衡二叉查找树，从图上可以看到，根结点P的左子树显然比右子树高，但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5)。所以我们叫红黑树这种平衡为黑色完美平衡。

2 红黑树的自平衡（左旋、右旋和变色）

1、变色

结点的颜色由红变黑或由黑变红。

2、左旋

以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。

左旋图示：

代码实现：

/**
         * 红黑树左旋
         * @param root 树的根节点
         * @param p 旋转的节点
         * @return
         */
        static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                              TreeNode<K,V> p) {
            // r：旋转节点的右节点
            // pp: 旋转节点的父节点
            // rl：旋转节点的右节点的左节点
            TreeNode<K,V> r, pp, rl;
            // 因为左旋之后旋转节点的右子节点成为旋转节点的父节点，所以：旋转节点不为null，旋转节点的右子节点不为空null可以进行左旋
            if (p != null && (r = p.right) != null) {
                // 左旋使旋转节点的右子节点的左子节点成为旋转节点的右子节点，
                // 旋转节点的右子节点的左子节点赋值给旋转节点的右子节点 并赋值给rl
                if ((rl = p.right = r.left) != null)
                    rl.parent = p;// 旋转节点的右子节点的左子节点认下p节点作为父节点
                // 将旋转节点的父节点赋值给旋转节点的右子节点的父节点（p的父去做r的父）并且用pp记录
                // 如果为空说明r就是跟节点了，需要标记为黑色
                if ((pp = r.parent = p.parent) == null)
                    (root = r).red = false;
                // 下面的判断是 旋转节点的父，认下旋转节点的右子节点作为哪个儿子
                else if (pp.left == p)
                    pp.left = r;
                else
                    pp.right = r;
                r.left = p; // 旋转节点作为旋转节点的右子节点的左儿子
                p.parent = r;// 上面是r认p做儿，这里是p认r作为父
            }
            return root;
        }

(rl = p.right = r.left) 这句代码的意思是 r的左节点，赋值给p的右节点，并且用rl标记这个节点。

-> p.right = r.left; rl = p.right; 就是这两个语句。

3、右旋

以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。

右旋图示：

代码实现：

/**
         * 右旋
         * @param root 根节点
         * @param p 旋转节点
         * @return
         */
        static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {
            // l:旋转节点的左子节点，pp：旋转节点的父节点，lr：旋转节点的左子节点的右子节点。
            TreeNode<K,V> l, pp, lr;
            //判断旋转节点，以及旋转节点的左子节点不能为空
            if (p != null && (l = p.left) != null) {
                //将旋转节点的左子节点的右子节点赋值给旋转节点的左指针，并用lr标记这个节点。旋转节点认左儿子
                if ((lr = p.left = l.right) != null)
                    lr.parent = p;//旋转节点的左子节点的右子节点认旋转节点做父
                // 将旋转节点的父节点赋值给旋转节点的左子节点的父指针，并用pp标记这个节点，如果等于null说明旋转节点是根节点。
                if ((pp = l.parent = p.parent) == null)
                    (root = l).red = false;//那么现在旋转节点的左子节点就是根节点，标记为黑色
                // 如果旋转节点的父节点不等于null，那么它的指针指向l（认下儿子）。
                else if (pp.right == p)
                    pp.right = l;
                else
                    pp.left = l;
                //l 认下p 作为 右儿子
                l.right = p;
                //p 认下 l 做 父
                p.parent = l;
            }
            return root;
        }

3 红黑树的插入

注意：插入节点，必须为红色，理由很简单，红色在父节点（如果存在）为黑色节点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。

3.1 红黑树的树化

HashMap在链表长度>8（默认值）和table数组长度>=64（默认值）时就会将链表树化。

下面看树化的过程：

3.1.1 链表结构替换

将Node节点链表结构替换为TreeNode节点链表结构

treeifyBin方法

put方法中，如果达到了树化的条件(链表长度>8) 执行treeifyBin()

这个方式首先判断table数组的****长度是否达到了树化阈值(默认64)，如果没有达到，那么进行扩容操作。如果达到了，那么将这个桶内的链表(Node)，转化为链表(TreeNode) 。然后 执行treeify方法 进行树化。

/**
     * Replaces all linked nodes in bin at index for given hash unless
     * table is too small, in which case resizes instead.
     *
     * 树化，如果table表没有达到默认值，那么进行扩容
     */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    // tab: table数组
    // hash: 当前插入节点的key的hash值
    // n: table数组长度
    // index: 当前hash所在的桶位置索引
    // e: 当前桶位置的头节点
    int n, index; Node<K,V> e;
    // 如果table数组长度小于默认值，那么进行扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    //头节点不为null
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 下面的过程是：将链表节点（Node）替换为树节点（TreeNode），还是链表结构
        // hd：树节点链表的头节点
        // tl: 临时变量
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 将一个链表节点，替换为一个树节点并返回
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        //将树节点的链表结构放入桶中，判断是否为空
        if ((tab[index] = hd) != null)
            //不为空，进行树化。hd：树节点
            hd.treeify(tab);
    }
}

3.1.2 链表树化

treeify方法

该方法的作用是：将链表(TreeNode) 树化，并且在每一次节点插入树中时执行balanceInsertion方法自平衡，最后执行moveRootToFront方法保证根节点是桶位置的第一个节点即头节点

/**
         * 将树节点链表转为树结构
         * 这个方法是TreeNode的内部方法，通过TreeNode调用
         * Forms tree of the nodes linked from this node.
         * @return root of tree
         * @param tab 传入的table数组
         */
final void treeify(Node<K,V>[] tab) {
    // 树化，在从树节点链表->树的过程中，this指的是当前桶位置上的头节点（树节点），桶位置上还是链表
    // root: 树的根节点。
    TreeNode<K,V> root = null;
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        // 当前节点的下一个节点
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        //说明当前是第一个节点
        if (root == null) {
            x.parent = null;
            // 表示是一个黑节点
            x.red = false;
            root = x;
        }
        else {// 说明当前不是第一个节点
            // 记录当前节点的key，hash
            K k = x.key;
            int h = x.hash;
            //kc : k如果是Comparable的实例，那么返回运行时的类型
            Class<?> kc = null;
            // 遍历当前树
            for (TreeNode<K,V> p = root;;) {
                // dir: 用于判断x树节点应该放在left，还是right上
                // ph: 当前树上节点的hash值
                // pk: 当前树上节点的key值
                int dir, ph;
                K pk = p.key;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);

                TreeNode<K,V> xp = p;
                // 判断是否遍历到了树的叶子节点，如果是那么直接将x放到树上，结束循环。
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    // 向树中插入了一个节点，进行自平衡操作
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    moveRootToFront(tab, root);
}

3.2 红黑树的插入

putTreeVal方法

**该方法：**添加一个树节点 ，执行该方法时说明链表已经树化过了，桶上就已经是树了。

/**
         * Tree version of putVal.
         * 树节点的put过程
         * @param map HashMap
         * @param tab HashMap的散列表数组
         * @param h 要添加key的hash值
         * @param k 要添加的key
         * @param v 要添加的value
         * @return
         */
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                               int h, K k, V v) {
    // kc: 如果key是一个Comparable类型的实现，那么保存key运行具体类型，否则保存null
    Class<?> kc = null;
    boolean searched = false;
    // root: 树的根节点
    TreeNode<K,V> root = (parent != null) ? root() : this;
    // 遍历树
    for (TreeNode<K,V> p = root;;) {
        // dir：用于记录，插入的节点应该在当前节点的左节点还是右节点
        // ph: 当前节点的hash值
        // pk: 当前节点的key值
        int dir, ph; K pk;
        // 说明新插入的节点应该在当前节点的左子树上
        if ((ph = p.hash) > h)
            dir = -1;
        // 说明新插入的节点应该在当前节点的左子树上
        else if (ph < h)
            dir = 1;
        // 说明新插入的节点和当前节点的key值相同，那么不做处理直接返回，由上层方法修改value值
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            if (!searched) {
                TreeNode<K,V> q, ch;
                searched = true;
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    return q;
            }
            dir = tieBreakOrder(k, pk);
        }
        // 判断是否遍历到了叶子节点，如果是将插入的节点插入进去，如果不是继续遍历
        TreeNode<K,V> xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            Node<K,V> xpn = xp.next;
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            xp.next = x;
            x.parent = x.prev = xp;
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            // 插入完成之后，先进行一个自平衡操作，然后保证root根节点是桶的头节点
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

3.3 重要方法

下面这几个方法都是TreeNode结构的内部方法。

3.3.1 balanceInsertion()

/**
         * 新插入一个节点之后，从低到上进行树自平衡操作，就是变色，左旋，右旋操作，直到满足红黑树的性质
         * @param root 树的根节点
         * @param x 新插入的树节点
         * @return 返回根节点。
         */
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                            TreeNode<K,V> x) {
    //将新插入树中的节点设为红节点，插入到树中的节点必须是红色
    x.red = true;
    // x: 新插入到树中的节点
    // xp: x的父节点
    // xpp: xp的父节点
    // xppr: xpp的右节点
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
        // 情况一：红黑树为空树，x的父节点为空，那么x节点就是一个跟节点，是黑节点
        if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        // 情况二：插入节点的父节点为黑色
        else if (!xp.red || (xpp = xp.parent) == null)
            //直接返回 说明 x就是一个红节点
            return root;
        // 情况三：插入节点的父节点为红色
        // 情况3.1：父节点是祖父节点的左子节点，依据红黑树性质4可知：红色节点不能相连 ==> 祖父结点肯定为黑结点；
        if (xp == (xppl = xpp.left)) {
            // 叔叔结点存在并且为红结点，那么该插入子树的红黑层数的情况是：黑红红。显然最简单的处理方式是把其改为：红黑红。
            if ((xppr = xpp.right) != null && xppr.red) {
                xppr.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            // 叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子节点
            else {
                //新插入节点，为其父节点的右子节点（LR红色情况）将LR红色情况经过左旋改为LL情况
                // 这个条件执行会将当前节点设为父节点，下面if对祖父节点的父节点自平衡（在祖父节点存在的的情况下）
                if (x == xp.right) {
                    // 对父节点左旋。当前节点设为父节点
                    root = rotateLeft(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                // 进入这个条件表示，新插入节点，为其父节点的左子节点（LL红色情况）如果是LR情况，经过上面处理后也变成了LL情况
                if (xp != null) {
                    // 目前红黑层数的情况是：黑红红，所以要改为红黑红
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true;
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        //情况3.2：父节点是祖父节点的右子节点
        else {
            // 叔叔结点存在并且为红结点，那么该插入子树的红黑层数的情况是：黑红红。显然最简单的处理方式是把其改为：红黑红。
            if (xppl != null && xppl.red) {
                xppl.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            // 叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子节点
            else {
                //新插入节点，为其父节点的左子节点（RL红色情况）将RL红色情况经过右旋改为RR情况
                // 这个条件执行会将当前节点设为父节点，下面if对祖父节点的父节点自平衡（在祖父节点存在的的情况下）
                if (x == xp.left) {
                    // 对父节点右旋。当前节点设为父节点
                    root = rotateRight(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                // 进入这个条件表示，新插入节点，为其父节点的右子节点（RR红色情况）如果是RL情况，经过上面处理后也变成了RL情况
                if (xp != null) {
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true;
                        //对祖父节点左旋
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}

(1) 自平衡流程

1) 情景1：红黑树为空树

最简单的一种情景，直接把插入结点作为根结点，并且设为黑色。

**根据红黑树性质2：**根节点是黑色。

**2) 情景2：**插入节点的父节点为黑节点

由于插入的结点是红色的，并不会影响红黑树的平衡，直接插入即可，无需做自平衡。

**3) 情景3：**插入节点的父节点是红色节点

根据红黑树的性质2：根结点是黑色。如果插入节点的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。根据红黑树性质4：每个红色节点的两个子节点一定都是黑色。不能有两个红色节点相连。 所以祖父节点一定存在且是红色的。

衍生出两种情况：

3.1) 父节点是祖父节点的左子节点

3.1.1) 叔叔结点存在并且为红结点

那么该插入子树的红黑层数的情况是：黑红红。显然最简单的处理方式是把其改为：红黑红。

处理：

1. 将P和U节点改为黑色
2. 将PP改为红色
3. 将PP设置为当前节点，进行后续处理

可以看到，我们把PP结点设为红色了，如果PP的父结点是黑色，那么无需再做任何处理；

但如果PP的父结点是红色，则违反红黑树性质了。所以需要将PP设置为当前节点，继续做插入操作自平衡处理，直到平衡为止。

3.1.1) 叔叔结点不存在或为黑结点

新插入节点，为其父节点的右子节点（LR红色情况）

处理：

1. 对P进行左旋。
2. 将P设置为当前节点，得到LL红色情况。
3. 按照LL红色情况处理（1.变颜色 2.右旋PP）。

新插入节点，为其父节点的左子节点（LL红色情况）

处理：

1. 变颜色：将P设置为黑色，将PP设置为红色。
2. 对PP节点进行右旋。

3.2) 父节点是祖父节点的右子节点

3.2.1) 叔叔结点存在并且为红节点

这种情况和父节点是祖父节点的左子节点一样

3.2.1) 叔叔结点不存在或为黑节点

新插入节点，为其父节点的左子节点（RL红色情况）

处理：

1. 对P进行右旋。
2. 将P设置为当前节点，得到RR红色情况。
3. 按照RR红色情况处理（1.变颜色 2.左旋PP）。

新插入节点，为其父节点的右子节点（RR红色情况）

处理：

1. 变颜色：将P设置为黑色，将PP设置为红色。
2. 对PP节点进行左旋。

(2) 总结：

    /**
     * 插入后修复红黑树平衡的方法
     * |---情景1：红黑树为空树
     *              处理：直接把插入结点作为根结点并设为黑节点。
     * |---情景2：插入节点的父节点为黑色
     *              处理：直接插入即可。
     * |---情景3：插入节点的父节点为红色，祖父节点肯定为黑色
     * |---情景3.1：插入节点的父节点为祖父节点的左子节点
     * |---情景3.1.1：叔叔节点存在，并且为红色（父-叔 双红）
     *                处理：父亲和叔叔节点改为黑色，爷爷节点改为红色，将爷爷节点设为当前节点继续平衡处理。
     * |---情景3.1.2：叔叔节点不存在或者为黑色节点
  
     * |---情景3.1.2.1：插入节点为其父节点的右子节点（LR情况）
     *                  处理：对父亲节点进行左旋，得到LL情况，按照LL情况继续处理。
     * |---情景3.1.2.2：插入节点为其父节点的左子节点（LL情况）
     *                  处理：父亲节点改为黑色，爷爷节点改为红色，对爷爷节点进行右旋
     * |---情景3.2：插入节点的父节点为祖父节点的右子节点
     * |---情景3.2.1：叔叔节点存在，并且为红色（父-叔 双红）
     *                处理：父亲和叔叔节点改为黑色，爷爷节点改为红色，将爷爷节点设为当前节点继续平衡处理。
     * |---情景3.2.2：叔叔节点不存在或者为黑色节点
     * |---情景3.2.2.1：插入节点为其父节点的左子节点（RL情况）
     *                  处理：对父亲节点进行右旋，得到RR情况，按照RR情况继续处理。
     * |---情景3.2.2.2：插入节点为其父节点的右子节点（RR情况）
     *                  处理：父亲节点改为黑色，爷爷节点改为红色，对爷爷节点进行左旋
     */

4. 二叉树的删除

删除操作流程：

1. 首先删除删除节点的链表结构的引用
2. 删除删除节点的树结构引用
   1. 删除节点左右子树都不为null，那么找到删除节点右子树的最小值节点，并将两者替换（颜色也要换）。用replacement记录删除节点的可替换节点，如果没有记录删除节点。
   2. 删除节点的右子树为null，用replacement记录左子树。
   3. 删除节点的左子树为null，用replacement记录右子树。
   4. 删除节点的左右子树都为null，用replacement记录删除节点，表示没有可替换节点
   5. replacement不等于删除节点说明删除节点有子树，那么将删除节点的子树替换删除节点，除去删除节点的引用。
   6. 然后在判断如果删除节点是黑节点，那么需要执行balanceDeletion(root，replacement)方法，自平衡操作。
   7. replacement等于删除节点，说明删除节点没有子树，那么直接从父节点掉对删除节点的引用。不需要平衡。

注意：1，2，3，4只会执行一个，5，6，7是顺序执行，5，7也只执行一个。

4.1 removeTreeNode()

/**
         * Removes the given node, that must be present before this call.
         * This is messier than typical red-black deletion code because we
         * cannot swap the contents of an interior node with a leaf
         * successor that is pinned by "next" pointers that are accessible
         * independently during traversal. So instead we swap the tree
         * linkages. If the current tree appears to have too few nodes,
         * the bin is converted back to a plain bin. (The test triggers
         * somewhere between 2 and 6 nodes, depending on tree structure).
         * 先查找到树节点之后，然后删除一个树节点 删除节点调用的该方法，删除节点就是当前节点
         * @param map this,就是当前的map
         * @param tab 散列表数组
         * @param movable
         */
        //首先从链表结构中解除删除节点的引用，然后从树结构中删除节点的引用
        final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                  boolean movable) {
            //================================删除链表中的引用=========================
            // n： table数组的长度
            int n;
            if (tab == null || (n = tab.length) == 0)
                return;
            // index 删除节点在数组中的索引
            int index = (n - 1) & hash;
            // first，root： 要删除节点所在桶位置的头节点，即树的根节点
            // rl： 根节点的左节点
            TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
            // sunc：要删除节点的下一个节点
            // pred：删除节点的上一个节点
            TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
            // 删除节点的上一个节点是null，说明删除节点是根节点。下面是删除节点的工作。
            if (pred == null)
                // 将删除节点的下一个节点放到桶的第一个位置，作为头节点
                tab[index] = first = succ;
            else
                // 删除节点的上一个节点指向删除节点的下一个节点，将删除节点踢出。
                pred.next = succ;
            if (succ != null)
                // 删除节点的下一个节点认自己的上级。与上一行代码相互指向
                succ.prev = pred;
            // 删除掉删除节点的工作已经完成
            // 头节点为null，说明树没有节点了，直接返回。
            if (first == null)
                return;
            // root指向根节点。
            if (root.parent != null)
                root = root.root();
            // 判断树是否需要退化
            if (root == null || root.right == null ||
                (rl = root.left) == null || rl.left == null) {
                // 说明树中的节点只有0或2或3个，那么需要从树退化链表。
                // untreeify()方法，返回Node节点，将TreeNode节点替换为Node
                tab[index] = first.untreeify(map);  // too small
                return;
            }
            //==============================删除节点在树中的引用===========================
            // p: 当前删除节点
            // replacement: 替换掉删除节点的节点
            TreeNode<K,V> p = this, pl = left, pr = right, replacement;
            // 情景1：删除节点的左右子树都不为null，这种情况将右子树的最小节点与删除节点交换
            if (pl != null && pr != null) {
                // s: 删除节点的右节点，sl：s.left
                TreeNode<K,V> s = pr, sl;
                // 找到右子树的最小子节点
                while ((sl = s.left) != null) // find successor
                    s = sl;
                // 让删除节点和右子树的最小值节点交换颜色
                boolean c = s.red; s.red = p.red; p.red = c; // swap colors
                // sr: 右树最小值节点的右节点，
                // pp: 删除节点的父节点
                TreeNode<K,V> sr = s.right;
                TreeNode<K,V> pp = p.parent;
                if (s == pr) { // p was s's direct parent
                    //删除节点作为s的右子节点
                    p.parent = s;
                    s.right = p;
                }
                else {
                    TreeNode<K,V> sp = s.parent;
                    if ((p.parent = sp) != null) {
                        if (s == sp.left)
                            sp.left = p;
                        else
                            sp.right = p;
                    }
                    if ((s.right = pr) != null)
                        pr.parent = s;
                }
                // 右子树的最小子节点的值来替换删除节点，那么删除节点的左节点一定为空。
                p.left = null;
                // 将右子树最小子节点的右子树赋值给删除节点
                if ((p.right = sr) != null)
                    sr.parent = p;
                // 将删除节点的左子树赋值给右子树的最小节点
                if ((s.left = pl) != null)
                    pl.parent = s;
                // 将删除节点赋值给右子树的最小节点
                if ((s.parent = pp) == null)
                    root = s;
                else if (p == pp.left)
                    pp.left = s;
                else
                    pp.right = s;
                // 这里判读和下面判断pl，pr 是否为null相同，找到可以替换删除节点的节点
                if (sr != null)
                    replacement = sr;
                else
                    replacement = p;
            }
            // 情景2：删除节点左子节点或右子节点为null，找到可以替换删除节点的节点
            else if (pl != null)
                replacement = pl;
            else if (pr != null)
                replacement = pr;
            else
                replacement = p;
            // replacement != p 说明删除节点p只有一个子节点。replacement就是可以替换掉删除节点的子节点
            if (replacement != p) {
                // 那么直接让将删除节点替换。
                TreeNode<K,V> pp = replacement.parent = p.parent;
                if (pp == null)
                    root = replacement;
                else if (p == pp.left)
                    pp.left = replacement;
                else
                    pp.right = replacement;
                p.left = p.right = p.parent = null;
            }
            // 如果删除节点是黑节点，那么需要删除节点自平衡。
            TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
            // 下面条件说明 删除节点p 没有子节点。
            if (replacement == p) {  // detach
                // 使删除节点的父节点对删除节点的指针改为null
                TreeNode<K,V> pp = p.parent;
                p.parent = null;
                if (pp != null) {
                    if (p == pp.left)
                        pp.left = null;
                    else if (p == pp.right)
                        pp.right = null;
                }
            }
            if (movable)
                moveRootToFront(tab, r);
        }

4.2balanceDeletion()

删除节点之后的自平衡操作。就是左旋，右旋，变色操作。

/**
         * 删除节点之后的自平衡操作，执行这个方法，那么删除节点一定是黑色节点。
         * @param root 树的根节点
         * @param x 删除节点或者是删除节点的替换节点。需要自平衡
         * @return
         */
        static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                                   TreeNode<K,V> x) {
            // xp: x的父节点
            for (TreeNode<K,V> xp, xpl, xpr;;)  {
                // x是根节点
                if (x == null || x == root)
                    return root;
                //x的父节点是根节点
                else if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                // x是红色，那么在x有替换节点的情况下，说明删除节点是黑色，替换节点需要变成黑色。
                else if (x.red) {
                    x.red = false;
                    return root;
                }
                // x是父节点的左子节点并且是黑色。那么x的父节点是红色。
                else if ((xpl = xp.left) == x) {
                    // x的兄弟节点存在并且是红色，此时情况就是 xp ： x ：xpr = 黑：黑：红色，所以不满足红黑树
                    if ((xpr = xp.right) != null && xpr.red) {
                        // x兄弟节点=黑色，父节点=红色，此时情况就是 红：黑：黑 满足
                        xpr.red = false;
                        xp.red = true;
                        //然后对父节点左旋
                        root = rotateLeft(root, xp);
                        xpr = (xp = x.parent) == null ? null : xp.right;
                    }
                    if (xpr == null)
                        x = xp;
                    else {
                        TreeNode<K,V> sl = xpr.left, sr = xpr.right;
                        if ((sr == null || !sr.red) &&
                            (sl == null || !sl.red)) {
                            xpr.red = true;
                            x = xp;
                        }
                        else {
                            if (sr == null || !sr.red) {
                                if (sl != null)
                                    sl.red = false;
                                xpr.red = true;
                                root = rotateRight(root, xpr);
                                xpr = (xp = x.parent) == null ?
                                    null : xp.right;
                            }
                            if (xpr != null) {
                                xpr.red = (xp == null) ? false : xp.red;
                                if ((sr = xpr.right) != null)
                                    sr.red = false;
                            }
                            if (xp != null) {
                                xp.red = false;
                                root = rotateLeft(root, xp);
                            }
                            x = root;
                        }
                    }
                }
                else { // symmetric
                    if (xpl != null && xpl.red) {
                        xpl.red = false;
                        xp.red = true;
                        root = rotateRight(root, xp);
                        xpl = (xp = x.parent) == null ? null : xp.left;
                    }
                    if (xpl == null)
                        x = xp;
                    else {
                        TreeNode<K,V> sl = xpl.left, sr = xpl.right;
                        if ((sl == null || !sl.red) &&
                            (sr == null || !sr.red)) {
                            xpl.red = true;
                            x = xp;
                        }
                        else {
                            if (sl == null || !sl.red) {
                                if (sr != null)
                                    sr.red = false;
                                xpl.red = true;
                                root = rotateLeft(root, xpl);
                                xpl = (xp = x.parent) == null ?
                                    null : xp.left;
                            }
                            if (xpl != null) {
                                xpl.red = (xp == null) ? false : xp.red;
                                if ((sl = xpl.left) != null)
                                    sl.red = false;
                            }
                            if (xp != null) {
                                xp.red = false;
                                root = rotateRight(root, xp);
                            }
                            x = root;
                        }
                    }
                }
            }
        }

看不下去了😭

情景1：节点的左子树、右子树都不为null

针对这种情况，通常为了简化操作，都会采用左子树的最大子节点或者右子树的最小子节点的值来替换当前节点的值，然后删除左子树的最大子节点或右子树的最小子节点，替换后需要删除的节点的可能情况为其他三种。

情景2：节点的左子树为null、右子树不为null 或者 右子树为null，左子树不为null

以下情景以左null右非null为例：

情景2.1：需要删除的节点为红色节点

根据红黑树的性质，其右子节点不可能为红色（违反性质4），不可能出现右子节点是黑色节点的情况（违反性质五）；所以右子节点只可能是NIL，直接删除该节点即可。

情景2.2：需要删除的节点为黑色节点

根据红黑树的性质，其右子节点要么就是NIL,要么是红色节点，且该红色节点的两个子节点为NIL。

1. 如果右子节点为NIL则符合左右子树都为null的情景，详见情景3解析；
2. 如果右子节点为红色，则把右子节点变成黑色并顶替该节点即可。

情景3：两个子树均为null

以下情景以该节点为父节点的左子节点为例：

情景3.1：需要删除的节点为红色节点

直接删除该节点即可。

情景3.2：需要删除的节点为黑色节点

因为该节点为黑色节点，删除该节点会导致该路径上的黑色节点数量 -1，并且因为没有子节点，根本无法通过子树内部修正路径；所以得考虑从该节点的兄弟节点处入手，让他匀一个黑色节点过来，因为该节点为黑色节点，所以其兄弟节点必然存在（性质5.1）且可能是红色节点，也可能是黑色节点。

情景3.2.1：该节点的兄弟节点为红色

他们的父节点一定是黑色节点。

处理：

1. 将兄弟节点变为黑色，父亲节点变为红色
2. 如果该节点为父节点的左子节点，则对父节点进行左旋处理，反之则进行右旋处理。

此时情景转化为3.2.2。

-->

情景3.2.2：该节点的兄弟节点为黑色

他们的父节点则颜色不定。

情景3.2.2.1：该节点的远侄子节点为红色且该节点为父节点的左子节点

没有上色的节点表示黑色红色均可，注意如果SL为黑色，则SL必为NULL节点。

处理：

1. 将P和S的颜色对调。
2. 对P节点进行左旋处理。
3. 把SR节点变成黑色，并删除D即可。

-->

情景3.2.2.2：该节点的远侄子节点为红色且该节点为父节点的右子节点

处理：

1. 将P和S的颜色对调。
2. 对P节点进行右旋处理。
3. 把SL节点变成黑色，并删除D即可

-->

情景3.2.2.3：远侄子节点为黑色，近侄子节点为红色，该节点为父亲节点的左孩子

处理：

1. SL节点颜色设为P节点颜色。
2. 将P节点颜色设为黑色。
3. 将S节点右旋。
4. 将P节点左旋。

情景3.2.2.4：远侄子节点为黑色，近侄子节点为红色，该节点为父亲节点的右孩子

处理：

1. SR节点颜色设为P节点颜色。
2. 将P节点颜色设为黑色。
3. 将S节点左旋。
4. 将P节点右旋。

-

情景3.2.3：父亲节p为红色，兄弟节点和兄弟节点的两个孩子（只能是NULL节点）都为黑色

处理：

1. 将父亲节点P改成黑色，将兄弟节点S改成红色。
2. 然后删除D即可。

-->

情景3.2.4：父亲节点p，兄弟节点s和兄弟节点的两个孩子（只能为NULL节点）都为黑色

处理：

1. 将兄弟节点S的颜色改成红色。
2. 然后删除D。
3. 以P为起始节点继续进行自平衡操作。

-->

总结：

/**
     * 删除红黑树自平衡方法
     *
     * |---情景1：左右子树均不为空
     *              处理：寻找后继节点进行替换操作，更新待平衡节点为替换后的节点。
     * |---情景2. 左右子树有一个为空
     * |---情景2.1：需要删除的节点为红色节点
     *                处理：直接删除。
     * |---情景2.2：需要删除的节点为黑色节点
     *                处理：如果一个子节点为红色，则把子节点变成黑色并替换该节点，删除替换后的节点。
     * |---情景3：两个子树均为null
     * |---情景3.1：需要删除的节点为红色节点
     *                处理：直接删除。
     * |---情景3.2：需要删除的节点为黑色节点
     * |---情景3.2.1：该节点的兄弟节点为红色
     *                  处理：将兄弟节点变为黑色，父亲节点变为红色，
     *                        若该节点为父节点的左子节点，则对父节点进行左旋处理，反之则进行右旋处理
     *                        此时情景转化为3.2.2。
     * |---情景3.2.2：该节点的兄弟节点为黑色
     * |---情景3.2.2.1：该节点的远侄子节点为红色且该节点为父节点的左子节点
     *                    处理：将父节点和兄弟节点的颜色对调。
     *                          对父节点进行左旋处理。
     *                          把远侄子节点变成黑色，并删除目标节点即可。
     * |---情景3.2.2.2：该节点的远侄子节点为红色且该节点为父节点的右子节点
     *                    处理：将父节点和兄弟节点的颜色对调。
     *                          对父节点进行右旋处理。
     *                          把远侄子节点变成黑色，并删除目标节点即可。
     * |---情景3.2.2.3：远侄子节点为黑色，近侄子节点为红色，该节点为父亲节点的左孩子
     *                    处理：将近侄子节点颜色设为父节点颜色。
     *                          将父节点颜色设为黑色。
     *                          将兄弟节点右旋。
     *                          将父节点节点左旋。
     * |---情景3.2.2.4：远侄子节点为黑色，近侄子节点为红色，该节点为父亲节点的右孩子
     *                    处理：将近侄子节点颜色设为父节点颜色。
     *                          将父节点颜色设为黑色。
     *                          将兄弟节点左旋。
     *                          将父节点节点右旋。
     * |---情景3.2.3：父亲节为红色，兄弟节点和兄弟节点的两个孩子（只能是NULL节点）都为黑色
     *                  处理：将父节点改成黑色，将兄弟节点改成红色。
     *                        然后删除目标节点即可。
     * |---情景3.2.4：父亲节点，兄弟节点和兄弟节点的两个孩子（只能为NULL节点）都为黑色
     *                  处理：将兄弟节点改成红色。
     *                        删除目标节点。
     *                        以父节点为目标节点继续进行自平衡操作
     *
     */

5 红黑树查找

5.1 getTreeNode方法

/**
         * Calls find for root node.
         * @param h 要查找节点的hash值
         * @param k 要查找节点的k
         * @return 找到的节点，不存在返回null
         */
final TreeNode<K,V> getTreeNode(int h, Object k) {
    // 如果当前节点不是根节点，那么先调用root()方法，返回根节点，根节点调用find，从根节点开始查找节点
    return ((parent != null) ? root() : this).find(h, k, null);
}

5.2 find()

/**
         * Finds the node starting at root p with the given hash and key.
         * The kc argument caches comparableClassFor(key) upon first use
         * comparing keys.
         * 从一个桶为的头节点开始查找，即从树的根开始
         * @param h
         * @param k
         * @param kc 如果key是Comparable接口的实现，那么可以通过比较器比较
         * @return 找到了返回节点，找不到返回null
         */
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    // p: 树的根节点
    TreeNode<K,V> p = this;
    // 遍历树，查找节点，找到后返回
    do {
        int ph, dir; K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        if ((ph = p.hash) > h)
            p = pl;
        else if (ph < h)
            p = pr;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if (pl == null)
            p = pr;
        else if (pr == null)
            p = pl;
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr;
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
            p = pl;
    } while (p != null);
    return null;
}

6 实现HashMap

使用数组+红黑树实现HashMap

class MyHashMap {
    private static class TreeNode {
        private int key;
        private int value;
        private boolean color;
        private TreeNode left;
        private TreeNode right;
        private TreeNode parent;

        private TreeNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private static final boolean RED = false;
    private static final boolean BLACK = true;
    private TreeNode[] hashtable = new TreeNode[1024];
    private int currentSize;

    public void put(int key, int value) {
        if (currentSize >= hashtable.length) {
            resize(); // 从结果来看，加载因子选 1.0 效率较高。
        }
        int index = key & (hashtable.length - 1);
        insert(index, new TreeNode(key, value));
    }

    public int get(int key) {
        int index = key & (hashtable.length - 1);
        TreeNode node = getNode(index, key);
        return node == null ? -1 : node.value;
    }

    public void remove(int key) {
        int index = key & (hashtable.length - 1);
        delete(index, key);
    }

    /**
     * 对哈希表进行扩容。
     */
    private void resize() {
        TreeNode[] oldTable = hashtable;
        hashtable = new TreeNode[hashtable.length << 1];
        for (TreeNode root : oldTable) {
            postorderTraversal(root);
        }
        currentSize >>= 1;
    }

    /**
     * 获取指定位置上的指定结点。
     * @param index
     * @param key
     * @return
     */
    private TreeNode getNode(int index, int key) {
        TreeNode current = hashtable[index];
        while (current != null) {
            if (current.key == key) {
                break;
            }
            if (current.key < key) {
                current = current.right;
            } else {
                current = current.left;
            }
        }
        return current;
    }

    /**
     * 在指定位置上插入结点。
     * @param index
     * @param insert
     */
    private void insert(int index, TreeNode insert) {
        TreeNode current = hashtable[index], parent = null; // 分别保存当前结点及其父结点。
        while (current != null) {
            parent = current;
            if (current.key == insert.key) {
                current.value = insert.value;
                return;
            }
            if (current.key < insert.key) {
                current = current.right;
            } else {
                current = current.left;
            }
        }
        insert.parent = parent;
        if (parent == null) {
            hashtable[index] = insert;
        } else if (parent.key < insert.key) {
            parent.right = insert;
        } else {
            parent.left = insert;
        }
        currentSize++;
        fixAfterInsertion(index, insert);
    }

    /**
     * 删除指定位置上的指定结点。
     * @param index
     * @param key
     */
    private void delete(int index, int key) {
        TreeNode delete = getNode(index, key);
        if (delete == null) {
            return;
        }
        if (delete.left != null && delete.right != null) {
            TreeNode successor = delete.right;
            while (successor.left != null) {
                successor = successor.left;
            }
            delete.key = successor.key;
            delete.value = successor.value;
            delete = successor;
        }
        TreeNode replacement = delete.left == null ? delete.right : delete.left;
        if (replacement == null) {
            fixAfterDeletion(index, delete);
            if (delete.parent == null) {
                hashtable[index] = null;
            } else if (delete.parent.left == delete) {
                delete.parent.left = null;
            } else {
                delete.parent.right = null;
            }
        } else { // 被删除的结点只有一个子结点，那它一定是黑色结点，且它的子结点为红色。
            replacement.parent = delete.parent;
            if (delete.parent == null) {
                hashtable[index] = replacement;
            } else if (delete.parent.left == delete) {
                delete.parent.left = replacement;
            } else {
                delete.parent.right = replacement;
            }
            replacement.color = BLACK;
        }
        currentSize--;
    }

    /**
     * 对插入后的结点进行调整。
     *
     * @param index
     * @param insert
     */
    private void fixAfterInsertion(int index, TreeNode insert) {
        // 只有父结点是红色才进行处理。
        while (colorOf(insert.parent) == RED) {
            // 分别保存当前结点的父结点、叔父结点、祖父结点。
            TreeNode parent = insert.parent, uncle = sibling(parent), grand = parent.parent;
            // 不管是哪种情况，祖父结点都需要染成红色。
            grand.color = RED;
            if (colorOf(uncle) == BLACK) { // 叔父结点为黑色。
                if (grand.left == parent) {
                    if (parent.right == insert) {
                        rotationLeft(index, parent); // LR 情况：先对父结点进行左旋转。
                        parent = insert;
                    }
                    rotationRight(index, grand); // LL 情况：对祖父结点进行右旋转。
                } else {
                    if (parent.left == insert) {
                        rotationRight(index, parent); // RL 情况：先对父结点进行右旋转。
                        parent = insert;
                    }
                    rotationLeft(index, grand); // RR 情况：对祖父结点进行左旋转。
                }
                parent.color = BLACK; // 将旋转后的中心结点染成黑色。
                insert = hashtable[index]; // 处理完直接退出循环。
            } else { // 叔父结点为红色，则将父结点与叔父结点都染成黑色，将祖父结点作为新插入的结点继续处理。
                uncle.color = BLACK;
                parent.color = BLACK;
                insert = grand;
            }
        }
        hashtable[index].color = BLACK; // 根结点必须是黑色。
    }

    /**
     * 对删除后的结点进行调整。
     * @param index
     * @param delete
     */
    private void fixAfterDeletion(int index, TreeNode delete) {
        while (delete.parent != null && delete.color == BLACK) { // 只有删除的是黑色结点才进行处理。
            // 分别保存当前结点的父结点、兄弟结点。
            TreeNode parent = delete.parent, sibling = sibling(delete);
            if (sibling.color == BLACK) { // 兄弟结点是黑色。
                if (colorOf(sibling.left) == BLACK && colorOf(sibling.right) == BLACK) { // 兄弟结点没有红色子结点。
                    if (parent.color == BLACK) {
                        delete = parent;
                    }
                    parent.color = BLACK;
                    sibling.color = RED;
                } else { // 兄弟结点有红色子结点。
                    if (parent.left == sibling) {
                        if (colorOf(sibling.left) == BLACK) {
                            rotationLeft(index, sibling); // LR 情况：先对兄弟结点进行左旋转。
                            sibling = sibling.parent;
                        }
                        rotationRight(index, parent); // LL 情况：对父结点进行右旋转。
                    } else {
                        if (colorOf(sibling.right) == BLACK) {
                            rotationRight(index, sibling); // RL 情况：先对兄弟结点进行右旋转。
                            sibling = sibling.parent;
                        }
                        rotationLeft(index, parent); // RR 情况：对父结点进行左旋转。
                    }
                    sibling.color = parent.color; // 旋转后中心结点继承父结点的颜色。
                    sibling.left.color = BLACK;
                    sibling.right.color = BLACK;
                    delete = hashtable[index]; // 处理完直接退出循环。
                }
            } else { // 兄弟结点是红色。
                if (parent.left == sibling) {
                    rotationRight(index, parent);
                } else {
                    rotationLeft(index, parent);
                }
                parent.color = RED;
                sibling.color = BLACK;
            }
        }
    }

    /**
     * 获取指定结点的兄弟结点。
     * @param node
     * @return
     */
    private TreeNode sibling(TreeNode node) {
        if (node.parent.left == node) {
            return node.parent.right;
        }
        return node.parent.left;
    }

    /**
     * 对指定位置上的指定结点进行左旋转。
     * 以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，
     * 右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。
     * @param index 桶位置
     * @param node 旋转节点
     */
    private void rotationLeft(int index, TreeNode node) {
        TreeNode newRoot = node.right; // 结点的右子结点会成为这颗子树的根结点。
        node.right = newRoot.left;
        if (newRoot.left != null) {
            newRoot.left.parent = node;
        }
        newRoot.left = node;
        newRoot.parent = node.parent;
        if (node.parent == null) {
            hashtable[index] = newRoot;
        } else if (node.parent.left == node) {
            node.parent.left = newRoot;
        } else {
            node.parent.right = newRoot;
        }
        node.parent = newRoot;
    }

    /**
     * 对指定位置上的指定结点进行右旋转。
     * 以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，
     * 左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。
     * @param index 桶位置
     * @param node 旋转节点
     */
    private void rotationRight(int index, TreeNode node) {
        TreeNode newRoot = node.left; // 结点的左子结点会成为这颗子树的根结点。
        node.left = newRoot.right;
        if (newRoot.right != null) {
            newRoot.right.parent = node;
        }
        newRoot.right = node;
        newRoot.parent = node.parent;
        if (node.parent == null) {
            hashtable[index] = newRoot;
        } else if (node.parent.left == node) {
            node.parent.left = newRoot;
        } else {
            node.parent.right = newRoot;
        }
        node.parent = newRoot;
    }

    /**
     *  获取指定结点的颜色。
     * @param node
     * @return
     */
    private boolean colorOf(TreeNode node) {
        return node == null || node.color;
    }

    /**
     * 对结点进行后序遍历。
     * @param node
     */
    private void postorderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        node.left = node.right = node.parent = null;
        node.color = RED;
        int index = node.key & (hashtable.length - 1);
        insert(index, node);
    }
}