平衡查找树

之前讲的二叉查找树在最坏情况下性能还是很低的。平衡查找树能够保证无论如何构造它，它的运行时间都是对数级别。在一棵含有 N 个结点的树中，我们希望树高为 ~lgN，这样我们就能保证所有查找都能在 ~lgN 次比较内结束，就和二分查找一样。但是，在动态插入中保证树的完美平衡的代价太高。我们稍微降低完美平衡的要求，学习一种能够保证符号表 API 中所有操作均能在对数时间内完成的数据结构。

1. 2-3查找树

为了保证查找树的平衡性，我们需要一些灵活性，因此我们允许树中的一个结点保存多个键。一棵标准的二叉查找树中的结点称为 2- 结点 ，含有一个键和两条连接；将含有两个键和三条连接的结点称为 3- 结点 （左连接指向的 2-3 树中的键都小于该结点，中连接指向的 2-3 树种中的键都位于该结点的两个键之间，右链接指向的 2-3 树中的键都大于该结点）。

一棵完美平衡的 2-3 查找树中的所有空连接到根结点的距离都应该事相同的。简洁起见，这里用 2-3 树指代一棵完美平衡的 2-3 查找树（在其他情况下这个次表示一种更一般的结构）。

1.查找

将二叉查找树的查找算法一般化就能直接得到 2-3 树的查找算法。要判断一个键是否存在树中，先将它和根结点中的键比较。如果它和其中任意一个键相等，查找命中；否则就根据比较的结果找到指向相应区间的链接，并在其指向的子树中递归地继续查找。

2.向 2- 结点中插入新键

要在 2-3 树中插入一个新结点，我们可以和二叉查找树一样先进行一次未命中的查找，然后把新结点挂在树的底部。但这样的话树无法保持完美平衡性。我们使用 2-3 树的主要原因就在于它能够在插入后继续保持平衡。

如果未命中的查找结束于一个 2- 结点，处理就简单：我们只要把这个 2- 结点替换成一个 3- 结点，将要插入的键保存在其中即可。

但是，如果未命中的查找结束于一个 3- 结点，就要麻烦一些。

3.向一棵只含有一个 3- 结点的树中插入新键

在考虑一般情况之前，先假设我们需要向一棵只含有一个 3- 结点的树中插入一个新键。这棵树中有两个键，所以它已经没有可插入新键的空间了。为了将新键插入，我们先临时将新键存入该结点，使之称为一个 4- 结点（三个键和四条链接）。然后把这个 4- 结点转换未一棵由 3个 2- 结点组成的 2-3 树，其中一个结点（根）含有中键，一个结点含有3个键中的最小者（和根结点的左连接相连），一个结点含有3个键中的最大者。

这棵树既是一棵含有3个结点的二叉查找树，同时也是一棵完美平衡的 2-3 树，因为其中所有的空链接到根结点的距离都相等。插入树前高度为 0，插入树后高度为 1。

4.向一个父结点为 2- 结点的 3- 结点中插入新键

在这种情况下我们需要在维持树的完美平衡下为新键腾出空间。先像上面一样构造一个临时的 4- 结点将其分解成3个 2- 结点，但此时我们不会为中键创建一个新结点，而是将其移至原父结点中。

5.向一个父结点为 3- 结点的 3- 结点插入新键

对于这种情况，我们还是构造一个临时 4- 结点并将其分解，然后将它的中键插入它的父结点。但此时父结点也变成一个新的临时 4- 结点，然后继续在这个结点上进行相同的变换，直至遇到一个 2- 结点或到达根结点。

6.分解根结点

如果从插入结点到根结点都是 3- 结点，根结点最终变成一个临时的 4- 结点。此时按照向一棵只有一个 3- 结点的树中插入新键的方法，将临时 4- 结点分解成3个 2- 结点，使得树高加1。

7.局部变换

将一个 4- 结点分解成一棵 2-3 树可能有6种情况：

2-3 树插入算法的根本在于这些变换都是局部的：除了相关结点和链接之外不必修改或者检查树的其他部分。每次变换中，变更的链接树不会超过一个很小的常数。

8.全局性质

这些局部变换不会影响树的全局有序性和平衡性：任意空链接到根结点的路径长度都是相等的。和标准的二叉查找树由上向下生长不同， 2-3 树的生长是由下向上的。

在一棵大小为 N 的 2-3 树中，插入和查找操作访问的结点必然不超过 lgN 个。因此可以确定 2-3 树在最坏的情况下仍有较好的性能，任何查找或者插入的成本都肯定不会超过对数级别。例如，含有 10亿个结点的 2-3 树的高度仅在 19到30之间。

但是，我们只是实现方式的一部分。 尽管有可能编写代码来对表示2节点和3节点的不同数据类型执行转换，但是我们已经描述的大多数任务在这种直接表示中都不方便实现。

