概述

二叉搜索树是优化搜索效率最常用的数据结构，时间复杂度为O(h)，其中h是树的高度。可以看出，树的高度是影响搜索效率的关键因素。在树退化为一个链表(节点都在左或都在右)，搜索效率也就退化为O(n)。为了防止这种情况的出现平衡二叉搜索树出现，本文所介绍的红黑树就是一种特殊的"平衡"二叉树，因为红黑树只能保证没有一条路径会比其他路径长出2倍，所以并不是严格意义上的平衡树。但是这个性质却能保证最坏情况下搜索操作的复杂度是O(h)。

定义及性质

红黑树每个节点包含color，key，left，right和p，如果一个节点没有子节点或者父节点，那么该节点响应指针的属性值为NIL，我们将NIL视为指向也节点的指针。一个红黑树必须满足一下性质：
(1) 每个节点只能是红色或者黑色；
(2) 根节点是黑色；
(3) 每个叶节点（NIL）是黑色；
(4) 红节点的子节点一定是黑色；
(5) 对于每个节点，从该节点到到期所有后代也节点的路径上，均包含相同数目的黑节点。

插入操作

红黑树的插入操作和一般的二叉搜索树一样，但是插入节点后需要进行调整，以满足红黑树的以上五个性质。我们知道JDK8中的HashMap和ConcurrentHashMap在桶中链表长度大于等于8时会将链表转换为红黑树以提高搜索效率，下面我们通过这块代码来了解下具体调整算法。下面代码涉及两个操作：左旋和右旋，大家可以认为对x节点左旋就是用x节点的右子节点y代替x，并且x成为y的左子节点；对x节点进行右旋就是用x的左子节点y代替x并且x成y的右子节点。

左旋右旋.png

static <K,V> ConcurrentHashMap.TreeNode<K,V> balanceInsertion(ConcurrentHashMap.TreeNode<K,V> root,
                                                                  ConcurrentHashMap.TreeNode<K,V> x) {
        //1.所有新插入的节点颜色都是红色
        x.red = true;
        for (ConcurrentHashMap.TreeNode<K,V> xp, xpp, xppl, xppr;;) {
            //如果节点是根节点，那么直接将该节点置为黑色，结束
            if ((xp = x.parent) == null) {
                x.red = false;
                return x;
            }
            //如果x的父节点是黑色，符合红黑树定义直接返回。
            else if (!xp.red || (xpp = xp.parent) == null)
                return root;
            //2.插入的节点x的父节点是红色并且是左子树
            if (xp == (xppl = xpp.left)) {
                //2.1查看x的叔叔节点的颜色，如果是红色，那么将x的父节点，叔节点置为黑色，爷爷节点置为红色，并将要调整的节点置为爷爷节点
                if ((xppr = xpp.right) != null && xppr.red) {
                    xppr.red = false;
                    xp.red = false;
                    xpp.red = true;
                    x = xpp;
                }
                else {
                  //2.2 x节点的叔叔节点是黑色，且x是右子树，那么将x的父节点进行右旋
                    if (x == xp.right) {
                        root = rotateLeft(root, x = xp);
                        xpp = (xp = x.parent) == null ? null : xp.parent;
                    }
                  //2.3 x节点的叔叔节点是黑色，且x是左子树，将父节点置为黑色，爷爷节点置为红色并将爷爷节点进行右旋
                    if (xp != null) {
                        xp.red = false;
                        if (xpp != null) {
                            xpp.red = true;
                            root = rotateRight(root, xpp);
                        }
                    }
                }
            }
           //3.插入节点x父节点是红色并且是右子树，处理过程与情况2相同
            else {
                if (xppl != null && xppl.red) {
                    xppl.red = false;
                    xp.red = false;
                    xpp.red = true;
                    x = xpp;
                }
                else {
                    if (x == xp.left) {
                        root = rotateRight(root, x = xp);
                        xpp = (xp = x.parent) == null ? null : xp.parent;
                    }
                    if (xp != null) {
                        xp.red = false;
                        if (xpp != null) {
                            xpp.red = true;
                            root = rotateLeft(root, xpp);
                        }
                    }
                }
            }
        }
    }

删除操作

相对于红黑树的插入操作，删除操作比较麻烦，我们按照被删除节点x的颜色和x的子节点情况分类如下。为了更容易理解在有的情况下我们给出了操作图，红色代表红节点，黑色代表黑节点，白色代表不知道该节点是红还是黑，并且为了简化图示我们没有将NIL节点画出，大家可以认为所有页节点都隐含一个黑色节点NIL。
(1) x为红色并且x没有子节点
这种情况下较为简单，直接删除x不会破坏红黑树上述五个限制。
(2) x为红色并且x有一个子节点
这种情况实际是不存在的，因为如果x是红色，其子节点必定是黑色，而左右子树的黑高就不相等。
(3) x为黑色并且x有一个子节点
这种情况下，x的这个子节点y必定是红色，因此只需要将y替换为x并且将y置为黑色即可。具体如下图：

image

(4) x为红色并且x有两个子节点

这种情况下，可以找到x节点的后继节点s，s的情况可能有以下两种：

image 删除x时可以用s替换为x，并将s的颜色设置为x的颜色。此时删除x相当于删除s。如果s没有子节点则这种情况转换为(1)或者(6)，如果s有子节点，这种情况转换为(2)或者(3)。我们以比较负责的情况x的后继节点有一个子孩子并且s为黑色为例给出删除示例： image

(5) x为黑色并且x有两个子节点

这种情况同(4)的处理机制一样。

(6) x为黑色并且x没有子节点

这种情况比较复杂，因为删除黑节点会破坏黑高。可以分为如下几种情况讨论：

(a). x节点的兄弟节点b有一个与其方向一致的红色子节点s

此时将父节点进行旋转，并将删除节点的黑色转移到父节点，而父节点原来位置的颜色保持不变。

image

(b). x节点的兄弟节点b有一个与其方向不一致的红色节点s

此时首先通过旋转操作转为情况(a)，再按照(a)进行处理。

image

(c) 兄弟节点为黑色，且兄弟节点无红色子节点

如果父节点是红色，那么将父节点置为黑色，兄弟节点置为红色即可解决问题。

image

如果父节点是黑色，那么确实没有红节点可以作为黑节点转移的节点，只能对兄弟节点重新设置颜色，已平衡被删除节点侧减小的黑高，并即将节点一直上移知道根节点使得所有的路径的黑高都减1。

(d) 兄弟节点为红色

这种情况可以通过旋转父节点，转换为父节点为红色，兄弟节点为黑色的情况处理。

从以上的删除过程可以看出，如果删除节点是红色节点，不会破会黑高，可以直接删除。如果删除的节点是黑色节点，并且删除的节点的父节点或者兄弟节点，兄弟节点的子节点存在红色节点，那么可以通过旋转操作即将红色节点旋转到被删除节点侧并置为黑色保持黑高不改变。如果以上节点都不存在红色节点，那么只能向上回溯整个树的黑高整体减一。

原文

袁琼琼的技术博客，欢迎指针
https://yuanqiongqiong.cn/2019/06/09/%E7%BA%A2%E9%BB%91%E6%A0%91/