红黑树

作者: null12 | 来源:发表于2018-03-21 22:22 被阅读0次

一、定义

红黑树（Red Black Tree）是一种特殊的二叉查找树（有时也称为2-3-4树），相比二叉查找树，特点是完全平衡，满足以下条件：

红链接均为左链接；
没有任何一个结点同时和两条红链接相连；
该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。

注：满足上述定义的红黑树也称 左倾红黑树 。

红黑树的数据结构定义：

public class RedBlackBST<Key extends Comparable<Key>, Value> {
    private static final boolean RED   = true;
    private static final boolean BLACK = false;
    private Node root;     // root of the BST
    private class Node {
        private Key key;           // key
        private Value val;         // associated data
        private Node left, right;  // links to left and right subtrees
        private boolean color;     // 结点颜色，表示其父节点到该结点的链接颜色（根节点为黑色，空结点为黑色）
        private int size;          // subtree count
 
        public Node(Key key, Value val, boolean color, int size) {
            this.key = key;
            this.val = val;
            this.color = color;
            this.size = size;
        }
    }
    public RedBlackBST() {
    }
}

二、红黑树与2-3-4树的关系

理解红黑树的关键不在红黑树本身，而在2-3-4树。红黑树的真正本质是要将2-3-4树“表达”成二叉搜索树。

那么什么是2-3-4树？

2.1 2-3-4树的定义

2-3-4树的名字是根据子结点数目来确定的，它含有三类结点：2-node、3-node、4-node，其中4-node只会出现在最底层。

2-3-4树示意图

2.2 红黑树与2-3-4树的映射

2-3-4树有三类不同的结点，而二叉搜索树只有一类结点（2-node）。
因此主要的问题就是：如何把3-node和4-node“表达”成2-node，而“红边”的引入，使这个问题的解决成为可能。
事实上，在一棵红黑树中，结点是无所谓红色还是黑色的，被染色的不是结点，而是连接结点的边。

由于在我们的定义中，红黑树的红色链接都是左链接，故映射如下：

注意：上述4-结点出现了两条相连的红色链接，违反了左倾红黑树的定义，故需要进行旋转/调整。

三、红黑树的操作

3.1 旋转

在红黑树的某些操作过程中，可能会出现红色右链接或者两条连续的红链接的情况，但在操作最终完成前，这些情况都会通过旋转来修复。旋转操作会改变红链接的指向。
旋转操作有以下几种类型（注意所谓左右旋转是针对红色链接来说的）：

3.1.1 左旋转

左旋转是指将一条红色右链接转换成红色左链接，如下图：

3-1-1 左旋
代码实现：

/**
 * 将树h进行左旋转（假设h的右链接为红色）
 * 
 * @return 返回旋转后新树的根结点，该树根结点的左链接为红色
 */
private Node rotateLeft(Node h) {
    // assert (h != null) && isRed(h.right);
    Node x = h.right;
    h.right = x.left;
    x.left = h;

    x.color = x.left.color;
    x.left.color = RED;

    x.size = h.size;
    h.size = size(h.left) + size(h.right) + 1;
    return x;
}

3.1.2 右旋转

右旋转是指将一条红色左链接转换成红色右链接，如下图：

3-1-2 右旋
代码实现：

/**
 * 将树h进行右旋转（假设h的左链接为红色）
 * 
 * @return 返回旋转后新树的根结点，该树根结点的右链接为红色
 */
private Node rotateRight(Node h) {
    // assert (h != null) && isRed(h.left);
    Node x = h.left;
    h.left = x.right;
    x.right = h;

    x.color = x.right.color;
    x.right.color = RED;

    x.size = h.size;
    h.size = size(h.left) + size(h.right) + 1;
    return x;
}

3.2 颜色翻转

当一个结点的左右链接都是红色时，需要将其转换为黑色：

3-2 颜色翻转

代码实现：

/**
 * 将以h为根的树的左右链接反转
 * 基于以下假设：
 * ①h结点的左右结点均存在
 * ②当h为黑色时，其左右结点必须都是红色；当h是红色时，其左右结点必须是黑色
 */
private void flipColors(Node h) {
    // h must have opposite color of its two children
    // assert (h != null) && (h.left != null) && (h.right != null);
    // assert (!isRed(h) && isRed(h.left) && isRed(h.right))
    // || (isRed(h) && !isRed(h.left) && !isRed(h.right));
    h.color = !h.color;
    h.left.color = !h.left.color;
    h.right.color = !h.right.color;
}

