数据结构 - 树 - 红黑树

作者: faris_shi | 来源:发表于2018-02-22 06:55 被阅读110次

1. 介绍

大家都知道二叉树查找树有一个问题，就是容易偏向某一侧，这样就像一个链表结构了，失去了树结构的优点，查找时间会变坏。

因此我们需要树的平衡。

AVL树是一个完全平衡的二叉树，因为它规定了每个节点的左子树和右子树的高度最多差1。因此为了平衡，AVL树在修改数据之后，会通过更多的旋转来达到完美平衡。因此 AVL树的查询效率是最高的，但是删除和插入的效率却是最低的。

234树通过对二叉树的扩展以及节点分裂而实现了树的完美平衡，但是将这种直白的表述写成代码实现起来并不方便，因为要处理的情况太多。

因此红黑树出现了，它的实现逻辑是234树的逻辑。红黑树通过红黑作为标记，来实现234树。

红黑树中，所有的节点都是标准的2-节点，为了体现出3-节点，这里将3-节点的两个元素用斜红色的链接连接起来，即连接了两个2-节点来表示一个3-节点。这里红色节点标记就代表指向其的链接是红链接，黑色标记的节点就是普通的节点。

所以才会有那样一条定义，叫“从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点”，因为红色节点是可以与其父节点合并为一个3-节点的。

红黑树实现的其实是一个完美的黑色平衡，如果你将红黑树中所有的红色链接放平，那么它所有的叶子节点到根节点的距离都是相同的。所以它并不是一个严格的平衡二叉树，但是它的综合性能已经很优秀了。

红黑树用非严格的平衡来换取增删节点时候旋转次数的降低，因此它的插入、删除效率会比AVL树快，但是查询效率会略微低。

定义：

一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。

红-黑树的主要规则如下：

每个节点不是红色就是黑色的；
根节点总是黑色的；
如果节点是红色的，则它的子节点必须是黑色的（反之不一定）；
从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。

树节点定义

存在一个问题：

对于一棵2-3-4树可能有多种不同的表示，这是在于对于3-node的表示，红色的边可以向左倾，也可以向右倾。

考虑很多情况。

我们在此只考虑左倾的情况，所以这种树也叫做左倾红黑树。

对于左倾红黑树，我们还有以下要求，就是不能以下情况的节点情况：

由于是左倾的，就不能出现右倾的3-node
不允许出现两个红边连在一起的情况，变成2-3-4树的情况就是不允许两个3-node相互连接。因为这样化，234树无法完成分裂。

左倾红黑树与234树的对比关系：

2. 实现

2.1 类定义

public class RedBlackTree<T extends Comparable<T>> {
    private static final boolean RED = true;

    private static final boolean BLACK = false;

    private TreeNode<T> root;
}

2.2 节点定义

private static class TreeNode<T> {

    T data;

    TreeNode<T> left;

    TreeNode<T> right;

    boolean color;

    public TreeNode(T data, boolean color) {
        this.data = data;
        this.color = color;
    }

}

2.2 查询

红黑树的查询逻辑与二叉查找树、AVL树的逻辑完全相同，因此不在此再做展示，有需要可以查看 AVL树、二叉树查找树。

2.3 插入

插入操作是红黑树中最复杂的操作之一。因为不仅要插入还要维持红黑颜色的。

我们对红黑树中的节点的转化操作也使用了旋转：

左旋转

左旋操作就是将右倾的3-node变成左倾的3-node。

private TreeNode<T> rotateLeft(TreeNode<T> node) {
    TreeNode<T> rightNode = node.right;
    node.right = rightNode.left;
    rightNode.left = node;
    rightNode.color = rightNode.left.color;
    rightNode.left.color = RED;
    return rightNode;
}

右旋转

右旋操作就是将左倾的3-node变成右倾的3-node，与坐旋转相反。

private TreeNode<T> rotateRight(TreeNode<T> node) {
    TreeNode<T> leftNode = node.left;
    node.left = leftNode.right;
    leftNode.right = node;
    leftNode.color = leftNode.right.color;
    leftNode.right.color = RED;
    return leftNode;
}

