红黑树

Table of Contents

最近上下班途中从网易云课堂了下了MIT的算法导论 课程打发时间, 回顾回顾算法, 顺便锻炼一下计算机英语术语. 结合这门课的视频加上手头上的<<算法>> 这本书, 对红黑树又加深了 印象, 记个笔记记录一下.

注:这本书关于红黑树的电子版章节可以在下面的链接找到, 里面有大量的示例图, 方便更形象的了解各种术语. http://algs4.cs.princeton.edu/33balanced/

二叉树实现排序

树是数据结构的一种, 之所以称其为树是因为每个节点都跟多个节点相连, 并且它还有 层级的约束(图的每个节点也和多个节点相连, 但是没有层级的概念). 对于线性的数据结构, 比如数组或链表, 其节点都只有一个前后节点(首/尾节点没有前/后). 一个树节点可以跟多个"下层"节点相连, 但是每个节点只有一个父节点.

二叉树是树的一个特例, 它的附加约束条件为每个节点最多只有两个子节点.

用二叉树实现排序, 规则也很简单, 每个节点的左子树(上的数据)都小于该节点(的数据), 右子树(上的数据)都大于该节点. 基于这个规则可以很容易的将一组数据转使用二叉树 排序, 即二叉搜索树. 例如下面的代码就将一个新数据插入到一个现成的二叉搜索树中.

class Node(){
    int data;
    Node left;
    Node right;
}

void insert(Node root, Node newNode) {
    Node cur = root;

    while(cur != null) {
        if(newNode.data < cur.data) {
            if(cur.left == null) {
                cur.left = newNode;
                break;
            }
            cur = cur.left;
        } else {
            if(cur.right == null){
                cur.right = newNode;
                break;
            }
            cur = cur.right;
        }
    }
}

上面的代码很简单, 首先定义了一个Node类, 代表树的节点, 然后定义了插入算法 insert, 将一个新节点 newNode 插入到根节点为 root 的二叉搜索树中. 对树的遍历都是"折半" 进行的,如果新节点的数据小于当前节点, 则转移到左子树去寻找, 否则转移到右子树 去寻找. 直到找到底部该插入的位置, 则插入.

二叉树排序数据的展示可以通过"中序遍历"树的方式实现, 即先递归遍历左子树, 输出, 然后输出当前节点, 然后递归遍历右子树输出. 代码如下:

void preorderTraverse(Node root) {
    if(root == null) return;

    preorderTraverse(root.left);
    print(root.data);
    preorderTraverse(root.right);
}

基本二叉树的缺陷

上述的二叉搜索树有一个缺陷, 即会出现树"失衡"的情况. 失衡一般是指 树的左右子树的高度差距太大. 以上面的算法举例来说, 对于组已经排好序的 数据, 例如 {5, 7, 8, 11, 14, 20, 44, 52}, 如果以第一个节点作为根节点 来创建树, 那么这个数组中的每个数都会成为前一个数的右节点, 最后就变成了一个"线性树".

所以在不了解所要处理的数据的"有序度"的情况下, 如果使用简单的二叉搜索树 来实现排序, 坏情况下效率也会很糟.

2-3树

为了解决上面所提到的缺陷问题, 科学家们做了很多研究. 一个基本的思路就是不能简单的插完节点之后就什么都不管了, 而是应该做一些额外的操作来维持树的"平衡". 2-3树就是其中的 一种解法.

二叉树时讲到每个节点只能存放一个数据, 并且最多只能有两个 子节点. 而2-3树则是这样一种结构: 每个节点最多可以存放两个数据, 并且每个节点最多可以有三个子节点. 当一个节点只存放了一个数据时, 称该节点为"2-"节点(表示它只有两个分支), 当一个节点存放了两个数据时, 称其为"3-"节点, 代表其有三个分支.

对于一个"3-"节点来说, 设其中的两个数据为 X,Y. 设其三个分支为left, middle, right. 那这五者之间的关系为:

  1. X < Y.
  2. left 子树的数据都小于 X.
  3. middle 子树的数据大于X且小于Y.
  4. right 子树的数据都大于Y.

2-3树的规则维持

