前言介绍

红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。

那么为什么刚开始叫平衡二叉B树呢？这里拆成两个概念： “二叉平衡” 和 “B树”

说到二叉平衡，我们不得不先了解一下AVL（平衡二叉树）
而红黑树明明是一种二叉树，怎么又会和B树扯上关系呢？其实红黑树确实和234树（四阶B树）有着千丝万缕的联系。可以说红黑树是234树的一种实现（以二叉树的表现形式）

为了让大家对红黑树有更好的理解，接下来我会先简单介绍一下AVL（平衡二叉树）和234树，最后再对比它们讲解红黑树。

AVL树的简单介绍

为什么需要AVL树？

AVL树其实就是一棵特殊的二叉树，为什么会出现AVL树，AVL树比普通二叉树优势在什么地方呢？

我们知道，一棵普通的二叉搜索树（既二叉排序树，不了解二叉排序树的可以看这篇文章【二叉排序树BST】），以其特殊的性质（左<根<右），中序遍历将得到有序的序列，同时在搜索目标值时可以根据其性质加快搜索，但数据如果有序或接近有序，二叉搜索树会退化成为单支树，查找目标值，相当于在顺序表中查找，时间复杂度从O(lgn)退化到O(n)

例如： 如果顺序插入1 、2 、3 、4 、5 、6几个数字
插入后的结果为：

AVL树为了避免上述问题的出现，规定其性质：

必须是一棵二叉排序树
每个节点的左子树和右子树的高度差的绝对值不能大于1
平衡因子

性质：

判断对应二叉树是否平衡的一个整型值
平衡因子 = 右子树的层数 - 左子树的层数

以下面这棵树为例：

AVL树的调整过程

为了保证AVL树的平衡，在插入节点时，若出现不平衡的情况，则要根据新插入的节点与最低不平衡节点的位置关系进行相应的调整。分为LL型、RR型、LR型和RL型四种类型，各调整方法如下

LL调整：

RR调整：

LR调整：

RL调整：

AVL树的缺点

最大的缺点就是追求完美的平衡导致插入和删除需要大量的平衡调整，这个在插入和删除大的情况导致开销较大，这个时候我们就想着，有没有一种树，解决BST的缺点，同时又不要大量的计算平衡，于是RB-Tree（红黑树）就被发明了

红黑树与AVL相比

红黑树不追求“完美平衡”，红黑树分红、黑两种节点，它追求的是“黑色节点完美平衡”
插入节点导致树失衡，AVL和RB-Tree都是最多两次树旋转来实现复衡rebalance，旋转的量级是O(1)
删除节点导致树失衡，AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡，旋转的量级为O(logN)，而RB-Tree最多只需要旋转3次实现复衡，只需O(1)，所以说RB-Tree删除节点的rebalance的效率更高，开销更小！
红黑树的查询性能略微逊色于AVL树，因为红黑树并非保证的完美平衡；红黑树在插入和删除上优于AVL树，相较于AVL树为了维持平衡的开销要小得多

总结：实际应用中，若搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB-T。

234树的简单介绍

234树的概念

2-3-4树是一种阶为4的B树。它是一种自平衡的数据结构，可以保证在O(lgn)的时间内完成查找、插入和删除操作。它主要满足以下性质：

每个节点每个节点有1、2或3个key，分别称为2（孩子）节点，3（孩子）节点，4（孩子）节点
所有叶子节点到根节点的长度一致（也就是说叶子节点都在同一层）
每个节点的key从左到右保持了从小到大的顺序，两个key之间的子树中所有的key一定大于它的父节点的左key，小于父节点的右key

234树的添加操作

首先234树的添加和BST树的添加一样，都是添加在叶子节点上的

如果2-3-4树中已存在当前插入的key，则插入失败，否则最终一定是在叶子节点中进行插入操作
如果待插入的节点不是4节点，那么直接在该节点插入
如果待插入的节点是个4节点，那么应该先分裂该节点然后再插入。一个4节点可以分裂成一个根节点和两个子节点（这三个节点各含一个key）然后在子节点中插入，我们把分裂形成的根节点中的key看成向上层插入的key，然后重复第2步和第3步。
如果是在4节点中进行插入，每次插入会多出一个分支，如果插入操作导致根节点分裂，则2-3-4树会生长一层。因此说2-3-4树(b树)都是自下向上生长的

234树与红黑树的对应关系

2节点 —— 一个黑节点
3节点 —— 黑父红子：左倾和右倾
4节点 —— 黑父两红子

如果一棵树满足红黑树，把红结点收缩到其父结点，就变成了2-3-4树。一棵红黑树对应一棵唯一的234树，但是一棵234树却不能唯一对应一棵红黑树(因为3节点可以对应两种情况：左倾和右倾)。

