红黑树

概述

二叉查找树的查找时间复杂度为O(lgN),但是二叉查找树有一个问题,如果插入的数据时有有序的,就变成了一个链表,查找时间复杂度为O(N)。如下图1.1:

图 1.1

为了解决这种退化的情况,需要对二叉树作平衡操作,但要保证二叉树的完全平衡的代价很高,因而演化出其他平衡树,比如2-3查找树,在一个节点上可能有2个键和3个链接,如下图1.2:8介于7和9之间,多了一条链。

图 1.2

2-3树很好地解决了保证平衡性的问题,但是代价也不小,比如查找就不如二叉查找树方便。还好,只需要作一点调整,就能很好地利用二叉查找树和2-3查找树的优点。我们用一条红色链连接两个 2-节点 表示一个 3-节点 ,如图1.3:

图 1.3
我们把这种2-3树的表示方式称为红黑树。每一个节点只有一个链接指向自己(如指向4的红色链接),把它的颜色保证到节点上,也就相当于给节点着色,这就是我们最常见的红黑树。


红黑树的性质如下:
1. 任何一个节点都有颜色,黑色或者红色
2. 根节点是黑色的
3. 空节点被认为是黑色的(叶子节点)
4. 父子节点之间不能出现两个连续的红节点
5. 任何一个节点向下遍历到其子孙的叶子节点,所经过的黑节点个数必须相等

如下图1.4,如果按照1-8的顺序插入,不再是链表结构。

图 1.4

二、插入

红黑树的插入和二叉搜索树一样,比对大小,找到节点插入。不同的是,插入后可能破坏了红黑树的特性,需进一步修复。新插入的节点,都作为红色处理(为什么是红色而不是黑色:黑色一定破坏性质的第四条,红色需要处理的情况简单一点)。

插入后不需要调整

  1. 如果是根节点,重新着色为黑即可。
  2. 父亲如果为黑色,并不违反红黑树性质,直接插入。

插入后需要调整

从上一种情况得知,插入后需要调整的,父节点一定是红色,又分3种情况。
3.1 叔叔节点为红色

图 2.1
父节点和叔叔都是红色,把他们都变为黑色,祖父变为红色,这样黑色节点同时减少一个,保证了特性5

调整结束后,祖父节点又可能破坏特性4,继续按照插入的逻辑往上回溯。后续谈到的情况中,不再涉及递归回溯说明。即把修改后的节点(祖父)当成是新加入的节点进行各种情形的检查。 这就好比,二叉树remove(),删除一个节点,用子节点来替换,需继续删除用来替换的子节点,如此递归或循环。

3.2 叔叔节点为黑色(或空),且祖父节点、父节点和新节点处于一条斜线上

图 2.2

图 2.3
如图2.2,在一条右斜线上,解决办法是:针对祖父节点7左旋,然后父亲祖父互换颜色。为什么这样能保证平衡性呢,因为祖父一定是黑色,旋转后,祖父位置被父亲替换,为了保证黑色节点不变少,父亲节点还用原来祖父的黑色。祖父旋转到另一个分支,黑色节点多了一个,重新着红色,同时保证了特性4,5。 反之为图2.4。

3.3 叔叔节点为黑色(或空),且祖父节点、父节点和新节点不在一条斜线上

图 2.4

图 2.5
如图2.4,插入节点3,左旋后,就跟第二情况类似,再按照第二种方式处理。反之亦然。

实现

要实现插入,先要实现几个方法,首先是能找到需要插入节点对应的父节点,插入后,需要找到叔叔节点。之后就是重新着色和左右旋。

/**
 * 寻找父节点:
 * 跟二叉查找树一样,比对节点值大小,找到要插入的父节点
 *
 * @param node node
 * @return RBTreeNode node
 */
public RBTreeNode<T> findParentNode(RBTreeNode<T> node) {
    RBTreeNode<T> parent = root;
    RBTreeNode<T> child = root;
    while (child != null) {
        int result = child.getValue().compareTo(node.getValue());
        if (result == 0) {
            // 和其中一只节点相同
            return child;
        }
        parent = child;
        if (result > 0) {
            child = child.getLeft();
        } else {
            child = child.getRight();
        }
    }
    return parent;
}
/**
 * 找到叔叔节点
 *
 * @param node node
 * @return uncle
 */
