红黑树算法

红黑树是二叉搜索树的增强版，我们知道优化二叉搜索树的核心是优化二叉搜索树的高度，也就是使树尽可能地平衡，红黑树就是解决这个问题的，它能够尽可能地平衡二叉搜索树的高度，保证动态集合操作在最差的情况下时间复杂度保持在O(lgn)。

红黑树通过在每个节点对象（Node）上增加颜色属性（color）来保证从根到叶子的从A到B节点任意两条路径差距不超过2倍，因而是近似于平衡的。

注意：红黑树只是平衡二叉搜索树的其中一种，平衡二叉树还有其它算法。

关于二叉搜索树可以阅读笔者前面写的二叉搜索树文章，这里只给出二叉搜索树的定义，其它不再过多详细讲解，二叉搜索树是指具有下面定义的二叉树：

1、任何父节点的值均大于等于（>=）左孩子节点值以及左孩子下的所有孩子节点值

2、任何父节点的值均小于（<）右孩子节点值以及右孩子下的所有孩子节点值

3、树最根节点是唯一父节点值为null的节点

定义

红黑树是一颗二叉搜索树，所以除了要满足二叉搜索树的定义外，红黑树还要满足下面的定义（背下来）：

1、每个节点要么是红色要么是黑色

2、根节点是黑色的

3、为null的叶节点是黑色的（代码实现上可以用一个全局对象代表所有为null的节点）

4、如果一个节点是红色的，那么它的两个子节点都是黑色的

5、给定任意节点，从该节点到其所有后代叶节点的简单路径上均包含相同数目的黑色节点

红黑树-左、右旋转（left/right-rotate）

我们知道，当对二叉搜索树进行插入、删除操作时会改变树结构，改变后的树结构可能会破坏红黑树的性质（前面列出的定义），为了保证每次改变结构后性质不被破坏，每次修改后需要调整，调整方式有两种，分别是变色和旋转，其中旋转又包含左旋转和右旋转。

注意，只有旋转才会改变（逐渐平衡）树的高度，变色是不会改变树高度的。

下面图解左右旋转分别是怎么调整节点位置的（学习旋转时我们先不要关注它们的颜色，只关注旋转怎么调整相关节点的位置）。

我们通过上图可以很直观发现，B树左旋转后得到A树，A树可以通过B树右旋转还原回来，它们是对称的。下面是对左右旋转规律的总结：

B树a节点左旋转后得到A树位置调整如下：

1、将a节点的右孩子节点c替换到a节点位置的父节点下

2、a节点变为c节点的左孩子

3、c节点原来的左孩子变为a节点的右孩子

4、a节点原来的左孩子不变

5、c节点原来的右孩子节点不变

左旋转代码实现如下：

