红黑二叉查找树（原理、实现）

2018-07-28 本文已影响73人 yifyif

转载请注明出处！https://www.jianshu.com/p/d9d9f223f0ad

Github源码地址

此篇需要二叉树基本知识，若对二叉树不了解，请移步一篇文章搞懂二叉树！

Welcome back!

在了解了二叉树的基本知识后，我们知道，二叉树虽然可以在一般情况下控制比较次数在logN内结束，但是一旦遇到较差的情况，导致树的高度很高的时候，性能就不是很令人满意了。另外，对于插入过程中保持二叉树的完美动态平衡这一操作，代价又显得太高了。所以，我们稍微放松点完美平衡的要求，将操作的性能保持在logN内完成即可。

下面，在正式学习红黑二叉树之前，我们先学习另一种树形结构“2-3查找树（B-树）”。这种树形结构也是红黑二叉树形成的历史由来，掌握它非常简单，并且能更好的帮助我们理解红黑二叉树。

2-3查找树

2-3查找树只是高级数据结构B-树中非常简单的一种情况。之前二叉树中了解到，操作的复杂度与树的高度成正相关。那么在如何维持树的高度和平衡性，我们这里需要一些灵活性。

我们允许二叉树中的一个结点保存多个键值
我们将标准二叉树中的结点（1个键值）称之为2-结点。
我们将含有2个键值和3个连接线（连接子结点）的称之为3-结点。

一个2-3查找树或是一个空树，或是由下列结点组成：

2-结点：含有1个键与2条连接线的结点，其与标准二叉树的结点性质一样，x.left < x < x. right。

3-结点：含有2个键与3条连接线的结点，其中左连接线都小于2个键，中连接线在2个键之间，右连接线都大于2个键。

2-3树结构示意图

一个完美的2-3平衡树，它的所有空链接到根节点的距离应该是相同的。

2-3树查找 get：

设查找的键为key，查找的节点为x。与二叉树相似：

若未命中，则返回null。
若 key < x.key , 在x的左子树中寻找。
若 key > x.key , 在x的右子树中寻找。
若结点x是2-结点，则与二叉树一样。
若结点是3-结点，则比较key与2个键的大小，看是直接命中还是在哪个连接线继续寻找。

2-3树查找

2-3树插入 put：

先进行一次未命中查找。如果命中，则替换value。如果没有命中，则创建新结点挂在树的底部。

向2-结点 h 中插入

直接挂在树的底部会有些问题，破坏了树的平衡性，我们想要保持插入也是平衡的，所以选择结点上变化。那么分两种情况：

如果h无子结点或h的子结点是2-结点，则与二叉树一样插入，2-结点变3-结点。

结点为2结点插入
如果h的子结点是3-结点，则3-结点变成4-结点了。（见下）

向3-结点 h 中插入

如果向只含有一个3-结点的树插入，则3-结点变4-结点。这个情况则需要稍微变形处理下，可以将4-结点转化为2个2-结点。

规定：4-结点中有3个键，4个连接线。中间的键可以提到上面，成为左右两个键的父结点，此时树的高度+1。由于变换的是根节点，依然维持了完美平衡性。

4-结点转化为2个2-结点
理解树的变化是非常重要的，这关乎2-3树如何成长。

如果向父结点为2-结点的3-结点 h插入（接上），则3-结点变4-结点。变换后，提上来的中间键与父结点合并，注意，此时仍要保持父结点内键的大小顺序。

父结点为3结点插入
如果向父结点为3-结点的3-结点 h插入，则子结点变为4-结点，变换后父结点也变为4-结点，则再次向上变换，直至没有4-结点。

父结点为3-结点
如果插入的路径向上全是3-结点，则我们的根节点变为临时的4-结点，此时我们可以向情况1.中所描述的处理，分解4-结点，树的高度+1。

根节点为4-结点

请注意，2-3树中任何4-节点的分解与转化，均是局部操作，不会影响到树的平衡性！
只要符合相应的形态，变换即可进行。

2-3树性能：

2-3树的高度必然在 (logN)/(log3) ~ logN 之间，故增删查改的性能也在 O[ (logN)/(log3) ]~ O( logN ) 之间。

OK，2-3树的介绍就到这里，代码没写，因为我们的重点不是2-3树，而是红黑树。现在我们离红黑树只差一句话的距离了。当然，在告别2-3树之前，我们再看一眼2-3树的完美身影 :) 。

一般的2-3树，优雅，美丽，请记住她！

（喝口水，休息一下）

红黑二叉查找树