public RBTreeNode<T> getUncle(RBTreeNode<T> node) {
    RBTreeNode<T> parent = node.getParent();
    RBTreeNode<T> grandfather = parent.getParent();
    if (grandfather == null) {
        return null;
    }
    if (parent == grandfather.getLeft()) {
        return grandfather.getRight();
    } else {
        return grandfather.getLeft();
    }
}


图 2.6

图上,对2节点左旋:右节点4替换2,2作为4左节点,3作为2右节点。

/**
 * 左旋
 *
 * @param node node
 */
private void rotateLeft(RBTreeNode<T> node) {
    // 把待替换节(n)的右节点(r)替换它
    RBTreeNode<T> replaceNode = node.getRight();
    node.setRight(replaceNode.getLeft());

    if (replaceNode.getLeft() != null) {
        replaceNode.getLeft().setParent(node);
    }
    // r.p = n.p
    replaceNode.setParent(node.getParent());
    if (node.getParent() == null) {
        // p = null, 就是根节点
        root = replaceNode;
    } else {
        // p 重置子节点
        if (node.getParent().getLeft() == node) {
            node.getParent().setLeft(replaceNode);
        } else {
            node.getParent().setRight(replaceNode);
        }
    }

    // r.l = n
    replaceNode.setLeft(node);
    // n.p = r
    node.setParent(replaceNode);
}


图 2.7

/**
 * 右旋
 *
 * @param node node
 */
private void rotateRight(RBTreeNode<T> node) {
    // 把待替换节(n)的左节点(l)替换它
    RBTreeNode<T> replaceNode = node.getLeft();
    RBTreeNode<T> parent = node.getParent();
    node.setLeft(replaceNode.getRight());
    setParent(replaceNode.getRight(), node);

    replaceNode.setRight(node);
    setParent(node, replaceNode);

    if (parent == null) {
        root = replaceNode;
        setParent(replaceNode, null);
    } else {
        if (parent.getLeft() == node) {
            parent.setLeft(replaceNode);
        } else {
            parent.setRight(replaceNode);
        }
        setParent(replaceNode, parent);
    }
}

根据以上情况和方法,插入就变得容易了。

public T addNode(T value) {
    RBTreeNode<T> t = new RBTreeNode<T>(value);
    return addNode(t);
}

/**
 * 插入节点
 *
 * @param node node
 * @return value
 */
private T addNode(RBTreeNode<T> node) {

    // 新插入的节点为红色
    node.setLeft(null);
    node.setRight(null);
    node.setRed(true);

    if (root == null) {
        // 新插入节点为根节点
        root = node;
        root.setRed(false);
        return root.getValue();
    }
    // 找到要插入的父节点
    RBTreeNode<T> parentNode = findParentNode(node);
    int result = parentNode.getValue().compareTo(node.getValue());
    if (result == 0) {
        return node.getValue();
    }
    if (result > 0) {
        parentNode.setLeft(node);
    } else {
        parentNode.setRight(node);
    }
    node.setParent(parentNode);
    if (parentNode.isRed()) {
        fixAdd(node);
    }
    return null;
}

修复插入后的树

/**
 * 插入修复
 *
 * @param node node
 */
private void fixAdd(RBTreeNode<T> node) {
    // 找到parent和uncle
    RBTreeNode<T> parent = node.getParent();

    while (parent != null && parent.isRed()) {
        RBTreeNode<T> uncle = getUncle(node);
        if (uncle == null || !uncle.isRed()) {
            // 祖先
            RBTreeNode<T> ancestor = parent.getParent();

            if (ancestor == null) {
                parent.setRed(false);
                return;
            }
            if (ancestor.getLeft() == parent) {
                boolean isRight = node == parent.getRight();
                if (isRight) {
                    // 左旋,就变成一条斜线
                    rotateLeft(parent);
                }
                // 一条斜线,右旋
                rotateRight(ancestor);
                switchColor(ancestor, ancestor.getParent());
                parent = null;
            } else {
                boolean isLeft = node == parent.getLeft();
                if (isLeft) {
                    rotateRight(parent);
                }
                rotateLeft(ancestor);
                if (isLeft) {
                    node.setRed(false);
                    parent = null;
                } else {
                    parent.setRed(false);
                }
                ancestor.setRed(true);
            }
        } else if (uncle.isRed()) {
            // 1. 叔叔不为空
            uncle.setRed(false);
            parent.setRed(false);
            parent.getParent().setRed(true);
            node = parent.getParent();
            parent = node.getParent();
        }
    }
    getRoot().setRed(false);
    getRoot().setParent(null);
}