3.3 插入

红黑树的插入位置肯定在最底层（null位置），根据之前2-3-4树的定义，最底层可能是2-结点、3-结点、4-结点。
由于2-3-4树映射成红黑树后，4-结点需要处理掉，故我们只需要考虑在2-结点和3-结点插入的情况。另外，为保证树的平衡性，我们假设新插入的结点颜色初始时始终为红色。

3.3.1 向2-结点中插入新键

如果我们向2-结点插入的话，有两种情况：

插入左孩子，那么直接插入就可以；
插入右孩子，为了保持左倾，插入之后，我们需要进行一个左旋操作；

3-3-1 插入示意图（最终得到一个3-结点）

3.3.2 向3-结点中插入新键

如果我们向3-结点插入的话，有三种情况：
1. 新键大于3-结点中的两个键（右）

2. 新键小于3-结点中的两个键（左）

3. 新键在3-结点中的两个键之间（中）

上述所有情况归结起来，具体步骤如下：

找到待插入的位置（肯定是个NULL）
沿着插入点到根结点的路径向上移动，途径的每个结点（不含当前插入的结点）顺序完成以下操作：
①如果右子结点是红色，左子结点是黑色，则对该结点进行左旋转；
②如果左子结点是红色，且左子结点的左子结点也是红色，则对该结点进行右旋转；
③如果左右子结点都是红色的，则对该结点进行颜色转换；

3-3-2 插入示意图（最终得到一个4-结点，需要通过颜色转换处理掉）

代码实现：

public void put(Key key, Value val) {
    if (key == null)
        throw new IllegalArgumentException("first argument to put() is null");
    root = put(root, key, val);
    //根节点的颜色始终置为黑色
    root.color = BLACK;     
}
/**
 * 在以h为根的树中插入新结点，并进行红黑链接调整
 * @return 返回调整后的新树的根节点
 */
private Node put(Node h, Key key, Value val) {
    //h==null说明当前指向插入位置
    if (h == null)
        return new Node(key, val, RED, 1);
 
    int cmp = key.compareTo(h.key);
    if (cmp < 0)        //在左子树中插入
        h.left = put(h.left, key, val);
    else if (cmp > 0)   //在右子树中插入
        h.right = put(h.right, key, val);
    else                //h结点即查找到的键的位置，仅更新
        h.val = val;
 
    // 针对h结点进行链接调整（可抽象成通过的调整方法）：
    if (isRed(h.right) && !isRed(h.left))       //1.如果右子结点是红色，左子结点是黑色，则对该结点进行左旋转；
        h = rotateLeft(h);
    if (isRed(h.left) && isRed(h.left.left))    //2.如果左子结点是红色，且左子结点的左子结点也是红色，则对该结点进行右旋转；
        h = rotateRight(h);
    if (isRed(h.left) && isRed(h.right))        //3.如果左右子结点都是红色的，则对该结点进行颜色转换；
        flipColors(h);
    h.size = size(h.left) + size(h.right) + 1;  
    return h;
}

3-3-3 红黑树的完整插入示例

3.4 删除

删除的基本原则：

删除路径上，当前结点不能是2-结点；
必要情况下，允许各层出现4-结点；
待删除的结点，经调整后总处于最底层；
删除结点后，向上修正（fixUp）以消除之前产生的4-结点和红色右链接；

fixUp源码如下：

/**
 * 对以h为根的树进行调整，使其重新满足左倾红黑树的特点
 * @return 返回新树的根结点
 */
private Node fixUp(Node h) {
    if (isRed(h.right))     //左旋
        h = rotateLeft(h);      
    
    if (isRed(h.left) && isRed(h.left.left))    //右旋
        h = rotateRight(h);
    
    if (isRed(h.left) && isRed(h.right))        //颜色转换
        colorFlip(h);
    return h;
}

3.4.1 删除最大结点

显然，最大结点一定在最右边。
而最右边的结点可能有3种情况：2-结点、3-结点、4-结点。分别进行分析：

3-结点、4-结点：
直接删除即可。

2-结点：
如果直接删除2-结点会破坏红黑树的平衡，所以在沿搜索路径向下遇到2-结点时需要进行变换，变成3-结点或者4-结点。
变换方式就从兄弟结点借一个或者两个结点过来，根据兄弟结点的类型，分为两大类：
1、兄弟结点为2-结点
这种情况，要从父结点拿一个结点，然后与兄弟结点合并（2-结点变成4-结点）：