2-3树的数据插入并不想前面的二叉树那么简单, 因为2-3的目的是"尽量" 维持平衡性, 所以在插入一个新节点时, 要根据插入位置情况来做操作. 可能出现的情况包括:

  1. 父节点是一个 "2-" 节点, 那么直接将新节点跟父节点合并成一个 "3-" 节点即可. 这样就没有增加子树的高度, 所以没有破坏树的平衡性.
  2. 父节点是一个 "3-" 节点. 可以先将新节点跟这个 "3-" 节点结合, 行程一个 临时的的 "4-" 节点. 所谓 "4-" 节点, 就是其节点内部存了三个数据, 而且其 有4个分支. 基于"3-"节点, 可以很容易推导出 "4-" 节点之间数据和分支的关系. 对于这个新的 "4-" 节点, 它所在的 2-3 可能有以下情况:
    1. 这个树中只有这一个 "4-" 节点. 那样的话, 可以将该节点分成3个 "2-" 节点, 其中存放 "中位数" 的节点当作根节点, 最小数的节点当左节点, 最大数节点 当右节点. 这样不会破坏树的平衡性, 只是将树的高度增加了1.
    2. 这个临时 "4-" 节点的父节点是 "2-" 节点, 可以将 "4-" 节点的中位数提出来 放到 "2-" 节点中行程一个新的 "3-" 节点, 然后将 "4-" 的最小数提成一个 "2-"节点作为新 "3-" 节点的 "中链接". "最大数"提成一个 "2-" 节点作为 新 "3-" 节点的 "右链接".
    3. 临时 "4-" 节点的父节点是 "3-" 节点, 可以将 "中位数" 提出来放到父节点中, 使父节点变为一个临时的 "4-" 节点. 剩下的两个数拆成两个"2-"节点(跟上一步一样). 由于此时父节点已经变成了 "4-" 节点, 所以要继续向上一层看这个新的 "4-" 节点的父节点的情况. 其实就是递归向上回溯, 直到根节点. 如果最后根节点 也被转化成了一个 "4-" 节点, 则依据第一步的做法将其拆分. 这个不断向上回溯 的过程并没有破话"2-3"树的性质, 如果在上溯过程中遇到一个 "2-" 节点, 那么 只是将其转化成了 "3-" 节点, 树的高度都没有增加. 唯一增加树高度的情况就是 根节点也变成 "4-" 节点的情况.

这就是2-3树的情况, 它的一个良好的性质就是树的平衡性很好. 不会像一般的二叉搜索树那样, 在最坏情况下会变成"线性树".

红黑树

具体到代码实现层面上, 如果按照上述的理论进行编程, 2-3树的实现会比较麻烦, 因为其涉及到了"三种"数据结构: "2-", "3-", "4-". 并且需要在这三种结构之间来回切换. 这种状态维护会很麻烦. 聪明的科学家们为了解决这个问题, 在二叉树的基础上, 通过给节点添加附加信息的方式, 创造了一种新的结构, 叫做红黑树.

红黑树的红黑可以理解为节点的颜色(在 算法 这本书中, 红色被 理解成链接的颜色, 其实都是一样的). 可以总是将一个红色节点和 其父节点放到一起对待, 它们本质上就是上面提到2-3树的 "3-" 节点. 因为2-3树最多只有"3-"节点, 所以可以推理出红黑树的一些规则:

  1. 红色节点不能有红色子节点. (这样会形成 "4(或>4)-" 节点).
  2. 黑色节点左右节点不能同时为红色. (这样会形成 "4-" 节点).

另外还有如下规则:

  1. 根节点必须为黑色节点.
  2. 红色节点必须为其父节点的左子节点. (因为两个子节点不能同时为红色, 所以约束左子节点为红色可以便于维护代码).

红黑树的规则维持

既然红黑树本质上可以是2-3树, 那么基于2-3树的平衡维护规则同样可以推导出 红黑树的规则维持. 红黑树规定新插入节点的颜色必须是红色, 因为前面讲过 红节点可以和其第一个祖父节点结合, 形成2-3树中的 "3-" 或 "4-" 节点, 所以我们 可以很方便的使用2-3树的平衡规则.