/** * 为null的节点统一对象 */private Node nil;/** * 根节点 */private Node rootNode;private static final int RED = 1;private static final int BLACK = 2;public RedBlackTree() {    this.nil = new Node();    this.nil.color = BLACK;    this.rootNode = this.nil;}/** * 节点对象 */private class Node {    private Node left;    private T eleVal;    private Node right;    private Node parent;    /**     * 颜色  RED：红色 BLACK：黑色     */    private int color;    private Node(T eleVal) {        this.eleVal = eleVal;    }    private Node() {        this.color = RED;        this.left = null;        this.right = null;        this.parent = null;    }    @Override    public String toString() {        return "Node{" +                "eleVal=" + eleVal +                ", color=" + color +                '}';    }}/** * 左旋转 * * @param a 操作节点 */private void leftRotate(Node a) {    Node c = a.right;    //1、将a节点的右孩子节点c替换到a节点位置的父节点下    c.parent = a.parent;    if (a.parent == this.nil) {        this.rootNode = c;    } else if (a == a.parent.left) {        a.parent.left = c;    } else {        a.parent.right = c;    }    //2、a节点变为c节点的左孩子    c.left = a;    a.parent = c;    //3、c节点原来的左孩子变为a节点的右孩子    a.right = c.left;    if (c.left != this.nil) {        c.left.parent = a;    }}

A树c节点右旋转后得到B树位置调整如下：

1、将c节点的左孩子节点a替换到c节点位置的父节点下

2、c节点变为a节点的右孩子

3、a节点原来的右孩子变为c节点的左孩子

4、a节点原来的左孩子不变

5、c节点原来的右孩子节点不变

右旋转代码实现如下：

/** * 右旋转 * * @param c 操作节点 */private void rightRotate(Node c) {    //1、将c节点的左孩子节点a替换到c节点位置的父节点下    Node a = c.left;    a.parent = c.parent;    if (c.parent == this.nil) {        this.rootNode = a;    } else if (c.parent.left == c) {        c.parent.left = a;    } else {        c.parent.right = a;    }    //2、c节点变为a节点的右孩子    a.right = c;    c.parent = a;    //3、a节点原来的右孩子变为c节点的左孩子    c.left = a.right;    if (a.right != this.nil) {        a.right.parent = c;    }}

实际上，这种调整是严格按照二叉搜索树定义来的，这里并不打算花时间详细去证明这种调整是如何总是能够保证满足红黑树二叉搜索树性质的，有兴趣读者可以自己去研究或参考网上资料进行深入学习。但是不管研究深度如何，最后的做法都是把调整的规律记下来。

最后有几个疑问，就是在什么情况下应该进行左旋转、在什么情况下又应该进行右旋转呢？还有变色又是怎么回事？带着这些问题我们继续往下看。

红黑树-插入（insert）

插入实际上就是构建红黑树性质的二叉搜索树，每次插入一个节点时，既要遵循二叉搜索树的定义又要保证不破坏红黑树的性质，可想而知，插入的逻辑会比较复杂。还是那个习惯，我们只关心操作规律规则，暂且不要纠结如何证明，因为证明的过程太复杂，很多程序员包括一般算法类工程师也未必能够用数学公式完全证明出来，大部分都是记住定义，就是学数学一样，把公式记下来。

我们先思考假设插入一个节点newNode,大概步骤有哪些？一般来说有以下步骤：

1、首先要根据二叉搜索树定义将newNode节点插入到正确位置，例如插入值为4的新节点图解如下（虽然下图颜色是满足红黑树定义的，但先不要关心颜色，因为现在还不到检查调整红黑树定义的步骤）：

二叉搜索树性质插入代码如下：

/** * 根据二叉搜索树定义插入新节点 * * @param newNode 新节点 */@SuppressWarnings("unchecked")private void twoForkSearchTreeInsert(Node newNode) {    Node insertParent = this.nil;    Node currentParent = this.rootNode;    //只要不是为null的叶子节点，就一直查找下去    while (currentParent != this.nil) {        //当前父节点作为本次插入节点的父节点        insertParent = currentParent;        //newNode.eleVal <= currentParent.eleVal        //左孩子作为父节点继续判断        if (newNode.eleVal.compareTo(currentParent.eleVal) <= 0) {            currentParent = currentParent.left;        } else {            //newNode.eleVal > currentParent.eleVal            //右孩子作为父节点继续判断            currentParent = currentParent.right;        }    }    newNode.parent = insertParent;    //如果父节点为null，本次插入的直接作为最根节点    if (insertParent == this.nil) {        this.rootNode = newNode;    } else if (newNode.eleVal.compareTo(insertParent.eleVal) <= 0) {        //左孩子        insertParent.left = newNode;    } else {        //右孩子        insertParent.right = newNode;    }}

2、为新节点新增颜色（默认为红色），以及设置为null的叶子节点为nil属性，代码如下：

/** * 给新插入节点进行红黑树着为红色 * * @param newNode 新插入节点 */private void setRedBlackTreeProperty(Node newNode) {    newNode.left = this.nil;    newNode.right = this.nil;    newNode.parent = this.nil;    //红色    newNode.color = RED;}

为什么将新插入的节点默认着为红色，答案在红黑树第五条定义：

“给定任意节点，从该节点到其所有后代叶节点的简单路径上均包含相同数目的黑色节点”

从这条定义可以看出，如果插入黑色的话，一定是错误的。当然，红色也可能错误，但是红色导致的错误比黑色导致的错误容易处理些，所以选择了红色作为插入的默认颜色。

3、根据二叉搜索树插入后，接下来就需要判断是否满足红黑树性质，如果不满足则需要进行调整。我们知道新插入节点颜色默认着为红色，根据红黑树的定义，下面我们分析哪些定义可能会被破坏：

定义1：每个节点要么是红色要么是黑色（不会被破坏）

定义2：根节点是黑色的（可能会被破坏）

定义3：为null的叶节点是黑色的（不会被破坏）

定义4：如果一个节点是红色的，那么它的两个子节点都是黑色的（可能会被破坏）

定义5：给定任意节点，从该节点到其所有后代叶节点的简单路径上均包含相同数目的黑色节点（不会被破坏，因为插入节点是红色的）

上面总结出当每次插入至多只有一条定义被破坏，要么是定义2（根节点必须是黑色但插入的是红色），要么是定义4（如果它父节点是红色但插入的子节点默认也是红色），他们不可能同时被破坏，因为如果新插入节点是根，那么根本还没有子节点，根本不会出现定义4的情况；如果不是根，那就证明存在根，根肯定已经是黑色的，虽然在进过多次调整后根节点也可能会被破坏，所以简单粗暴的办法就是每次插入最后那行代码把根节点着为黑色即可。下面给出调整红黑树的代码，紧接着分析定义4被破坏的3种情况相应的调整规则。

/** * 调整红黑树结构，保证不破坏红黑树定义 * * @param newNode 新插入节点 */private void updateRedBlackTree(Node newNode) {    //如果新增节点的父节点颜色是红色，这种情况一定破坏了红黑树定义    //定义4：如果一个节点是红色的，那么它的两个子节点都是黑色的    while (newNode.parent.color == RED) {        //如果新增节点的父节点是祖父节点的左孩子        if (newNode.parent == newNode.parent.parent.left) {            //新增节点的叔节点            Node uncleNode = newNode.parent.parent.right;            //情况1：叔节点是红色            if (uncleNode.color == RED) {                this.setColor(newNode.parent, BLACK);                this.setColor(uncleNode, BLACK);                this.setColor(newNode.parent.parent, RED);                newNode = newNode.parent.parent;                //情况2：叔节点是黑色且新插入节是右孩子            } else if (uncleNode.color == BLACK && newNode == newNode.parent.right) {                newNode = newNode.parent;                this.leftRotate(newNode);            }            //情况3：叔节点是黑色且新插入节是左孩子            this.setColor(newNode.parent, BLACK);            this.setColor(newNode.parent.parent, RED);            this.rightRotate(newNode.parent.parent);            //如果新增节点的父节点是祖父节点的右孩子，交换位置后继续按左孩子逻辑调整        } else if (newNode.parent == newNode.parent.parent.right) {            Node uncleNode = newNode.parent.parent.left;            //情况1：叔节点是红色            if (uncleNode.color == RED) {                this.setColor(newNode.parent, BLACK);                this.setColor(uncleNode, BLACK);                this.setColor(newNode.parent.parent, RED);                newNode = newNode.parent.parent;                //情况2：叔节点是黑色且新插入节是右孩子            } else if (uncleNode.color == BLACK && newNode == newNode.parent.left) {                newNode = newNode.parent;                this.rightRotate(newNode);            }            //情况3：叔节点是黑色且新插入节是左孩子            this.setColor(newNode.parent, BLACK);            this.setColor(newNode.parent.parent, RED);            this.leftRotate(newNode.parent.parent);        }    }    //简单粗暴总是将根节点设置为黑色    this.rootNode.color = BLACK;}private void setColor(Node node, int color) {    if (node != null) {        node.color = color;    }}

情况1：新插入节点（newNode）的叔节点（uncleNode）是红色

此时情况如下图（下图省略了不关键的子树）

这种情况由于newNode的父节点和叔节点都是红色时发生，先将父节点变为黑色（修复被破坏的定义4），然后将祖父节点变为红色（变色父节点后导致定义5被破坏），最后将叔节点变为黑色（变色祖父节点后导致定义4再次被破坏），还没有结束，实际代码实现上，还需要将祖父节点指针赋值给newNode,循环检查直至根节点，因为我们改变了祖父节点的颜色，势必会破坏上面的结构。

情况2：新插入节点（newNode）的叔节点是黑色的且newNode是一个右孩子

情况3：新插入节点（newNode）的叔节点是黑色的且newNode是一个左孩子

情况4：叔节点是黑色且新插入节点是左孩子

其它情况的分析思路留给读者自己根据代码配合注释和前面的讲解去分析，无非就是旋转和变色，这里就不再过多地做规则翻译。