2.红黑二叉查找树

我们使用红黑二叉查找树的简单数据结构来表达并实现 2-3 树。

1.定义

红黑二叉树背后的基本思想是用标准的二叉查找树（完全由 2- 结点构成）和一些额外的信息（替换 3- 结点）来表示 2-3 树。我们将树中的链接分为两种类型：红链接将两个 2- 结点链接起来构成一个 3- 结点，黑链接则是 2-3 树中的普通链接。我们将 3- 结点表示为一条左斜的红色链接（两个 2- 结点其中之一是另一个的左子结点）相连的两个 2- 结点。这种表示法的一个优点是，无需修改就可以直接使用标准二叉查找树的 Get（）方法。

红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树：

1.左链接均为左链接；

2.没有任何一个结点同时和两条红链接相连；

3.该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。

满足这样定义的红黑树和相应的 2-3 树是一一对应的。

2.一一对应

如果我们将一棵红黑树中的红链接画平，那么所有的空链接到根结点的距离都是相同的。如果将有红链接相连的结点合并，得到的就是一棵 2-3 树。相反，如果将一棵 2-3 树中的 3- 结点画作由红色链接相连的两个 2- 结点，那么不会存在能够和两条红链接相连的结点，且树必然是完美黑色平衡的，因为黑链接即 2-3 树中的普通链接，根据定义这些链接必然是完美平衡的。无论我们用那种方式取定义它们，红黑树都既是二叉查找树，也是 2-3 树。因此如果我们能够在保持一一对应关系的基础上实现 2-3 树的插入算法，那么我们就能将两个算法的优点结合起来：二叉查找树中高效简洁的查找方法和 2-3 树中高效的平衡插入算法。

3.颜色表示

因为每个结点都只会有一条指向自己的链接（从父结点指向它），我们将链接的颜色保存在表示结点的 Node 数据类型的布尔变量中。如果指向它的链接是红色的，那么该变量为 true，黑色则为 false。我们约定空链接为黑色。我们使用 IsRed（） 来测试链接的颜色。