一个新插入的红节点可能会是以下几种情况:

  1. 它是红黑树的第一个节点, 那么只要将其变为黑色即可.
  2. 它的父节点是黑节点, 且它是父节点的左子节点. (形成一个 "3-" 节点) 这种情况完全没有破坏红黑树的规则, 保持不变即可.
  3. 父节点是黑节点, 且它是父节点的右子节点, 且父节点的左子节点是黑色. 这样仍然可以形成 "3-" 节点, 但是破坏是红黑树的规则4. 所以需要进行修正, 修正的方法为对父节点进行左旋转.
  4. 父节点是黑节点, 且它是父节点的右子节点, 且父节点的左子节点是红色. 修正方法为将左右子节点都设为黑色, 然后父节点设为红色. 这就相当于2-3树中对 "4-" 节点的修正方法, 即中位数上移, 这里的中位数 就是该情况下红黑树中的父节点, 将其上移的方法就是使其成为红节点 (因为红节点和父节点是可以"合并"在一起). 由于父节点变成了红色,有可能破坏了 红黑树的规则, 所以要上溯修改, 直到符合规则.
  5. 父节点是红节点, 该节点是父节点的左子节点. (基于规则, 该父节点一定是其父节点的左子节点). 形成了一个 "4-"节点, 按照2-3树的修改规则将中位数上移. 具体到红黑树, 修正方法为:
    • 对父节点进行右旋转, 旋转后变为父节点有两个红色节点(祖父节点选择后变为父节点的右子节点).
    • 将左右节点的颜色变成黑色, 父节点的颜色变成红色.这就变成了上一步的情况. (中位数上移,bingo).
    • 变成了4的情况, 递归上溯处理新红节点. 处理到根节点变成红色, 则直接置黑.
  6. 父节点是红节点, 该节点是父节点的右子节点. 同样是"4-"节点的处理规则, 只不过这次的中位数是新插入的红节点,所以要一步一步 将其上移, 具体的修正规则为:
    • 对父节点进行一次左旋转. 旋转后新节点成了祖父节点的左子节点, 父节点成了新节点的左子节点.
    • 对新节点进行一次右旋转. 旋转后新节点放到了祖父节点的位置, 父节点和祖父节点成立左右节点.
    • 变成了4的情况, 递归上溯处理新红节点. 处理到根节点变成红色, 则直接置黑.

左旋转

对一个节点进行左旋转, 就是

  1. 把节点的右子节点放到节点的当前位置, 并将其颜色变成该节点的颜色.
  2. 把节点变成其右子节点的左子节点, 并将颜色设为红色.

右旋转

对一个节点进行左旋转, 就是

  1. 把节点的左子节点放到节点的当前位置, 并将其颜色变成该节点的颜色.
  2. 把节点变成其左子节点的右子节点, 并将颜色设为红色.

红黑树Java实现

通过前面红黑树一节的描述, 应该不难实现其代码. 这里使用了Java代码.

下面代码是节点的实现, 每个节点被创建是都被设成了红色, 因为红黑树的规则维持 需要上溯, 所以定义了一个变量parent指向其父节点.

private class Node {
    int data;           //存放的数据
    int color;          //该节点颜色(也可以理解为其父节点到该节点的链接的颜色)
    int blackHeight;    //该节点的黑高度

    Node left;    //左子树
    Node right;   //右子树
    Node parent;  //指向父节点

    Node(int data) {
        this.data = data;
        color = RED;
        blackHeight = 0;
    }
}

下面代码是左旋转右旋转的代码, 注意这里要修改多个"指针", 尤其是parent. 同时也要注意旋转后root是否也需要修改的问题. 链表操作比较熟练的话应该没什么问题.