首先，让我们来去掉3-结点，就从2-3树变成了红黑树。
本质上，红黑树就是利用标准二叉树中结点的额外信息表示2-3树。所以，红黑树是一个二叉树，或者说，红黑树是二叉树的子类（不太准确的说法）。

去掉3-结点

上面说的结点的额外信息，其实就是指的（结点）链接的颜色。在标准二叉树中，所有链接的颜色都是黑色，而在红黑树中，我们规定有红色和黑色两种链接。
注：不少教科书上都是用结点为红/黑来定义红黑树，这里采用的是另一种定义规则，并不冲突。

黑链接是2-3树中的普通链接，也是标准二叉树中的链接。
红链接是将两个2-结点，变为一个3-结点。

所以，我们只需要将3-结点还原成由红链接连接的2个2-结点，即可去掉3-结点！而对于3-结点的子结点，则分配给两个2-结点来完成。

红链接是将两个2-结点，变为一个3-结点

等价定义

我们这里为了方便讨论情况，不影响性质的前提下，定义以下规则：

一个静态的红黑树：（不需要再变换的、操作完成后的）

所有红链接均为左链接

没有任何一个结点与两个红链接相连

该树是完美黑色平衡的，即任意空结点到根结点的路径上黑链接数量相同！（黑链数目既是树的高度）

肯定有小朋友对上面三条规则不满的，这边我来解释一下：

前提是变换好的红黑树。
红链接为右链接可不可以，我说可以，但是为了统一和美观，以及减少讨论的情况和复杂度，我们统一规定左边。
为啥不能两个红链接相连？两个红链接相连其实就产生了4-结点，这在2-3树中是会被转化的，而我们红黑树是由2-3树演变而来，所以应该通过相应的转化变换解决这个问题，后面会有介绍方法，且听我细细说来。
因为完美平衡二叉树是黑色平衡的，所以我们红黑也是完美黑色平衡的。或者等会你就能明白，为什么我们不计入红色为树的高度了，看下面。

红黑树与2-3树一一对应

注意这里红链接横置后的连接顺序，没有改变

我们将红黑树中，所有的红链接都横过来画（或者说，将2-3树中所有3-结点内部都加上红链接），即显示了为何红黑树也是2-3树，并且红黑树的高度就是2-3树的高度，也就是空结点到根节点路径上普通黑链接的数量。

红黑树既是二叉树，也是2-3树。
所以我们在红黑树中可以使用2-3树高效的插入算法，以及二叉树中高效的查找算法。

结点构成及颜色表示

boolean RED = true
boolean BLACK = false

我们在二叉树的基础上，加入了结点的颜色来表示指向当前结点的链接颜色。

C和G的颜色是红的，E和J不是

    private class Node {
        private Node left;
        private Node right;
        private boolean color = BLACK;
        private Key key;
        private Value value;
        private int size;

        public Node(Key key, Value value, int size, boolean color) {
            this.key = key;
            this.value = value;
            this.size = size;
            this.color = color;
        }
    }
    
    private boolean isRed(Node h) {
        if (h == null) return false;
        return h.color;
    }

旋转 rotate：

为了将我们所有的红链接都能自由的左右旋转，于是有以下两个方法：假设结点为 h

向左旋转 rotateLeft：

左旋可以将红链从右边移至左边。
这个方法多数用于删除操作和调整树的平衡，以满足我们的等价定义。

左旋前

左旋后
当然从视觉上来看就是h 的右子结点不动，h 自己旋转至左下方，同时，交换子结点和红链。

旋转后需要重置父结点的链接。
旋转后需要调整结点的大小，因为结点的高度变化了。

    private Node rotateLeft(Node h) {
        if (h == null) throw new IllegalArgumentException();
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = x.left.color;//x.color = h.color
        x.left.color = RED;
        x.size = h.size;
        h.size = 1 + size(h.left) + size(h.right);
        return x;
    }

向右旋转 rotateRight：

右旋可以将红链从左边移至右边。
这个方法多数临时用于删除操作中，后面我们会介绍删除操作。

右旋前

右旋后
操作与左旋完全相反，不再赘述。

    private Node rotateRight(Node h) {
        if (h == null) throw new IllegalArgumentException();
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = x.right.color;//x.color = h.color
        x.right.color = RED;
        x.size = h.size;
        h.size = 1 + size(h.left) + size(h.right);
        return x;
    }

插入 put：

红黑树的插入是为数不多的比较复杂的实现之一（还有就是删除），联系2-3树，这里我们先分情况讨论：