public class RedBlackBST<Key, Value> : BaseSymbolTables<Key, Value>
        where Key : IComparable
    {
        private Node root;
        private  const bool RED = true;
        private const bool BLACK = false;
        private class Node
        {
            public Key key;
            public Value value;
            public Node left, right;
            public int N;
            public bool color;

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

        private bool IsRed(Node x)
        {
            if (x == null)
            {
                return false;
            }
            return x.color == RED;
        }

        private int Size(Node x)
        {
            if (x == null)
                return 0;
            else
                return x.N;
        }
    }

4.旋转

在我们实现的某些操作中可能会出现红色右链接或者两条连续的红链接，但在操作完成前这些情况都会被小心地旋转并修复。旋转操作会改变红链接的指向。

一条红色的右链接被转换为左链接，称为左旋转。它对应的方法接受一条指向红黑树中的某个结点的链接作为参数。假设被指向的结点的右链接是红色的，这个方法会对树进行必要的调整并返回一个指向包含同一组键的子树且左链接为红色的根结点的链接。其代码实现，只是将用两个键中较小的作为根结点变成将较大的作为根结点。

        private Node RotateLeft(Node h)
        {
            Node x = h.right;
            h.right = x.left;
            x.left = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + Size(h.left) + Size(h.right);
            return x;
        }

        private Node RotateRight(Node h)
        {
            Node x = h.left;
            h.left = x.right;
            x.right = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + Size(h.left) + Size(h.right);
            return x;
        }

5.在旋转后重置父结点的链接

无论是左旋转还是右旋转，旋转操作都会返回一条链接。我们总是会用  RotateLeft 或 RotateRight 的返回值重置父结点或是根结点中相应的链接。返回的链接可能是左链接也可能是右链接，但是总会将它赋予父结点中的链接。这个链接可能是红色也可能是黑色 -- RotateLeft 和 RotateRight 都通过将 x.color 设为 h.color 保留它原来的颜色。这种简洁的代码是我们使用递归实现二叉查找树的各种方法的原因。

在插入新键时我们可以使用旋转操作保证 2-3 树和红黑树之间的一一对应，因为旋转操作可以保持红黑树的两个重要性质：有序性和完美平衡性。下面来看如何使用旋转操作来保持红黑树的另外两个重要性质：不存在两条连续的红链接和不存在红色的右链接。

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

一棵只含有一个键的红黑树只含有一个 2- 结点。插入另一个键后，需要马上将它们旋转。如果新键小于老键，只需新增一个红色的结点即可。如果新键大于老键，那么新增的红色结点将会产生一条红色的右链接，需要左旋转将其旋转为红色左连接并修改根结点的链接，插入操作才算完成。两种情况的结果均为一棵和单个 3- 结点等价的红黑树,其中含有两个键，一条红链接，树的黑链接高度为 1。

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

用和二叉查找树相同的方式向一棵红黑树中插入一个新键会在树的底部新增一个结点（为了保证有序性），但总是用红链接将新节点和它的父结点相连。

8.向一棵双键树（即一个 3- 结点）中插入新键

这种情况分为三种情况：新键小于树中的两个键，两者之间，或是大于树中的两个键。每种情况都会产生一个同时连接两条红链接的结点，而我们的目的就是修正这一点：

总的来说，我们通过 0 次，1 次和 2 次旋转以及颜色的变换得到了期望的结果。这些转换是红黑树的动态变化的关键。

9.颜色变换

我们专门用一个方法 FlipColors 方法来转换一个结点的两个红色子结点的颜色。除了将子结点的颜色由红变黑之外， 同时还要将父结点的颜色由黑变红 。 这项操作最重要的性质在于它和旋转操作一样是局部变换，不会影响整个树的黑色平衡性。

        private void FlipColors(Node h)
        {
            h.color = RED;
            h.left.color = BLACK;
            h.right.color = BLACK;
        }

10.根结点总是黑色

根据前面的情况，颜色转换会使根结点变为红色。这也可能出现在很大的红黑树中。严格地说，红色的根结点说明根结点是一个 3- 结点的一部分，但实际情况并不是。因此我们在每次插入后都会将根结点设置为黑色。当根结点由红变黑时树的高度就会加1。

11.向树底部的 3- 结点插入新键

对于这种情况，前面的三种情况都会出现：可能是 3- 结点的右链接（只需要转换颜色），或是左链接（需要右转然后转换颜色），或是中链接（需要左旋转下层链接然后右旋转上层链接，最后变换颜色）。颜色转换会使中间结点变红。

12.将红链接在树中向上传递

每次必要的旋转之后都会进行颜色转换，这使得中结点变红。在父结点看来，处理这样一个红色的结点的方式和处理一个新插入的红色结点完全相同，即继续把红链接转移到中结点上去。下图总结的三种情况显示了在红黑树中实现 2-3 树的插入算法的关键操作所需的步骤：要在一个 3- 结点下插入新键，先临时创建一个 4- 结点，将其分解并将红链接由中间键传递给它的父结点。重复这个过程，就能将红链接在树中向上传递，直至遇到一个 2- 结点或者根结点。

总之，只要慎重地使用左旋转，右旋转和颜色转换三种操作，就能保证插入操作后红黑树和 2-3 树的一一对应。在沿着插入结点到根结点的路径向上移动时所经过的每个结点中顺序完成以下操作，就能完成插入操作：

1.如果右子结点是红色且左子结点是黑色，进行左旋转；

2.如果左子结点和它的左子结点都是红色，进行右转；

3.如果左右子结点均为红色，进行颜色转换。

13.实现

因为保持树的平衡性所需的操作是由下至上在每个经历的结点中进行，所以实现很简单：只需要在递归调用之后完成上面所说的三种操作，这里通过三个 if 语句完成。

    public class RedBlackBST<Key, Value> : BaseSymbolTables<Key, Value>
        where Key : IComparable
    {
        private Node root;
        private  const bool RED = true;
        private const bool BLACK = false;
        private class Node
        {
            public Key key;
            public Value value;
            public Node left, right;
            public int N;
            public bool color;

            public Node(Key key,Value value,int N, bool color)
            {
                this.key = key;
                this.value = value;
                this.N = N;
                this.color = color;
            }
        }

        private bool IsRed(Node x)
        {
            if (x == null)
            {
                return false;
            }
            return x.color == RED;
        }

        private Node RotateLeft(Node h)
        {
            Node x = h.right;
            h.right = x.left;
            x.left = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + Size(h.left) + Size(h.right);
            return x;
        }

        private Node RotateRight(Node h)
        {
            Node x = h.left;
            h.left = x.right;
            x.right = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + Size(h.left) + Size(h.right);
            return x;
        }
        private int Size(Node x)
        {
            if (x == null)
                return 0;
            else
                return x.N;
        }

        private void FlipColors(Node h)
        {
            h.color = RED;
            h.left.color = BLACK;
            h.right.color = BLACK;
        }

        public override void Put(Key key, Value value)
        {
            root = Put(root,key,value);
        }

        private Node Put(Node h, Key key, Value value)
        {
            if (h == null)
                return new Node(key,value,1,RED);

            int cmp = key.CompareTo(h.key);
            if (cmp < 0)
                h.left = Put(h.left, key, value);
            else if (cmp > 0)
                h.right = Put(h.right, key, value);
            else
                h.value = value;

            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);

            h.N = Size(h.left) + Size(h.right) + 1;
            return h;
        }
    }

