红黑树(中):红黑树的数据结构设计


上一节中,我们对红黑树的性质和增删原理进行了详细的分析。接下来,我们尝试自己实现一个红黑树。

1 数据类型设定

首先,我们定义一个泛型类 RBTree<K extends Comparable<K>, V> 表示红黑树,其中 K 表示节点键的类型,V 表示节点值的类型。该类包含 rootcount 两个属性,分别用于表示根节点和节点数。此外,我们可以添加两个常量 REDBLACK,方便表示节点的颜色。

然后,我们在这个类内部声明一个三叉节点类型 Node<K extends Comparable<K>, V>,该静态内部类包含六个属性:key 表示节点的键,value 表示节点的值,leftrightparent 分别表示节点的左子节点、右子节点和父节点,color 属性用于指示节点是否为黑节点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class RBTree<K extends Comparable<K>, V> {

    // 红色常量
    private static final boolean RED   = false;
    // 黑色常量
    private static final boolean BLACK = true;

    /**
     * 根节点
     */
    private Node<K, V> root;

    /**
     * 节点总数
     */
    private int count;

    /**
     * 三叉节点类
     */
    static private class Node<K extends Comparable<K>, V> {
        K key;
        V value;
        Node<K, V> left, right, parent;
        // 默认为黑色
        boolean color = BLACK;

        Node(K key, V value, Node<K, V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }

        K getKey() {
            return key;
        }

        V getValue() {
            return value;
        }

        void setValue(V value) {
            this.value = value;
        }
    }

}
  • 为了声明关键字 K 的可比较性,我们让其继承了 Comparable<K> 接口。
  • 红黑树增删过程很依赖父节点,因此我们选择使用 三叉链表来实现存储结构。

红黑树在增删的过程中,会用到诸如染色、旋转等基础操作,实现如下:

2 节点颜色相关的方法

根据红黑树的性质,普通的叶子节点会有两个黑色的 NULL 叶子节点,因此当 colorOf 传入 node == null 时,需要返回虚拟的 NULL 节点的颜色,即黑色。实现如下:

1
2
3
4
5
6
/**
 * 获取节点颜色
 */
private static <K extends Comparable<K>, V> boolean colorOf(Node<K, V> node) {
    return (node == null ? BLACK : node.color);
}

设置颜色的方法 setColor 可以直接对属性进行赋值,实现如下:

1
2
3
4
5
6
7
/**
 * 设置节点颜色
 */
private static <K extends Comparable<K>,V> void setColor(Node<K,V> node, boolean c) {
    if (node != null)
        node.color = c;
}

3 获取父、子节点的静态方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 获取父节点
 */
private static <K extends Comparable<K>,V> Node<K, V> parentOf(Node<K,V> node) {
    return (node == null ? null: node.parent);
}

/**
 * 获取左子节点
 */
private static <K extends Comparable<K>,V> Node<K, V> leftOf(Node<K,V> node) {
    return (node == null) ? null: node.left;
}

/**
 * 获取右子节点
 */
private static <K extends Comparable<K>,V> Node<K, V> rightOf(Node<K,V> node) {
    return (node == null) ? null: node.right;
}

4 后置节点获取方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * 获取节点 t 的后置节点
 * 即 key 仅大于 t.key 的节点
 * 当 t 存在右子树的情况下,可以用来获取 t 的右子树上的最小节点
 */
static <K extends Comparable<K>,V> Node<K,V> successor(Node<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) { // 如果 t 存在右子树
        /*
            则返回右子树上的最小节点
              t  -> 开始
             / \
          ...   r
               /
              rl
             /
            rll <- 返回这个节点
             \
             ...
        */
        Node<K, V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else { // t 不存在右子树
        /*
            当前节点是父节点的左子节点,则返回其父节点:
                 p
                /
               t
            如果当前节点是父节点的右子节点,则向上递归直到找到作为左子树的根节点,并返回它的父节点:
                 a -> 返回
                /
               b -> 找到 a 的左子树根节点
                \
                 c
                  \
                   p
                    \
                     t -> 开始
        */
        Node<K, V> p = t.parent;
        Node<K, V> ch = t;// 双指针
        while (p != null && p.right == ch) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

5 前驱节点获取方法

实现思路与获取后置节点一样:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * 获取节点 t 的前驱节点
 * 即 key 仅小于 t.key 的节点
 */
static <K extends Comparable<K>,V> Node<K,V> predecessor(Node<K,V> t) {
    if (t == null)
        return null;
    else if (t.left != null) { // 如果 t 存在左子树
        /*
            则返回左子树上的最大节点
               t  -> 开始
              / \
             l   ...
              \
               lr
                \
                 lrr  <- 返回这个节点
                /
              lrrl
        */
        Node<K, V> p = t.left;
        while (p.right != null)
            p = p.right;
        return p;
    } else { // t 不存在左子树
        /*
            如果当前节点是父节点的右子节点,则返回其父节点:
                p
                 \
                  t
            如果当前节点是父节点的左子节点,则向上递归直到找到作为右子树的根节点,并返回其父节点:
                a -> 返回这个节点作为前驱
                 \
                  b -> 找到 a 的右子树根节点
                 /
                c
               /
              p
             /
            t  -> 开始
        */
        Node<K, V> p = t.parent;
        Node<K, V> ch = t; // 双指针
        while (p != null && p.left == ch) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

6 旋转操作

所有类型的二叉排序树的旋转规则都是通用的,在 AVL 树 中我们已经详细介绍过了,这里不再赘述。