三、删除

删除是红黑树最复杂的操作,为避免不被各种情况绕晕,中心思想就是:按照二叉查找树方式删节点,考虑各种情况下是否违背红黑树特性,特别是特性4,5

这里要做一个重要的说明,是后续删除操作都和这个说明有关: 对于一颗二叉查找树,如果节点有两个孩子,将会找右边子树中最小值(或左边最大值)作为替代值。然后再删除替代值原先的位置。这个替代值一定最多有一个孩子。

图 3.1

如图3.1, 删除22,替代值将会是31(右子树最小值),31的左子树一定为空,否则他不会作为替代值。这样看来,二叉树最终操作的是最多有一个孩子的节点。这对红黑树删除操作有很多简化,因为如果有寻找替换节点的过程,只是替换值,并不影响二叉树任何性质。

因此,我们只需要讨论删除只有一个儿子的节点(如果都为叶子节点,可将任意一个作为儿子看待)。

3.1 被删除节点是红色

还是图3.1,节点31为红色,那他的孩子一定都是叶子节点,并不破坏红黑树任何属性(平衡),直接删除即可。

3.2 被删除节点是黑色,儿子为红色

此时,儿子顶上来,变为黑色,黑色节点没少,也不会破坏特性4,5

图 3.2

3.3 被删除节点是黑色,儿子也是黑色

这种情况较复杂,我们分成多个case处理:
case1: 被删除的是根节点,替换后无需处理。
case2: S节点为红色

图 3.3
> 图中N为删除后的替换上来的子节点,此时,P-N这个分支已经少了一个黑色节点,其实,S应该是N的叔叔节点, 后续几种case的图也类似表达。

因为兄弟为红色,P和S1、S2坑一定都为黑色。这种情况下,对P左旋,并交换N父亲和祖父颜色。为什么这样做?相对P这个位置,颜色没变,右子树少一个红色节点,并不破坏红黑树性质;对于左子树,S-P-S1 路线上的黑色节点还是没变,对N,还是如同新替换上来的节点,继续做后面几种case处理。

case3:P,S,S1,S2都是黑色

图 3.4
如上图左,都为黑色,只需要把兄弟S变为红色即可做到P的作为分支平衡,但是对整个P这条分支,少了一个黑色节点。需要对P重新作平衡处理(从case1开始适配)。
case4:P为红色,S和儿子都不是红色

图 3.5
这中情况比较简单,把父兄颜色交换即可。因为通过S路径黑色没少,但通过N增加一个黑色P,从而达到平衡。

case5:S是黑色,S的一侧(N同侧)儿子红,另一侧儿子为黑色

图 3.6
这种情况,对S右旋。替换S和新父亲颜色,整个P的右子树黑色简单都没变,但经过N的路线还是少一个黑节点。按case6进行操作

case6:S是黑色,另一侧儿子为红色

图 3.7
如图,对P左旋并和S交互颜色,再把S2变为黑色。这样操作后,最顶上颜色没变,右侧少一个黑色S被S2补充,也没破坏平衡。左侧新增一个黑色节点,从而达到平衡:
>注: 这种情况下,P是红色或者黑色都一样。如果图中P为黑色,那么交互颜色后,在此基础上,还还是多了一个黑色祖先(S)

实现

/**
 * 删除节点
 *
 * @param node node
 */