private Node rotateLeft(Node node) {
        Node right = node.right;
        if (root == node) {
            root = right;
        }

        node.right = right.left;
        if(node.right != null) {
            node.right.parent = node.parent;
        }

        right.left = node;
        right.parent = node.parent;
        node.parent = right;

        //更改parent
        if (right.parent != null) {
            if (right.parent.left == node) {
                right.parent.left = right;
            } else {
                right.parent.right = right;
            }
        }

        right.color = node.color;
        node.color = RED;

        return right;
    }

    private Node rotateRight(Node node) {
        Node left = node.left;
        if (root == node) {
            root = left;
        }

        node.left = left.right;
        if(node.left != null) {
            node.left.parent = node.parent;
        }

        left.right = node;
        left.parent = node.parent;
        node.parent = left;

        if (left.parent != null) {
            if (left.parent.left == node) {
                left.parent.left = left;
            } else {
                left.parent.right = left;
            }
        }

        left.color = node.color;
        node.color = RED;

        return left;
    }

下面是红黑树的主要代码, insert()和resetTree()函数用于完成新节点的插入和插入后 红黑树的规则维持, 这里使用了一个while循环来进行一次维持后的上溯.

/**
 * 红黑树(Red-Black Tree)
 */
public class RbTree {
    private static final int[] DATA = {19, 7, 30, 18, 11, 22, 3, 25, 26, 38, 20};
    private static final int BLACK = 0;
    private static final int RED = 1;

    private Node root;

    /**
     * 基于数组构造红黑树
     */
    public void build(int[] data) {
        for (int i = 0, len = data.length; i < len; i++) {
            Node newNode = new Node(data[i]);
            insert(newNode);
        }
    }

    /**
     * 将新节点插入到root代表的红黑树,
     * 新节点的颜色会先被设置为红色, 然后基于排序规则插入到红黑树,
     * 如果插入后破坏了红黑树的任意规则, 则需要对红黑树进行重置
     */
    public void insert(Node newNode) {
        //第一个节点设为root
        if (root == null) {
            root = newNode;
            root.color = BLACK;
            return;
        }

        //先将节点根据排序插入到指定的位置
        Node cur = root;

        //根据数据的大小先将新节点插入到"应该插入"的位置,
        //注: 这有可能破坏红黑树的规则
        while (cur != null) {
            if (newNode.data < cur.data) {
                if (cur.left == null) {
                    cur.left = newNode;
                    newNode.parent = cur;
                    break;
                }
                cur = cur.left;
            } else {
                if (cur.right == null) {
                    cur.right = newNode;
                    newNode.parent = cur;
                    break;
                }
                cur = cur.right;
            }
        }

        resetRbTree(newNode);
    }

    /**
     * 如果一个节点的左右节点都为红色, 该使用该方法修改这个子树的
     * 结构, 将两个子节点都改为黑色, 并且将该节点改为红色.
     *
     * @param node
     */
    private void flipColor(Node node) {
        node.left.color = BLACK;
        node.right.color = BLACK;
        node.color = RED;
    }

    /**
     * 重置红黑树, 因为新插入的节点可能会破坏红黑树的规则,
     * 所以每次插入一个节点后都要看是否需要重置红黑树
     */
    private void resetRbTree(Node newNode) {
        Node cur = newNode;

        //提示, 这里父节点永远是其父节点的左节点
        while (cur != root && cur.color == RED) {
            Node p = cur.parent;

            //没有破坏红黑树, 直接返回
            if (p.color == BLACK && cur == p.left) {
                break;
            }

            //父节点是黑点, 且新节点是父节点的右节点
            else if (p.color == BLACK && cur == p.right) {
                //如果父节点的左节点也为红色, 则说明父节点的左右节点都为红色
                if (p.left != null && p.left.color == RED) {
                    flipColor(p);
                    cur = p;
                    continue;
                } else {
                    rotateLeft(p);
                    break;
                }
            }

            //父节点是红色,
            else if (p.color == RED) {
                Node pp = p.parent;

                //新节点是父节点的左节点, 先右旋转, 再flip
                if (cur == p.left) {
                    cur = rotateRight(pp);   //祖父节点右旋
                    flipColor(cur);
                } else {
                    //新节点是父节点的右节点, 先左旋转, 再右旋转, 再flip
                    rotateLeft(p);
                    cur = rotateRight(pp);
                    flipColor(cur);
                }
            }
        }

        if (cur == root && cur.color == RED) {
            cur.color = BLACK;
        }
    }

红黑树Elisp实现(待完成)

Created At <2016-03-19 Sat> by Luis Xu. Email: xuzhengchaojob@gmail.com