规定：插入的新结点的color都是RED
这个只要想想2-3树中插入就明白了。

向单个2-结点中插入新键：

如果一个红黑树只有一个2-结点，即根节点root，那么插入的时候会有三种情况：

key == root，替换root 的值。
key < root，则插入左子结点，此时不需要调整。
key > root，则插入右子结点，此时为了满足等价定义，rotateLeft一下就好了。

向树底部的2-结点插入新键：

和上面三个情况差不多，只要保证我们的等价定义，以及二叉树的基本定义（x.left < x < x.right），调整并更新父链接就好啦。

向一个双键树（3-结点）插入新键：

分以下三种情况：

1. 新插入的键最大：

插入右子结点x.right。则形成4-结点，此时需要进行变换。这里介绍一个flipColors方法，用来分解4-结点：

一个键h 的左右子结点都是红色，h 为黑色。
将h 的左右子结点都变为黑色，h 变为红色。
此时树的高度+1。
调整后的h 可以根据其他情况进行继续变换。

变换前

变换后

    private Node flipColors(Node h) {
        if (h == null || h.left == null || h.right == null) throw new IllegalArgumentException();
        h.color = !h.color;
        h.left.color = !h.left.color;
        h.right.color = !h.right.color;
        return h;
    }

2. 新插入的键最小：

插入左子结点的子结点 x.left.left，则此时形成连续的左链接都是红色(A 插入 B-C ，形成 A-B-C)。
这时候需要我们先对C进行右旋 rotateRight(C)，然后就形成了上面1.的情况。

旋转后flip

3. 新插入的键大小在两个键之间：

插入左子结点的右结点 x.left.right，这种情况最为复杂。例如B插入A-C
此时需要先对A进行左旋 rotateLeft(A)，然后就形成了上面2.的情况。

新插入的键大小在两个键之间

由此我们可以看出，插入总是在“ 情况3 -> 情况2 -> 情况1 ”之间转化。

请确保完全理解了上述中树的变化，再继续看下去。

根节点总是黑色

当我们进行插入后，根节点有时候会变为红色，此时当根节点由红色转为黑色时，树的高度+1。

代码实现：

插入的实现，可以参考2-3树，这里只是在插入完成后，重新调整树的结构以达到完美平衡，满足等价定义。

    public void put(Key key, Value value) {
        root = put(root, key, value);
        root.color = BLACK;//根节点总是黑色
    }

    private Node put(Node h, Key key, Value value) {
        if (key == null) throw new IllegalArgumentException();
        //创建新子结点，颜色为红色
        if (h == null) return new Node(key, value, 1, RED);

        int comp = key.compareTo(h.key);
        if (comp > 0) h.right = put(h.right, key, value);
        else if (comp < 0) h.left = put(h.left, key, value);
        else h.value = value;

        //插入完成后重新调整树以满足等价定义
        if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);//情况3 -> 情况2
        if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);//情况2
        if (isRed(h.left) && isRed(h.right)) h = flipColors(h);//情况1

        //调整完成后需要重新计算树的高度
        h.size = size(h.left) + size(h.right) + 1;
        return h;
    }

删除 delete：

删除任意一个键，是红黑树中最为复杂的算法。而在删除任意结点的时候，我们先想想二叉树中是如何进行删除操作的。

当x不是树的末结点，若直接删除会造成空缺，树不连续，我们需要变换一下。
则当x不是树的末结点且x有两个子结点时：
删除x后，需要寻找x的右子结点中最小的（或者x的左子结点中最大的）来代替x的位置，保证二叉树的性质“每个结点的键都大于任意左子节点而小于任意右子节点”。

故我们可以这样理解，最复杂的情况下，假设x不是树的末结点且x有两个子结点：
如果我们将x先和右结点最小的（或者左结点最大的）进行交换，然后就将x变为树的末结点，此时即可直接删除。

所以，删除的操作可以简化为 删除最小值 或 删除最大值 的操作。

删除最小值 deleteMin：

由二叉树性质可知，最小键一定是在树的最左边。并且由等价定义可知，最小值一定是在树的末端最左边。

当我们进行删除末结点的时候，让我们先回归2-3树，并且稍微允许临时4-结点的存在。

有时候为了让父结点变为红色，需要临时合并为4-结点。
如果删除的末结点是3-结点，则直接删除即可。
如果删除的末结点是2-结点，直接删除会破坏树的完美平衡。所以此时我们需要进行变换。

分以下几种情况：