private void remove(RBTreeNode<T> node) {
    RBTreeNode<T> dataRoot = getRoot();
    RBTreeNode<T> parent = root;
    while (dataRoot != null) {
        int cmp = dataRoot.getValue().compareTo(node.getValue());
        if (cmp < 0) {
            // 遍历右子树
            parent = dataRoot;
            dataRoot = dataRoot.getRight();
        } else if (cmp > 0) {
            // 遍历左子树
            parent = dataRoot;
            dataRoot = dataRoot.getLeft();
        } else {
            // 找到对应节点
            if (dataRoot.getRight() != null && dataRoot.getLeft() != null) {
                // 被删除节点的"左右孩子都不为空"的情况
                RBTreeNode<T> successor = findMin(dataRoot.getRight());
                dataRoot.setValue(successor.getValue());
                node = successor;
                dataRoot = dataRoot.getRight();
            } else {
                // 最多只有一个孩子
                if (dataRoot.isRed()) {
                    // 两个节点不是非空且是红色,那么孩子一定都是叶子节点
                    if (parent.getLeft() == dataRoot) {
                        parent.setLeft(null);
                    } else {
                        parent.setRight(null);
                    }
                    dataRoot = dataRoot.getLeft() == null ? dataRoot.getRight() : dataRoot.getLeft();
                } else {
                    // 最多只有一个孩子的黑色节点:1. 孩子是红色,2. 没有孩子(叶子节点)
                    RBTreeNode<T> onlyChild = findOneChild(dataRoot);
                    if (isRed(onlyChild)) {
                        //1. 孩子是红色
                        dataRoot.setValue(onlyChild.getValue());
                        if (dataRoot.getLeft() == onlyChild) {
                            dataRoot.setLeft(null);
                        } else {
                            dataRoot.setRight(null);
                        }
                        return;
                    }
                    // 2. 没有孩子(都是叶子节点)
                    fixRemove(dataRoot);
                    parent = dataRoot.getParent();
                    if (parent == null) {
                        root = null;
                        return;
                    }
                    if (parent.getLeft() == dataRoot) {
                        parent.setLeft(null);
                    } else {
                        parent.setRight(null);
                    }
                    dataRoot = null;
                }
            }
        }
    }
}

删除修复

/**
 * 删除修复
 *
 * @param node node
 */
private void fixRemove(RBTreeNode<T> node) {
    if (node == null || node.isRed()) {
        throw new IllegalArgumentException("Node err ... ");
    }
    RBTreeNode<T> onlyChild = findOneChild(node);
    if (isRed(onlyChild)) {
        throw new IllegalArgumentException("Node err ... ");
    } else {
        // 删除节点是黑色,儿子也是黑色(其实应该说孩子都是叶子节点)
        RBTreeNode<T> parent = node.getParent();
        if (parent == null) {
            // case1: 被删除的是根节点,替换后无需处理。
            return;
        }
        boolean isLeft = parent.getLeft() == node;
        RBTreeNode<T> sibling = getSibling(node);
        if (sibling == null) {
            // 黑色(非叶子节点)节点才修改,但黑色节点一定有兄弟
            throw new IllegalArgumentException("Node err ... ");
        }
        if (isRed(sibling)) {
            // case2:  S节点为红色
            if (isLeft) {
                rotateLeft(parent);
            } else {
                rotateRight(parent);
            }
            switchColor(parent, parent.getParent());
            // 此时,新节点还是原来位置
            parent = node.getParent();
            sibling = getSibling(node);
        }
        if (!parent.isRed() && !isRed(sibling) && !isRed(sibling.getLeft()) && !isRed(sibling.getRight())) {
            // case3: P,S,S1,S2都是黑色
            sibling.setRed(true);
            if (parent.getParent() == null) {
                parent.setRed(false);
            } else {
                fixRemove(parent);
            }
        }
        if (isRed(parent) && !isRed(sibling.getLeft()) && !isRed(sibling.getRight())) {
            //case4: P为红色,S(一定黑)和儿子都不是红色
            switchColor(parent, sibling);
            return;
        }
        if (isLeft && !isRed(sibling) && isRed(sibling.getLeft()) && !isRed(sibling.getRight())) {
            //case5: S是黑色,S的一侧(N同侧)儿子黑色,另一侧儿子为红色
            rotateRight(sibling);
            switchColor(sibling, sibling.getParent());
            sibling = getSibling(node);
        } else if (!isLeft && !isRed(sibling) && isRed(sibling.getRight()) && !isRed(sibling.getLeft())) {
            rotateLeft(sibling);
            switchColor(sibling, sibling.getParent());
            sibling = getSibling(node);
        }
        // case6: S是黑色,S的一侧(N同侧)儿子黑色,另一侧儿子为红色
        if (isLeft && !isRed(sibling) && isRed(sibling.getRight())) {
            rotateLeft(parent);
            sibling.getRight().setRed(false);
            switchColor(parent, sibling);
        } else if (!isLeft && !isRed(sibling) && isRed(sibling.getLeft())) {
            rotateRight(parent);
            sibling.getLeft().setRed(false);
            switchColor(parent, sibling);
        }
    }
}

省略了一些方法如switchColor,getSibling。代码还有不少可以重构优化的点。源码


参考文档:
[1]. https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91
[2]. http://sandbox.runjs.cn/show/2nngvn8w
[3]. https://tech.meituan.com/redblack-tree.html
[4]. http://blog.csdn.net/v_JULY_v/article/details/6284050
[5]. https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
[6]. https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md

CONTENTS