从上面的对应关系图可以看出，2、3、4节点都分别对应红黑树中的一个黑节点，又因为234树它是一棵绝对平衡的多叉树，因此红黑树是黑色节点绝对平衡的，对整棵树来说是近似平衡的。

红黑树（Red Black Tree）

红黑树的定义

红黑树是每个节点都带有颜色属性的平衡二叉查找树，它的节点分为黑色节点和红色节点。除了二叉排序树的要求以外，对红黑树我们还增加了如下的要求：

1. 节点要么红色要么是黑色
2. 根节点一定是黑色
3. 每个叶子节点都带有两个空的黑色节点（称之为NIL节点，它又被称为黑哨兵）
4. 从每个叶子到根的所有路径上不能有两个连续的红色节点
5. 从任一节点到它所能到达得叶子节点的所有简单路径都包含相同数目的黑色节点
其实记这五个要求我们并不用死记硬背，234树那一节我已经给大家讲解了 2、3、4节点与红黑树节点的对应关系，我们可以根据它们的对应关系来理解这几条规则（建议先记住上面的对应关系）

1、节点要么红色要么黑色：因为红黑树是一个二叉树，而要用一个二叉树来实现一个234树（四阶B树/多叉树），那当然需要一些限制手段，而将节点再加上颜色的概念就是红黑树以二叉树实现234树的基本手段
2、根节点一定是黑色：根据上面2、3、4节点与红黑树节点的对应关系图我们发现，不管是2节点、3节点还是4节点它们对应的红黑树子树的父节点都是黑节点，这样一来红黑树的根节点肯定也就是黑色节点了
4、不能存在连续的红色节点：2、3、4节点对应的几种子树，除了2节点对应一颗黑色节点，3、4节点都是“黑父带黑子”的组合，可以看出是没有连续的红色的
5、任一节点到达叶子节点的路径中包含的黑色节点个数是相同的：2、3、4节点对应的红黑树子树组合中都只包含一颗黑色节点，又因为234树它是一棵完全平衡的多叉树，因此红黑树是黑色节点完全平衡的

上面的叙述只是为了方便大家记忆这几条规则，当然红黑树肯定是先有了规则才会有与2、3、4节点的对应关系

最后说一下黑哨兵的作用：

我们看上面这张图，如果不使用黑哨兵，它完全满足红黑树性质，根结点5到两个叶结点1和叶结点9路径上的黑色结点数都为3个，且没有连续红色节点。
但如果加入黑哨兵后，叶结点的个数变为8个黑哨兵，根结点5到这8个叶结点路径上的黑高度就不一样了，所以它并不是一棵红黑树。

红黑树新增节点的意义

根据上面的介绍，我们都知道红黑树是通过234树演变过来的，为了让我们更深入的理解红黑树添加节点的意义，接下来我分别列举一下，2 、3 、4节点添加元素与红黑树添加的对应关系

新增节点为根节点

新增节点与2节点合并

新增节点与3节点合并

新增节点与4节点合并

插入操作的平衡调整分析

红黑树的平衡调整过程是一个迭代的过程。把正在处理的节点叫作关注节点。关注节点会随着不停地迭代处理，而不断发生变化。最开始的关注节点就是新插入的节点。

红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上
关于插入操作的平衡调整，有这样两种特殊情况：
结合上面图解分析

如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义（情况2-1、2-2、3-1、3-4）
如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了（情况1-1）

除此之外，其他情况都会违背红黑树的定义，需要进行调整，调整的过程包含两种基础的操作：左右旋转和改变颜色。
这里的其他情况就是指插入节点的父节点为红色的情况（3-2、3-3、3-5、3-6、4-1、4-2、4-3、4-4）。一般我们把这些情况再分为三种情况：

一、父亲节点和叔叔节点都是红色（4-1、4-2、4-3、4-4）
二、父亲节点红色，叔叔节点黑色，关注节点与父节点在同一侧（3-2、3-5）
三、父亲节点红色，叔叔节点黑色，关注节点与父节点不在同一侧（3-3、3-6）

这三种情况调整的过程已在上图中演示，后面我会用代码进行实现
备注：我们只需要根据每种情况的特点，不停地调整，就可以让红黑树继续符合定义，也就是继续保持平衡。为了简化描述，把父节点的兄弟节点叫作叔叔节点，父节点的父节点叫作祖父节点。

左旋和右旋

根据红黑树新增节点的分析图我们会发现，红黑树的左旋和右旋操作还是经常用到的，我先专门封装一下这部分代码
左旋：
左旋就是围绕某个节点的左旋，图中的 a，b，r 表示子树，可以为空。