3-4-1 兄弟结点为2-结点的两种情况
注意：由于我们沿着删除路径向右下搜索的时候会对2-结点进行变换，所以当前指向的2-结点的父结点只可能是3-结点或4-结点

2、兄弟结点非2-结点
这种情况直接从兄弟结点借取一个结点：

3-4-2 兄弟结点为非2-结点的四种情况

那么问题来了，上面的两类删除情况是针对2-3-4树的，如何转换成红黑树的相应操作呢？

做法如下：
当我们在沿右子树不断递归向下的过程中：
①遇到左倾红边，就把它右旋；
②遇到右子结点是2-结点时，就按照上面所说的合并/借取策略将2-结点转化成3-结点或4-结点（这样最终能保证最后被删除的结点是红结点，并位于整棵树的底端）；
递归终结的条件是当目标结点h的右子树为null，此时h就是最大结点。

具体来说，步骤如下：
1. 遇到左倾红边，就将其右旋（保证较大元素被“推”到右子树去），如下图：

2. 遇到当前结点h的右子结点是2-结点时（即h.right==BLACK&&h.right.left==BLACK）：
①若h的左子结点是2-结点（即h.left.left==BLACK），采取合并策略，如下图：

②若h的左子结点不是2-结点（即h.left.left==RED），采取借取策略，如下图：

上述①②归结起来就是：

/**
 * 将以h为根的树进行调整，使其右子结点变成非2-结点
 * （假设h是红结点，且h的右子结点为2-结点）
 * 
 * @return 返回新树的根结点
 */
private Node moveRedRight(Node h) {
    // assert (h != null);
    // assert isRed(h) && !isRed(h.right) && !isRed(h.right.left);
    flipColors(h);
    if (isRed(h.left.left)) {
        h = rotateRight(h);
        flipColors(h);
    }
    return h;
}

删除最大结点-完整代码：

public void deleteMax() {
    if (isEmpty())
        throw new NoSuchElementException("BST underflow");
 
    // if both children of root are black, set root to red
    if (!isRed(root.left) && !isRed(root.right))
        root.color = RED;
 
    root = deleteMax(root);
    if (!isEmpty())
        root.color = BLACK;
}
/**
 * 删除以h为根的树的最大结点
 * 
 * @return 返回删除并修复后新树的根节点
 */
private Node deleteMax(Node h) {
    if (isRed(h.left))         //遇到左倾红边，就将其右旋
        h = rotateRight(h);
    if (h.right == null)       //h即为最大结点
        return null;
 
    if (!isRed(h.right) && !isRed(h.right.left))  //h的右子结点为2-结点
        h = moveRedRight(h);
 
    h.right = deleteMax(h.right);
 
    return fixUp(h);           //向上修复红黑树
}

删除最大结点示例1（左子结点都是2-结点）：

3-4-3 删除示例（左子结点都是2-结点）

删除最大结点示例2：

3.4.2 删除最小结点

显然，最小结点一定在最左边，最左边的结点可能有3种情况：2-结点、3-结点、4-结点。
对于每种情况如何删除，参考3.4.1删除最大结点的方式。

那么，如何转换成红黑树的相应操作呢？

做法如下：
当我们在沿左子树不断递归向下的过程中：
①遇到左倾红边则忽略，因为左倾红黑树的红边本来就是左倾的；
②遇到左子结点是2-结点时，就按照上面所说的合并/借取策略将2-结点转化成3-结点或4-结点（这样最终能保证最后被删除的结点是红结点，并位于整棵树的底端）；
递归终结的条件是当目标结点h的左子树为null，此时h就是最小结点。

具体来说，步骤如下：
1. 遇到当前结点h的左子结点是2-结点时（即h.left==BLACK&&h.left.left==BLACK）：
①若h的右子结点是2-结点（即h.right.left==BLACK），采取合并策略，如下图：

②若h的右子结点不是2-结点（即h.right.left==RED），采取借取策略，如下图：

上述①②归结起来就是：

/**
 * 将以h为根的树进行调整，使其左子结点变成非2-结点
 * （假设h是红结点，且h的左子结点为2-结点）
 * 
 * @return 返回新树的根结点
 */
private Node moveRedLeft(Node h) {
    // assert (h != null);
    // assert isRed(h) && !isRed(h.left) && !isRed(h.left.left);
    flipColors(h);
    if (isRed(h.right.left)) {
        h.right = rotateRight(h.right);
        h = rotateLeft(h);
        flipColors(h);
    }
    return h;
}