如果此时要删除的结点，它的父结点、兄弟结点（父结点的右结点）都是2-结点，则可以将这三个结点flipColors，还原为一个临时的4-结点。这样在我们删除后，依然是3-结点，不会破坏完美平衡，高度-1。
情况1.父结点、兄弟结点都是2-结点

如果它的父结点不是红色，则想办法变为红色。

如果此时要删除的结点，它的父结点是2-结点，而它的兄弟结点不是2-结点，则此时需要向兄弟结点借一个结点过来，形成3-结点。

从兄弟结点中借一个结点，e可有可无
如果此时要删除的结点，它的父结点不是2-结点，那么从父结点借一个结点过来，形成3-结点。

两种情况，分别是兄弟结点是否为2-结点

若兄弟结点不是2-结点，则从父结点借一个结点后，兄弟结点可以补给父结点一个最小的结点，保持树的完美平衡性。
若兄弟结点是2-结点，则父结点中最小的结点向下合并，形成临时4-结点。

待删除完成后，需要自下而上重新整理树的结构，将所有的临时4-结点分解，从而满足我们的等价定义。

代码实现：

沿着树的最左路径，一路向下的过程中，当遇到2-结点，实现一些变换moveRedLeft()，从而保证当前结点不是2-结点。
这里也就是想办法变红色，从而能够删除键而不破坏树的完美平衡。

    private Node moveRedLeft(Node h) {
        //假设h为红色，h.left 和h.left.left都是黑色（h.left和h.left.left都是2-结点）
        //将h.left 或h.left 的子结点之一变红（想办法变红，变为3-结点）
        flipColors(h);//这个方法可以在拆分4-结点和组合4-结点之间变换。

        if (isRed(h.right.left)) {
        //兄弟结点为非2-结点，此时经旋转，将红键从右往左传递。见下图。
            h.right = rotateRight(h.right);
            h = rotateLeft(h);
        }
        return h;
    }

moveRedLeft 过程

    public void deleteMin() {
        if (isEmpty()) throw new NoSuchElementException();
        if (!isRed(root.left) && !isRed(root.right))
            root.color = RED;
        root = deleteMin(root);
        if (!isEmpty()) root.color = BLACK;
    }

    private Node deleteMin(Node h) {
        if (h.left == null) return null;
        if (!isRed(h.left) && !isRed(h.left.left))
            h = moveRedLeft(h);
        h.left = deleteMin(h.left);
        return balance(h);//自下而上重新整理树的结构。
    }

一开始，如果根节点的两个子键都没有红键，则需要我们临时将根节点变红，从而可以拆分出红键。
而在删除完成最后，如果树还有结点，则要将根节点还原为黑色，以满足根节点总是黑色。
其中balance()方法与之前我们进行put后的操作类似，不再赘述。

    private Node balance(Node h) {
        if (!isRed(h.left) && isRed(h.right)) h = rotateLeft(h);
        if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
        if (isRed(h.left) && isRed(h.right)) flipColors(h);
        h.size = size(h.left) + size(h.right) + 1;
        return h;
    }

删除最大值 deleteMax：

由于我们的红链都是左链，所以这里与deleteMin稍有不同。

沿着树的最右路径，一路向下的过程中，当遇到2-结点，实现变换moveRedRight()，从而保证当前结点不是2-结点。

    private Node moveRedRight(Node h) {
        //假设h为红色，h.right 和h.right.left都是黑色（h.right和h.right.left都是2-结点）
        //将h.right 或h.right 的子结点之一变红（想办法变红，变为3-结点）
        flipColors(h);
        if (!isRed(h.left.left))//两个子结点均为2-结点
            h = rotateRight(h);
        return h;
    }

两个子结点都是2-结点的删除示意

如图示不难理解，由于我们删除的是最大值，所以键一定在右子结点中，故要将红键从左往右传递。其与操作与deleteMin差不多，就不赘述了。但是要记住，我们这些局部的旋转和移动都不会改变树的组成（见2-3树性质）。

    public void deleteMax() {
        if (isEmpty()) throw new NoSuchElementException();
        if (!isRed(root.left) && !isRed(root.right))
            root.color = RED;
        root = deleteMax(root);
        if (!isEmpty()) root.color = BLACK;
    }

    private Node deleteMax(Node h) {
        if (isRed(h.left))//由于我们删除的键总在右子结点中
            h = rotateRight(h);
        if (h.right == null) return null;

        if (!isRed(h.right) && !isRed(h.right.left))//h.right是个2-结点
            h = moveRedRight(h);//此时将红键从左向右传递
        h.right = deleteMax(h.right);
        return balance(h);
    }

