红黑树

2017-03-26

简介

以下内容来自 Algorithms 3.3 Balanced Search Trees.。

要理解红黑树,首先需要理解 2-3 树。对于普通的二叉搜索树,其平均搜索时间为 $O(logN)$。但是在最差情况下二叉搜索树可能会退化成线性链表,导致搜索时间为 $O(n)$。为了解决这个问题,人们提出平衡搜索树的概念,保证树的任意节点的左右子树高度平衡,这样在最坏情况下搜索时间也是 $(lgN)$。

2-3树

2-3 树是平衡搜索树中的一类,一颗非空的 2-3 树有两类节点:

  • 2-node,包含一个 key 值,和两个指向子树的指针
  • 3-node,包含两个 key 值,和三个指向子树的指针

一颗典型的 2-3 树如下:

2-3 树插入

2-3 树插入比普通二叉搜索树略复杂,首先需要找到要插入的位置:

  • 如果要插入的节点是 2-node,那么就可以插入并将该节点扩展为 3-node
  • 如果要插入的节点是 3-node,那么首先将 key 插入到节点中形成 4-node,接着将节点分成两个 2-node,并将 middle key 插入到父节点中。这样递归向上插入直到父节点是 2-node 或者形成一个新的根节点

一个典型的插入过程如下:

在一颗平衡 2-3 树中,根节点到每个空节点的距离都相同,也就是说所有叶子都在同一层。

Red-Black Tree

红黑树也属于平衡搜索树,其使用 BST 并加上额外的颜色信息表示 2-3 树。定义如下:

The basic idea behind red-black BSTs is to encode 2-3 trees by starting with standard BSTs and adding extra information to encode 3-nodes. We think of the links as being of two different links, red links, which bind two 2-nodes together to represent 3-nodes, and black links, which bind together the 2-3 tree. Specfically, we represent 3-nodes as two 2-nodes connected by a single read link that leans left (on of the 2-nodes is the left child of the other).

基本意思是:如果两个节点由 red link 连接在一起,那么应该将这两个节点合在一起看成 2-3 树中的 3-node;如果两个节点由 black link 连接在一起,那么就应该将这两个节点看成 2-3 树中的两个不同节点(2-node 或者 3-node)。

另一个基于 red link 和 black link 的等价定义为:

  • Red links lean left
  • No node has two red links connected left
  • The tree has perfect black balance: every path from the root to a null link has the same number of black links.

1-1 对应

基于上述定义,那么每颗红黑树都存在一颗对应的 2-3树:

1-1 correspondence

上图展示了如何将一个红黑树转化成 2-3 树。事实上,上图也展示了如何将一个 2-3 树转化成红黑树:将 3-node 节点拆分成两个 2-node,并将其中一个节点作为另外一个节点的子树 。注意这里总是将左边的 key 拆分出来作为左子树,符合 red links lean left 规则。事实上,更通用的红黑树没有限制红节点总是要在左边,所以如果我们将右边的 key 拆分出来作为右子树也是可以的。不过这里需要遵守上述 red links lean left 规定才这么拆分。

着色

因为每个节点与父节点之间只有一条 link,所以我们可以将 link 的颜色存储在节点中:通过 red link 与父节点相连的是红节点;通过 black link 与父节点相连的是黑节点。

When we refer to the color of a node, we are referring to the color of the link pointing to it, and vice versa.

如果定义我们的节点为:

private static final Boolean RED = true;
private static final Boolean BLACK = false;

private class Node {
    Key key;
    Value val;
    Node left, right;
    boolean color;
    int N; //number of subtrees

    Node(Key key, Value val, int N,boolean color) {
        this.key = key;
        this.val = val;
        this.N = N;
        this.color = color;
    }
}

private boolean isRed(Node x) {
    return x != null && x.color == RED;
}

那么红黑节点可以表示为:

旋转

旋转的目的类似于 AVL 树,维持红黑树性质,并使得红黑树保持平衡。旋转可以分为左旋和右旋两种。

左转

可以看到,旋转不但调整了节点位置关系,还调整了颜色关系。类似的,右旋为

右旋

红黑树插入

因为可以将红黑树看成 2-3 树,那么我们可以用 2-3 树的插入来理解红黑树的插入过程。在这里,我们记将要插入的新节点为 $N$,其父节点为 $P$。同时,我们在这里遵守 red links lean left 规则,所以当红节点出现在右子树时,我们需要做一次左旋。

父节点对应 2-node

如果父节点 $P$ 是一个 2-Node,那么其必定是黑色,并且插入后 $N$ 和 $P$ 一起组成 3-node。考虑到 $N$ 有可能插入左边,也有可能插入右边,那么就有两种情况:

  • 如果 $N$ 要插入左边,那么我们把 $N$ 插入就完成了: 2-node left insertion

  • 如果 $N$ 要插入右边,那么我们需要做一次左旋: 2-node right insertion

父节点对应 3-node

如果父节点对应 3-node,那么此时有两个 key,而 $N$ 的 key 可能比这两个 key 都小;在两者之间;比两者都大。所以对应有三种情况:

  • 最简单的情况是 $N$ 的 key 比两者都大,这时将 $N$ 加入到最右边,并进行颜色翻转
  • 如果 $N$ 的 key 比两者都小,那么将 $N$ 加入到最左边,然后做一次右旋再做一次颜色翻转
  • 如果 $N$ 的 key 在两者之间,那么类似将 $N$ 加入到中间,然后做一次左旋再做一次右旋最后做一次颜色翻转

具体插入过程如下: 3-node insertion

当一个黑节点有两个红节点时,虽然这符合红黑树定义,但是该节点却变成了 4-node,这不符合 2-3 树定义。所以我们要做一次颜色翻转。翻转过程如下:

同时,我们还注意到上述插入过程中,每次 b 都变成了红色,但是可能 b 的父节点也是红色,这样就冲突了。所以我们需要将 b 递归向上插入。这个过程等价于 2-3 树中将 4-node 分裂为两个 2-node 并将 middle key 向上递归插入过程。对应过程为:

递归插入的过程中有可能产生新的根,由于颜色翻转的关系,新的根的颜色可能为红色。考虑到红节点会与父节点组成 3-node,但是这一关系对于根节点不成立。所以我们需要设置根节点为黑色。

插入节点代码如下:

public class RedBlackBST<Key extends Comparable<Key>, Value> {

    private static final Boolean RED = true;
    private static final Boolean BLACK = false;

    private class Node {...}

    private Node root;

    private boolean isRed(Node x) {...}

    private Node rotateLeft(Node h) {...}

    private Node rotateRight(Node h) {...}

    private void flipColors(Node h) {...}

    public void put(Key key, Value val) {
        root = put(root, key, val);
        root.color = BLACK;
    }

    private Node put(Node h, Key key, Value val) {
        if (h == null)
            return new Node(key, val, RED);
        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.val = val;

        if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
        if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
        if (isRed(h.left) && isRed(h.right)) flipColors(h);
        return h;
    }
}