删除最小结点-完整代码：

public void deleteMin() {
    if (isEmpty())
        throw new NoSuchElementException("BST underflow");
 
    // if both children of root are black, set root to red
    if (!isRed(root.left) && !isRed(root.right))
        root.color = RED;
 
    root = deleteMin(root);
    if (!isEmpty())
        root.color = BLACK;
}

/**
 * 删除以h为根的树的最小结点
 * 
 * @return 返回删除并修复后新树的根节点
 */
private Node deleteMin(Node h) {
    if (h.left == null)     //h即为最小结点
        return null;
 
    if (!isRed(h.left) && !isRed(h.left.left))    //h的左子结点为2-结点
        h = moveRedLeft(h);
 
    h.left = deleteMin(h.left);
    return fixUp(h);        //向上修复红黑树
}

删除最小结点示例（右子结点都是2-结点）：

3-4-2 删除最小结点示例（右子结点都是2-结点）

3.4.3 删除任意结点

有了上述的铺垫，删除任意结点就相对简单很多了，其实思路是一样的，如果所要删除的结点在3-结点或者4-结点中，根据2-3-4树的性质直接删除就可以了。
最复杂的情况是如果是2-结点，那么删除就会引起不平衡。
所以就得从兄弟结点中借一个结点，但由于是任意结点，不像删除最大最小的情况，确定是左边或者右边，而是有很多种情况。根据理论研究，有9 * 6 + 27 * 9 + 81 * 12 = 1269多种情况，所以单纯的这种思路是不行的。

正确的思路：
像堆那样，如果要删除一个结点，把待删除结点和最底部的结点交换，然后就变成删除最底部的结点，就可以转换成删除最大结点或者最小结点了。
这样也把问题简化了，因为删除最大和最小结点的方法我们已经分析出来了。

具体步骤：

查找待删除结点的右子树中的最小结点（即后继结点）；
将待删除结点置为后继结点；
删除待删除结点的后继结点。

归结起来就是：

Node x = min(h.right);
h.key = x.key;
h.val = x.val;
h.right = deleteMin(h.right);

例如，要删除下面这棵红黑树的D结点，步骤如下：
1. 选用D结点左子树的最大结点或者右子树的最小结点来替换D的值（本质就是用离D最近的结点替换掉D，然后将替换的结点删除，那么树仍然是有序的）；
2. 然后删除D结点左子树的最大结点或右子树的最小结点。

3-4-3 选用D的右子树的最小结点作替换

删除任意结点-完整源码：

public void delete(Key key) {
    if (key == null)
        throw new IllegalArgumentException("argument to delete() is null");
    if (!contains(key))
        return;
 
    // if both children of root are black, set root to red
    if (!isRed(root.left) && !isRed(root.right))
        root.color = RED;
 
    root = delete(root, key);
    if (!isEmpty())
        root.color = BLACK;
}
/**
 * 删除以h为根的树中的指定结点
 * 
 * @return 返回删除后新树的根结点
 */
private Node delete(Node h, Key key) {
    // assert get(h, key) != null;
    int cmp = key.compareTo(h.key);
    if (cmp < 0) {    //待删除结点<当前结点，则在左子树中递归（采用5.2删除最小结点的变换方式）
        if (!isRed(h.left) && !isRed(h.left.left))
            h = moveRedLeft(h);
        h.left = delete(h.left, key);
    } else {          //待删除结点≥当前结点，则在右子树中递归（采用5.1删除最大结点的变换方式）
        if (isRed(h.left))
            h = rotateRight(h);
 
        if (cmp == 0 && (h.right == null))
            return null;
 
        if (!isRed(h.right) && !isRed(h.right.left))
            h = moveRedRight(h);
 
        if (cmp == 0) {   //找到待删除结点等于当前结点
            Node x = min(h.right);
            h.key = x.key;
            h.val = x.val;
            h.right = deleteMin(h.right);
        } else            //待删除结点>当前结点
            h.right = delete(h.right, key);
    }
    return fixUp(h);
}

四、性能分析

无论键的插入顺序如何，红黑树都几乎是完美平衡的。

一棵大小为N的红黑树，最大高度为2lgN（交替出现红黑结点），最小高度为lgN(所有结点都是黑色)。

时间复杂度
O(lgN)

红黑树