删除任意结点的实现：

删除任意结点就是转为为删除最小值和删除最大值的操作。

    public void delete(Key key) {
        if (key == null) throw new IllegalArgumentException();
        if (isEmpty()) throw new NoSuchElementException();
        if (!isRed(root.left) && !isRed(root.right))
            root.color = RED;
        root = delete(root, key);
        if (!isEmpty()) root.color = BLACK;
    }

上面这段代码就不解释了，和之前deleteMin的原因一样。我们主要看下面的具体实现。

    private Node delete(Node h, Key key) {
        if (key.compareTo(h.key) < 0) {
            if (!isRed(h.left) && !isRed(h.left.left))
                h = moveRedLeft(h);
            h.left = delete(h.left, key);
        } else {
            if (isRed(h.left))
                h = rotateRight(h);
            if (key.compareTo(h.key) == 0 && h.right == null)
                return null;
            if (!isRed(h.right) && !isRed(h.right.left))
                h = moveRedRight(h);
            if (key.compareTo(h.key) == 0) {
                h.value = get(h.right, min(h.right).key);
                h.key = min(h.right).key;
                h.right = deleteMin(h.right);
            } else h.right = delete(h.right, key);
        }
        return balance(h);
    }

如果寻找的键在左边，则消除左边路径上的2-结点，参考deleteMin。
如果寻找的键在右边，则消除右边路径上的2-结点，参考deleteMax。
我们在这里主要采用的是寻找右子键中最小值来交换自己的位置，此时待删除结点就从树的中间部分被交换到了树的末端，从而删除右子键中的最小值，简化为删除最小值的问题。
最后也要记得自下而上整理整个树的结构，满足我们的等价定义。

删除B的简易示意图

性能：

无论我们如何插入键值，红黑树都是几乎完美平衡的。

这个可以通过我们2-3树的性质得到。

大小为N的红黑树的高度不会超过2logN。

所以其操作复杂度始终维持在 ~O(logN)。一般来说，想构建2logN高度的红黑树比较困难，需要最左边一条路径均是3-结点，而其他的子结点都是2-结点才可以。我们在一般数据里很少能遇到。

大小为N的红黑树，根节点到任意子结点的平均路径长度为 ~1.00logN

这个性质很容易得到。而红黑树相对于二叉树而言，我们提高了40%以上的性能，能够使任何操作都在 ~O(logN) 内完成。

结束语：

复杂的红黑树终于了解完了，可以看出，理解2-3树对于掌握红黑树的原理至关重要。在树的生长变换中，局部变换并不会改变整体的结构这一点非常重要，也是红黑树的灵魂。

在下一篇文章，将会带来Java中另一个最常用的数据结构——散列表。

谢谢观看。

参考文献：《算法导论》《Algorithms, 4th Edition》

红黑二叉查找树（原理、实现）

2-3查找树

2-3树查找 get：

2-3树插入 put：

向2-结点 h 中插入

向3-结点 h 中插入

2-3树性能：

红黑二叉查找树

去掉3-结点

等价定义

结点构成及颜色表示

旋转 rotate：

向左旋转 rotateLeft：

向右旋转 rotateRight：

插入 put：

向单个2-结点中插入新键：

向树底部的2-结点插入新键：

向一个双键树（3-结点）插入新键：

1. 新插入的键最大：

2. 新插入的键最小：

3. 新插入的键大小在两个键之间：

根节点总是黑色

代码实现：

删除 delete：

删除最小值 deleteMin：

代码实现：

删除最大值 deleteMax：

删除任意结点的实现：

性能：

结束语：

猜你喜欢

热点阅读

红黑二叉查找树（原理、实现）

2-3查找树

2-3树 查找 get：

2-3树 插入 put：

向2-结点 h 中插入

向3-结点 h 中插入

2-3树 性能：

红黑二叉查找树

去掉3-结点

等价定义

结点构成及颜色表示

旋转 rotate：

向左旋转 rotateLeft：

向右旋转 rotateRight：

插入 put：

向单个2-结点中插入新键：

向树底部的2-结点插入新键：

向一个双键树（3-结点）插入新键：

1. 新插入的键最大：

2. 新插入的键最小：

3. 新插入的键大小在两个键之间：

根节点总是黑色

代码实现：

删除 delete：

删除最小值 deleteMin：

代码实现：

删除最大值 deleteMax：

删除任意结点的实现：

性能：

结束语：

猜你喜欢

热点阅读

2-3树查找 get：

2-3树插入 put：

2-3树性能：