下图时测试用例轨迹：

3.删除操作

和插入操作一样，我们也可以定义一系列局部变换来在删除一个结点的同时保持树的完美平衡性。这个过程比较复杂，因为不仅要在为了删除一个结点而构造临时 4- 结点时沿着查找路径向下进行变换，还要分解遗留的 4- 结点时沿着查找路径向上进行变换。

1.自顶向下的 2-3-4 树

开始之前，先学习一个沿着查找路径既能向上也能向下进行变换的简单算法： 2-3-4 树的插入算法，2-3-4 树=中允许存在 4- 结点。它的插入算法沿查找路径向下变换是为了把凹征当前结点不是 4- 结点（这样树底才有空间插入新的键），沿查找路径向上进行变换是为了将之前创建的 4- 结点配平。向下变换和 2-3 树种分解 4- 结点所进行的变换相同。如果根结点是4-结点，就将它分解成3个 2- 结点，使得树高加一。在向下查找的过程中，如果遇到一个父结点是 2- 结点的 4- 结点，将 4- 结点分解成两个 2- 结点并将中间键传递给父结点，使得父结点变成 3- 结点。如果遇到一个父结点是 3- 结点的 4- 结点，将 4- 结点分解成两个 2- 结点并将中间键传递给父结点，使得父结点变为 4- 结点；不必担心遇到父结点为 4- 结点的 4- 结点，因为插入算法本身就保证了这种情况不会出现。到达树底之后，只会遇到 2- 结点或 3- 结点，所以我们可以插入新的键。

要用红黑树实现这个算法，我们需要：

将 4- 结点 表示由三个 2- 结点组成的一棵平衡的子树，根结点和两个子结点都用红链接相连；

在向下的过程中分解所有 4- 结点并进行颜色转换；

和插入操作一样，在向上的过程用旋转将 4- 结点配平。

只需移动上面算法的 Put 方法中的一行代码就能实现 2-3-4 树中的插入操作：将 ColorFlip 语句及其 if 语句一道递归调用之前（null 测试和比较操作之间）。

2.删除最小键

从树底部的 3- 结点删除键很简单，但从 2- 结点删除一个键会留下一个空链接，这样会破环树的完美平衡性。

为了保证我们不会删除一个 2- 结点，我们沿着左连接向下进行变换，确保当前结点不是 2- 结点（可能是 3- 结点，也可能是临时 4- 结点）。

首先，根结点可能有两种情况。如果根结点是 2- 结点且它的两个子结点都是 2- 结点，我们可以直接将这三个结点变成一个 4- 结点；否则我们需要保证根结点的左子结点不是 2- 结点，如有必要可以从它右侧的兄弟结点“借”一个键来。如图。在沿着左连接向下的过程中，保证一下情况之一成立：

如果当前结点的左子结点不是 2- 结点，完成；

如果当前结点的左子结点是 2- 结点而它的亲兄弟结点不是 2- 结点，将左子结点的兄弟结点中的一个键移动到左子结点中；

如果当前结点的左子结点和它的亲兄弟结点都是 2- 结点，将左子结点，父结点中的最小键和左子节点最近的兄弟结点合并成一个 4- 结点，使父结点由 3- 结点变成 2- 结点或者由 4- 结点变成 3- 结点。

在遍历的过程中执行这个过程，最后能够得到一个含有最小键的 3- 结点或者 4- 结点，然后就可以直接从中将其删除。我们再回头向上分解所有临时的 4- 结点。

3.删除操作

在查找路径上进行和删除最小键相同的变换同样可以保证在查找过程中任意当前结点均不是 2- 结点。如果被查找的键在树的底部，可以直接删除。如果不在，需要将它和它的后继结点交换，和二叉查找树

一样。

红黑树的性质

研究红黑树的性质就是要检查对应的 2-3 树并对相应的 2-3 树进行分析过程。所有基于红黑树的符号表实现都能保证操作的运行时间为对数级别（范围查找除外）。

无论键的插入顺序如何，红黑树都几乎是完美平衡的。一棵大小为 N 的红黑树的高度不会超过 2lgN 。红黑树的最坏情况是它所对应的 2-3 树中构成最左边的路径结点全部都是 3- 结点而其余均是 2- 结点。

最左边的路径长度是只包含 2- 结点的路径长度（~lgN）的两倍。使用随机的键序列，在一棵大小为 N 的红黑树中一次查找所需的比较次数约为（1.00 lgN - 0.5）,根结点到任意结点的平均路径长度 ~ 1.00lgN 。

红黑树的 Get 方法不会检查结点的颜色，因此平衡性相关的操作不会产生任何负担；因为树是平衡的，所以查找比二叉查找树更快。每个只会被插入一次，但却可能查找无数次。