插入操作分为多种情况：

首先说下前提：我们讨论的是左倾红黑树，我们插入的节点都为红色。

2.3.1 向2-node节点插入

我们向2-node插入节点，将2-node变成3-node。

两种情况：

如果插入左子节点，正好是红色的，与父节点组成了3-node，直接插入，不需要再做任何操作。
但如果插入的是右子节点，变成了右倾的3-node，所以我们需要左旋转。

2.3.2 向3-node节点插入

我们向3-node插入一个节点，变成4-node。

我们知道，3-node中父节点为黑色，左子节点为红色。

分3种情况：

如果插入到左子节点的左子节点，会出现两个红边相连的情况，那么需要右旋转。
如果插入到左子节点的柚子节点，会出现右倾的情况，在进行左旋转之后，还是出现了两个红边相连的情况，所以还需要一次右旋转。
如果插入到右子节点，正好是红色，所以不需要任何操作就可以完成。

2.3.3 向4-node插入

在2-3-4树中，我们需要对4-node进行切分，切分的方法就是将4-node的中间节点向上移动到父节点中，然后再完成插入。

当父节点是2-node

那么会将2-node节点变成3-node。

我们发现有两种情况：

如果4-node节点是2-node节点的左子节点，分裂后，我们会发现，我们需要把4-node 中的子节点由红色变成黑色，而父节点变成红色与2-node正好组成3-node。
如果4-node节点是2-node节点的右子节点，分裂后，我们会发现，如果我们先进行变色后，新生成的3-node是一个右倾的3-node，这样我们只需要完成左旋转即可。

这个颜色变换的过程，我们叫做 color flip。

private TreeNode<T> colorFlip(TreeNode<T> node) {
    node.color = !node.color;
    node.left.color = !node.left.color;
    node.right.color = !node.right.color;
    return node;
}

如图：

当父节点为3-node

那么3-node会变成4-node

这三种情况都是先color flip操作，然后就变成了之前的操作，左旋和右旋。

总结：

向空节点插入一个节点，一定为红节点

如果出现了4-node的情况，我们我们就进行color flip

调整右倾的节点(左旋转)

对连续的两个红节点进行转换(右旋转)

public TreeNode<T> insert(TreeNode<T> node, T data) {
    if (node == null) { //如果是个空节点，则创建红色节点
        return new TreeNode<T>(data, RED);
    }
    if (isRed(node.left) && isRed(node.right)) {// 4-node节点
        colorFlip(node);
    }
    int result = node.data.compareTo(data);
    if (result == 0) {
        node.data = data;
    } else if (result > 0) {
        node.left = insert(node.left, data);
    } else if (result < 0) {
        node.right = insert(node.right, data);
    }

    if (isRed(node.right)) { // 需要左旋转
        node = rotateRight(node);
    }
    if (node.left != null && isRed(node.left) && isRed(node.left.left)) { // 出现两个红节点在一起的情况, 需要右旋转
        node = rotateRight(node);
    }
    return node;
}

2.4 删除

在删除红黑树后，如何调整？

private TreeNode<T> fixUp(TreeNode<T> node) {
    if (isRed(node.right)) {  //如果右倾，左旋转
        node = rotateLeft(node);
    } else if (isRed(node.left) && isRed(node.left.left)) {// 出现两个红节点在一起的情况, 需要右旋转
        node = rotateRight(node);
    } else if (isRed(node.left) && isRed(node.right)) {//如果为4-node则变化颜色
        colorFlip(node);
    }
    return node;
}

2.4.1 删除最大节点

我们都知道最大节点一定是在树的最右叶子节点。

如果我们删除的节点在3-node或者4-node中，我们直接删除掉就可以了。

如果我们删除的节点在2-node中，我们就不能直接删除了，需要借和组合。

删除2-node分为两类：

如果兄弟节点不是2-node，就可以直接从兄弟节点借一个节点过来，组成3-node。

