文章首发于：clawhub.club

数据结构

红黑树本质上是一颗二叉查找树，所以基本结构和二叉查找树是一样的。

二叉查找树的数据结构：

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
/**
 * 二叉查找树节点
 */
private class Node<T> {
    /**
     * 值
     */
    private T value;
    /**
     * 频率,如果value相同，则此值+1，去掉了重复的项
     */
    private int freq;
    /**
     * 父节点
     */
    private Node<T> parent;
    /**
     * 左节点
     */
    private Node<T> left;
    /**
     * 右节点
     */
    private Node<T> right;
}

有根据红黑树的以下五条性质可知，它比二叉查找树多了一个颜色属性。

  1. 每个结点要么是红的，要么是黑的。
  2. 根结点是黑的。
  3. 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。
  4. 如果一个结点是红的，那么它的俩个儿子都是黑的。
  5. 对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

红黑树的数据结构：

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
/**
 * 红黑树节点 <br>
 */
private class Node<T> {
    /**
     * 红色
     */
    private static final boolean RED = false;
    /**
     * 黑色
     */
    private static final boolean BLACK = true;
    /**
     * 值
     */
    private T value;
    /**
     * 频率,如果value相同，则此值+1，去掉了重复的项
     */
    private int freq;
    /**
     * 父节点
     */
    private Node<T> parent;
    /**
     * 左节点
     */
    private Node<T> left;
    /**
     * 右节点
     */
    private Node<T> right;
    /**
     * 颜色
     */
    boolean color = BLACK;
}

查找

红黑树的查找操作和二叉查找树是一样的。
当红黑树查找的时候，先与当前节点进行比较：

  • 如果相等的话就返回当前节点；
  • 如果少于当前节点则继续查找当前节点的左节点；
  • 如果大于当前节点则继续查找当前节点的右节点。

直到当前节点指针为空或者查找到对应的节点
Java代码实现：

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
/**
 * 根节点
 */
private Node<T> root;

/**
 * Search .
 *
 * @param value the value
 * @return node
 */
public Node<T> search(T value) {
    //死循环
    while (true) {
        //如果根节点为null,返回null
        if (root == null) {
            return null;
        }
        //如果根节点的value与待查找value相同，返回根节点的值
        if (root.value.equals(value)) {
            return root;
        } else if (root.value.compareTo(value) < 0) {
            //如果待查找的value 大于 根节点的value,则继续查找根节点 右边 的节点
            root = root.right;
        } else {
            //如果待查找的value 小于 根节点的value，则查找根节点 左边 的节点
            root = root.left;
        }
    }

}

旋转

上一篇19-HashMap源码分析之红黑树-旋转文章中，只介绍了红黑树旋转的理论知识，本次补充一下Java代码实现。
红黑树的旋转.png

左旋转

步骤：

  1. 通过下降节点a,找到上升节点b。（对a左旋转，即以a为圆心的逆时针旋转，a的右子节点b会上升。）
  2. a的右节点指向b的左节点。
  3. 如果b的左节点不为空，则b的左节点的父节点指向a。
  4. 将b的父节点指向a的父节点。
  5. 如果a是根节点,则将b变为根节点。
  6. 如果a是其父节点的左节点，则b成为a父节点的左节点。
  7. 如果a是其父节点的右节点，则b成为a父节点的右节点。
  8. b的左节点指向a。
  9. a的父节点指向b。
    Java代码实现：
    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

    /**
     * 对节点a左旋转,a会变成其右子节点b的左子节点
     *
     * @param a 待旋转节点a
     */
    private void rotateLeft(Node<T> a) {
        //节点为空的时候，返回
        if (a == null) {
            return;
        }
        //获取其右子节点b
        Node<T> b = a.right;
        //节点a的右子节点 指向 b的左节点
        a.right = b.left;
        //如果b的左节点不为空
        if (b.left != null) {
            //b的左节点的父节点指向a
            b.left.parent = a;
        }
        //b的父节点指向a的父节点
        b.parent = a.parent;
        //如果a的父节点为空，则b变为根节点
        if (a.parent == null) {
            root = b;
        } else if (a.parent.left == a) {
            //如果a是其父节点的左节点，则a的父节点的左节点指向b
            a.parent.left = b;
        } else {
            //如果a是其父节点的右节点，则a的父节点的右节点指向b
            a.parent.right = b;
        }
        //b的左节点指向a
        b.left = a;
        //a的父节点指向b
        a.parent = b;
    }

右旋转

算法逻辑可参考左旋转。理解为主。
Java代码实现：

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
/**
  * 对节点b右旋转，b会变成其左子节点a的右子节点
  *
  * @param b 待旋转节点 b
  */
 private void rotateRight(Node b) {
     //待旋转节点b为回
     if (b == null) {
         return;
     }
     //获取b的左子节点a
     Node<T> a = b.left;
     //b的左节点 指向 a的右节点
     b.left = a.right;
     //如果a的右节点不为空
     if (a.right != null) {
         //a的右节点的父节点指向b
         a.right.parent = b;
     }
     //a的父节点指向b的父节点
     a.parent = b.parent;
     //如果b的父节点为null,则a成为根节点
     if (b.parent == null) {
         root = a;
     } else if (b.parent.left == b) {
         //如果b是其父节点的左节点，则其父节点的左节点指向a
         b.parent.left = a;
     } else {
         //如果b是其父节点的右节点，则其父节点的右节点指向a
         b.parent.right = a;
     }
     //a的右节点指向b
     a.right = b;
     //b的父节点指向a
     b.parent = a;
 }