代码实现:

private void rotateLeft(Entry<K, V> p) {
    if (p != null) {
        /*根据X节点拿到Y节点 */
        Entry<K, V> r = p.right;

        // 1、 调整X节点与Y左节点的关系（节点是双向的）
        /* X.right -> Y.left*/
        p.right = r.left;
        /*Y.left.parent -> X*/
        if (r.left != null) {
            r.left.parent = p;
        }

        // 2、 Y节点替换X节点的位置（Y上位了）
        /* Y.parent-> X.parent （Y认X之前的父亲为父亲） */
        r.parent = p.parent;
        
        /* X之前的父亲收Y当新儿子 */
        if (p.parent == null) {
            root = r;
        }
        /*如果p 为左孩子，让他还是成为左孩子 同理*/
        else if (p.parent.left == p) {
            p.parent.left = r;
        } else {
            p.parent.right = r;
        }

        // 3、 调整X与Y的指向关系
        r.left = p;
        p.parent = r;
    }
}

右旋：

代码实现：

private void rotateRight(Entry<K, V> p) {
    if (p != null) {
        Entry<K, V> l = p.left;
        p.left = l.right;
        if (l.right != null) {
            l.right.parent = p;
        }
        l.parent = p.parent;
        if (p.parent == null) {
            root = l;
        } else if (p.parent.right == p) {
            p.parent.right = l;
        } else {
            p.parent.left = l;
        }
        l.right = p;
        p.parent = l;
    }
}

插入操作代码实现

private void insert(RBTreeNode<T> node) {
    int cmp;
    RBTreeNode<T> root = this.rootNode;
    RBTreeNode<T> parent = null;
 
    /*定位节点添加到哪个父节点下*/
    while (null != root) {
        parent = root;
        cmp = node.key.compareTo(root.key);
        if (cmp < 0) {
            root = root.left;
        } else {
            root = root.right;
        }
    }
 
    node.parent = parent;
    /*表示当前没一个节点，那么就当新增的节点为根节点*/
    if (null == parent) {
        this.rootNode = node;
    } else {
        //找出在当前父节点下新增节点的位置
        cmp = node.key.compareTo(parent.key);
        if (cmp < 0) {
            parent.left = node;
        } else {
            parent.right = node;
        }
    }
 
    /*设置插入节点的颜色为红色*/
    node.color = COLOR_RED;
 
    /*修正为红黑树*/
    insertFixUp(node);
}
 
/** * 功能描述：红黑树插入修正 */
private void insertFixUp(RBTreeNode<T> node) {
    RBTreeNode<T> parent, gparent;
    /*节点的父节点存在并且为红色（其他情况都不需要调整）*/
    while (((parent = getParent(node)) != null) && isRed(parent)) {
        gparent = getParent(parent);
 
        /* 若父节点是祖父节点的左孩子*/
        if (parent == gparent.left) {
            RBTreeNode<T> uncle = gparent.right;
            // 【插入操作的平衡调整分析】分析的 第一种情况
            if ((null != uncle) && isRed(uncle)) { 
                setColorBlack(uncle);
                setColorBlack(parent);
                setColorRed(gparent);
                node = gparent;
                continue;
            }
 			// 【插入操作的平衡调整分析】分析的 第二种情况中的上半部分（关注节点与父节点不同侧 转变成 关注节点与父节点同侧）
            if (parent.right == node) {
                RBTreeNode<T> tmp;
                leftRotate(parent);
                tmp = parent;
                parent = node;
                node = tmp;
            }
            // 【插入操作的平衡调整分析】分析的 第二种情况的下半部分 以及 第三种情况的全部
            setColorBlack(parent);
            setColorRed(gparent);
            rightRotate(gparent);
        } else {	// 若父节点是祖父节点的右孩子
            RBTreeNode<T> uncle = gparent.left;
            if ((null != uncle) && isRed(uncle)) {
                setColorBlack(uncle);
                setColorBlack(parent);
                setColorRed(gparent);
                node = gparent;
                continue;
            }
 
            if (parent.left == node) {
                RBTreeNode<T> tmp;
                rightRotate(parent);
                tmp = parent;
                parent = node;
                node = tmp;
            }
 
            setColorBlack(parent);
            setColorRed(gparent);
            leftRotate(gparent);
        }
    }
    // 最后无论如何都将根节点设置为黑色
    setColorBlack(this.rootNode);
}

完结撒花！！

参考优秀文章：
【234树到红黑树】
【硬核图解面试最怕的红黑树【建议反复摩擦】】
【红黑树与AVL树，各自的优缺点总结】
【程序员的内功心法-234树】
【对红黑树的认识总结】

红黑树（Red Black Tree）的简单理解