兄弟节点不是2-node，那么可能是3-node或者是4-node，那么此兄弟节点的左子树肯定是红色的。那么如何才能从兄弟节点这里借到一个节点呢？

我们需要右旋转，所以我们需要制造2个相连的红色节点。

因此先对 h 进行 colorFilp，制造了2个相连的红色节点，然后完成右旋转，然后在进行colorFilp，这样就完成了借到节点的效果。

如果兄弟节点是2-node，则从父节点中借一个过来，然后和兄弟节点合并成一个4-node。

既然是最右边的2-node，那么它肯定是黑色的

正好通过 colorFlip 即可将3个节点组成4-node。

将两种情况合并：

private TreeNode<T> moveRedRight(TreeNode<T> node) {
    colorFlip(node);
    if (isRed(node.left.left)) {
        node = rotateRight(node);
        colorFlip(node);
    }
    return node;
}

完整代码如下：

public void deleteMax() {
    root = deleteMax(root);
    root.color = BLACK;
}

private TreeNode<T> deleteMax(TreeNode<T> node) {
    if (isRed(node.left)) {
        node = rotateRight(node);
    }
    if (node.right == null) {
        return null;
    }
    if (!isRed(node.right)  &&  !isRed(node.right.left)) {
        node = moveRedRight(node);
    }
    node.right = deleteMax(node.right);
    return fixUp(node);
}

2.4.2 删除最小节点

与删除最大节点逻辑相同，只是从最右边变成了最左边。

private TreeNode<T> moveRedLeft(TreeNode<T> node) {
    colorFlip(node);
    if (isRed(node.right.left)) {
        node.right = rotateRight(node.right);
        node = rotateLeft(node);
        colorFlip(node);
    }
    return node;
}

public void deleteMin() {
    root = deleteMin(root);
    root.color = BLACK;
}

private TreeNode<T> deleteMin(TreeNode<T> node) {
    if (node.left == null) {
        return null;
    }
    if (!isRed(node.left) && !isRed(node.left.left)) {
        node = moveRedLeft(node);
    }
    node.left = deleteMin(node.left);
    return fixUp(node);
}

2.4.3 删除任意节点

如果所要删除的节点在3-node或者4-node中，根据2-3-4树的性质直接删除就可以了。

最复杂的情况是如果是2-node，那么删除就会引起不平衡。所以就得从兄弟节点中借一个节点，但由于是任意节点，不像删除最大最小的情况，确定是左边或者右边，而是有很多种情况。

我们需要转化思路，如果我们要删除一个节点，我们可以选择用此节点左子树的最大节点或者右子树的最小节点来替换此的值，然后再删除最大节点或者最小节点就可以了。

private TreeNode<T> delete(TreeNode<T> node, T data) {
    int result = data.compareTo(node.data);
    if (result < 0) {
        if (!isRed(node.left) && !isRed(node.left.left)) {
            node = moveRedLeft(node);
        }
        node.left = delete(node.left, data);
    } else {
        if (isRed(node.left)) {
            node = moveRedRight(node);
        }
        if (result == 0 && (node.right == null)) {
            return null;
        }
        if (!isRed(node.right) && !isRed(node.right.left)) {
            node = moveRedRight(node);
        }
        if (result == 0) {
            T temp = min(node.right);
            node.data = temp;
            node.right = deleteMin(node.right);
        } else {
            node.right = delete(node.right, data);
        }
    }
    return fixUp(node);
}

3. 总结

红黑树的用途非常的广泛，如java中常用的TreeMap、TreeSet、jdk8中的HashMap。

我们需要非常了解红黑树的逻辑及其奥秘！

参考

http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf

数据结构 - 树 - 红黑树

1. 介绍

2. 实现

2.1 类定义

2.2 节点定义

2.2 查询

2.3 插入

2.3.1 向2-node节点插入

2.3.2 向3-node节点插入

2.3.3 向4-node插入

2.4 删除

2.4.1 删除最大节点

2.4.2 删除最小节点

2.4.3 删除任意节点

3. 总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

数据结构和算法分析