qidao123.com技术社区-IT企服评测·应用市场

标题: 数据结构与算法之ACM Fellow-算法3.3 平衡查找树 [打印本页]
作者: 天空闲话    时间: 2025-4-10 17:07
标题: 数据结构与算法之ACM Fellow-算法3.3 平衡查找树
数据结构与算法之ACM Fellow-算法3.3 平衡查找树

我们在前面几节中学习过的算法已经可以大概很好地用于许多应用程序中，但它们在最坏情况下的性能还是很糟糕。在本节中我们会介绍一种二分查找树并能 包管 无论如何构造它，它的运行时间都是对数级别的。理想情况下我们希望可以大概保持二分查找树的平衡性。在一棵含有 ![N/740943/image00798.gif) 个结点的树中，我们希望树高为 ![\sim\lg N/740943/image00914.gif)，如许我们就能包管所有查找都能在 ![\sim\lg N/740943/image00914.gif) 次比较内结束，就和二分查找一样（请见命题 B）。不幸的是，在动态插入中包管树的完善平衡的代价太高了。在本节中，我们稍稍放松完善平衡的要求并将学习一种可以大概包管符号表 API 中所有操纵（范围查找除外）均可以大概在对数时间内完成的数据结构。
3.3.1　2-3 查找树

附赠网盘下载地点

对应视频资源地点+链接：资源网盘分享
更多资源+夸克网盘资源群 资源群
群满+新夸克共享群：备份群
为了包管查找树的平衡性，我们需要一些机动性，因此在这里我们允许树中的一个结点保存多个键。确切地说，我们将一棵标准的二叉查找树中的结点称为 2- 结点（含有一个键和两条链接），而现在我们引入 3- 结点，它含有两个键和三条链接。2- 结点和 3- 结点中的每条链接都对应着其中保存的键所分割产生的一个区间。
定义。一棵 2-3 查找树 或为一棵空树，或由以下结点构成：
和以前一样，我们将指向一棵空树的链接称为 空链接。2-3 查找树如图 3.3.1 所示。
![{%}/740943/image01341.gif)
图 3.3.1　2-3 查找树示意图
一棵 完善平衡 的 2-3 查找树中的所有空链接到根结点的距离都应该是相同的。简便起见，这里我们用 2-3 树 指代一棵完善平衡的 2-3 查找树（在其他情况下这个词应该表示一种更一般的结构）。稍后我们将会学习定义并高效地实现 2- 结点、3- 结点和 2-3 树的基本操纵。现在先假设我们已经可以大概自如地操纵它们并来看看应该如何将它们用作查找树。
3.3.1.1　查找

将二叉查找树的查找算法一般化我们就可以大概直接得到 2-3 树的查找算法。要判定一个键是否在树中，我们先将它和根结点中的键比较。如果它和其中任意一个相称，查找命中；否则我们就根据比较的结果找到指向相应区间的链接，并在其指向的子树中递归地继续查找。如果这是个空链接，查找未命中。具体查找过程如图 3.3.2 所示。
![/740943/image01342.gif)
图 3.3.2　2-3 树中的查找命中（左）和未命中（右）
3.3.1.2　向 2- 结点中插入新键

要在 2-3 树中插入一个新结点，我们可以和二叉查找树一样先举行一次未命中的查找，然后把新结点挂在树的底部。但如许的话树无法保持完善平衡性。我们利用 2-3 树的主要原因就在于它可以大概在插入后继续保持平衡。如果未命中的查找结束于一个 2- 结点，事变就好办了：我们只要把这个 2- 结点更换为一个 3- 结点，将要插入的键保存在其中即可（如图 3.3.3 所示）。如果未命中的查找结束于一个 3- 结点，事变就要麻烦一些。
![/740943/image01343.gif)
图 3.3.3　向 2- 结点中插入新的键
3.3.1.3　向一棵只含有一个 3- 结点的树中插入新键

在考虑一般情况之前，先假设我们需要向一棵只含有一个 3- 结点的树中插入一个新键。这棵树中有两个键，所以在它唯一的结点中已经没有可插入新键的空间了。为了将新键插入，我们先临时将新键存入该结点中，使之成为一个 4- 结点。它很自然地扩展了以前的结点并含有 3 个键和 4 条链接。创建一个 4- 结点很方便，因为很轻易将它转换为一棵由 3 个 2- 结点构成的 2-3 树，其中一个结点（根）含有中键，一个结点含有 3 个键中的最小者（和根结点的左链接相连），一个结点含有 3 个键中的最大者（和根结点的右链接相连）。这棵树既是一棵含有 3 个结点的二叉查找树，同时也是一棵完善平衡的 2-3 树，因为其中所有的空链接到根结点的距离都相称。插入前树的高度为 0，插入后树的高度为 1。这个例子很简单但却值得学习，它说明白 2-3 树是如何生长的，如图 3.3.4 所示。
![{%}/740943/image01344.gif)
图 3.3.4　向一棵只含有一个 3- 结点的树中插入新键
3.3.1.4　向一个父结点为 2- 结点的 3- 结点中插入新键

作为第二轮热身，假设未命中的查找结束于一个 3- 结点，而它的父结点是一个 2- 结点。在这种情况下我们需要 在维持树的完善平衡的条件下为新键腾出空间。我们先像刚才一样构造一个临时的 4- 结点并将其分解，但此时我们不会为中键创建一个新结点，而是将其移动至原来的父结点中。你可以将这次转换看成将指向原 3- 结点的一条链接更换为新父结点中的原中键左右两边的两条链接，并分别指向两个新的 2- 结点。根据我们的假设，父结点中是有空间的：父结点是一个 2- 结点（一个键两条链接），插入之后变为了一个 3- 结点（两个键 3 条链接）。另外，这次转换也并不影响（完善平衡的）2-3 树的主要性质。树仍然是有序的，因为中键被移动到父结点中去了；树仍然是完善平衡的，插入后所有的空链接到根结点的距离仍然相同。请确认你完全理解了这次转换——它是 2-3 树的动态变化的核心，其过程如图 3.3.5 所示。
![/740943/image01345.gif)
图 3.3.5　向一个父结点为 2- 结点的 3- 结点中插入新键
3.3.1.5　向一个父结点为 3- 结点的 3- 结点中插入新键

现在假设未命中的查找结束于一个父结点为 3- 结点的结点。我们再次和刚才一样构造一个临时的 4- 结点并分解它，然后将它的中键插入它的父结点中。但父结点也是一个 3- 结点，因此我们再用这个中键构造一个新的临时 4- 结点，然后 在这个结点上举行相同的变换，即分解这个父结点并将 它的 中键插入到 它的 父结点中去。推广到一般情况，我们就如许一直向上不断分解临时的 4- 结点并将中键插入更高层的父结点，直至遇到一个 2- 结点并将它更换为一个不需要继续分解的 3- 结点，或者是到达 3- 结点的根。该过程如图 3.3.6 所示。
![/740943/image01346.gif)
图 3.3.6　向一个父结点为 3- 结点的 3- 结点中插入新键
3.3.1.6　分解根结点

如果从插入结点到根结点的路径上全都是 3- 结点，我们的根结点最终变成一个临时的 4- 结点。此时我们可以按照向一棵只有一个 3- 结点的树中插入新键的方法处理这个问题。我们将临时的 4- 结点分解为 3 个 2- 结点，使得树高加 1，如图 3.3.7 所示。请注意，这次最后的变换仍然保持了树的完善平衡性，因为它变换的是根结点。
![/740943/image01347.gif)
图 3.3.7　分解根结点
3.3.1.7　局部变换

将一个 4- 结点分解为一棵 2-3 树大概有 6 种情况，都总结在了图 3.3.8 中。这个 4- 结点大概是根结点，大概是一个 2- 结点的左子结点或者右子结点，也大概是一个 3- 结点的左子结点、中子结点或者右子结点。2-3 树插入算法的根本在于这些变换都是 局部的：除了相关的结点和链接之外不必修改或者检查树的其他部门。每次变换中，变更的链接数目不会超过一个很小的常数。需要特别指出的是，不光是在树的底部，树中的 任何地方 只要符合相应的模式，变换都可以举行。每个变换都会将 4- 结点中的一个键送入它的父结点中，并重构相应的链接而不必涉及树的其他部门。
![/740943/image01348.jpeg)
图 3.3.8　在一棵 2-3 树中分解一个 4- 结点的情况汇总
3.3.1.8　全局性质

这些 局部 变换不会影响树的 全局 有序性和平衡性：任意空链接到根结点的路径长度都是相称的。作为参考，图 3.3.9 所示的是当一个 4- 结点是一个 3- 结点的中子结点时的完整变换情况。如果在变换之前根结点到所有空链接的路径长度为 ![h/740943/image00826.gif)，那么变换之后该长度仍然为 ![h/740943/image00826.gif)。所有的变换都具有这个性质，纵然是将一个 4- 结点分解为两个 2- 结点并将其父结点由 2- 结点变为 3- 结点，或是由 3- 结点变为一个临时的 4- 结点时也是如此。当根结点被分解为 3 个 2- 结点时，所有空链接到根结点的路径长度才会加 1。如果你还没有完全理解，请完成训练 3.3.7。它要求你为其他的 5 种情况画出图 3.3.8 的扩展图来证明这一点。理解所有局部变换都不会影响整棵树的有序性和平衡性是理解这个算法的关键。
![/740943/image01349.gif)
图 3.3.9　4- 结点的分解是一次局部变换，不会影响树的有序性和平衡性
和标准的二叉查找树由上向下生长不同，2-3 树的生长是由下向上的。如果你花点时间仔细研究一下图 3.3.10，就能很好地理解 2-3 树的构造方式。它给出了我们的标准索引测试用例中产生的一系列 2-3 树，以及一系列由同一组键按照升序依次插入到树中时所产生的所有 2-3 树。还记得在二叉查找树中，按照升序插入 10 个键会得到高度为 9 的一棵最差查找树吗？如果利用 2-3 树，树的高度是 2。
![/740943/image01350.gif)
图 3.3.10　2-3 树的构造轨迹
以上的笔墨已经足够为我们定义一个利用 2-3 树作为数据结构的符号表的实现了。2-3 树的分析和二叉查找树的分析大不相同，因为我们主要感爱好的是 最坏情况下 的性能，而非一般情况（这种情况下我们会用随机键模型分析预期的性能）。在符号表的实现中，一般我们无法控制用例会按照什么次序向表中插入键，因此对最坏情况的分析是唯一可以大概提供性能包管的办法。
命题 F。在一棵大小为 ![N/740943/image00798.gif) 的 2-3 树中，查找和插入操纵访问的结点一定不超过 ![\lg N/740943/image00915.gif) 个。
证明。一棵含有 ![N/740943/image00798.gif) 个结点的 2-3 树的高度在 ![\lfloor\log_3N\rfloor=\lfloor(\lg N)/(\lg3)\rfloor/740943/image01351.gif)（如果树中满是 3- 结点）和 ![\lfloor\lg N\rfloor/740943/image00945.gif)（如果树中满是 2- 结点）之间（请见训练 3.3.4）。
因此我们可以确定 2-3 树在最坏情况下仍有较好的性能。每个操纵中处理每个结点的时间都不会超过一个很小的常数，且这两个操纵都只会访问一条路径上的结点，所以任何查找或者插入的本钱都肯定不会超过对数级别。通过对比图 3.3.11 中的 2-3 树和图 3.2.8 中由相同的键构造的二叉查找树，你也可以看到，完善平衡的 2-3 树要平展得多。比方，含有 10 亿个结点的一棵 2-3 树的高度仅在 19 到 30 之间。我们最多只需要访问30个结点就可以大概在10亿个键中举行任意查找和插入操纵，这是相当惊人的。
![/740943/image01352.gif)
图 3.3.11　由随机键构造的一棵典型的 2-3 树
但是，我们和真正的实现还有一段距离。尽管我们可以用不同的数据类型表示 2- 结点和 3- 结点并写出变换所需的代码，但用这种直白的表示方法实现大多数的操纵并不方便，因为需要处理的情况着实太多。我们需要维护两种不同类型的结点，将被查找的键和结点中的每个键举行比较，将链接和其他信息从一种结点复制到另一种结点，将结点从一种数据类型转换到另一种数据类型，等等。实现这些不仅需要大量的代码，而且它们所产生的额外开销大概会使算法比标准的二叉查找树更慢。平衡一棵树的初衷是为了消除最坏情况，但我们希望这种保障所需的代码可以大概越少越好。幸运的是你将看到，我们只需要一点点代价就能用一种统一的方式完成所有变换。
3.3.2　红黑二叉查找树

上文所述的 2-3 树的插入算法并不难理解，现在我们会看到它也不难实现。我们要学习一种名为 红黑二叉查找树 的简单数据结构来表达并实现它。最后的代码量并不大，但理解这些代码是如何工作的以及为什么可以大概工作却需要一番仔细的探究。
3.3.2.1　更换 3- 结点

红黑二叉查找树背后的基本思想是用标准的二叉查找树（完全由 2- 结点构成）和一些额外的信息（更换 3- 结点）来表示 2-3 树。我们将树中的链接分为两种类型： 红链接 将两个 2- 结点连接起来构成一个 3- 结点， 黑链接 则是 2-3 树中的普通链接。确切地说，我们将 3- 结点表示为由一条 左斜 的红色链接（两个 2- 结点其中之一是另一个的左子结点）相连的两个 2- 结点，如图 3.3.12 所示。这种表示法的一个长处是，我们 无需修改 就可以直接利用标准二叉查找树的 get() 方法。对于任意的 2-3 树，只要对结点举行转换，我们都可以立即派生出一棵对应的二叉查找树。我们将用这种方式表示 2-3 树的二叉查找树称为 红黑二叉查找树（以下简称为 红黑树）。
![/740943/image01353.gif)
图 3.3.12　由一条红色左链接相连的两个 2- 结点表示一个 3- 结点
3.3.2.2　一种等价的定义

红黑树的另一种 定义 是含有红黑链接并满足下列条件的二叉查找树：
满足如许定义的红黑树和相应的 2-3 树是一一对应的。
3.3.2.3　一一对应

如果我们将一棵红黑树中的红链接画平，那么所有的空链接到根结点的距离都将是相同的（如图 3.3.13 所示）。如果我们将由红链接相连的结点归并，得到的就是一棵 2-3 树。相反，如果将一棵 2-3 树中的 3- 结点画作由红色左链接相连的两个 2- 结点，那么不会存在可以大概和两条红链接相连的结点，且树一定是完善黑色平衡的，因为黑链接即 2-3 树中的普通链接，根据定义这些链接一定是完善平衡的。无论我们选择用何种方式去定义它们，红黑树都 既是 二叉查找树， 也是 2-3 树，如图 3.3.14 所示。因此，如果我们可以大概在保持一一对应关系的基础上实现 2-3 树的插入算法，那么我们就可以大概将两个算法的长处联合起来：二叉查找树中简便高效的查找方法和 2-3 树中高效的平衡插入算法。
![/740943/image01354.jpeg)
图 3.3.13　将红链接画平常，一棵红黑树就是一棵 2-3 树
![/740943/image01355.jpeg)
图 3.3.14　红黑树和 2-3 树的一一对应关系
3.3.2.4　颜色表示

方便起见，因为每个结点都只会有一条指向自己的链接（从它的父结点指向它），我们将链接的颜色保存在表示结点的 Node 数据类型的布尔变量 color 中。如果指向它的链接是红色的，那么该变量为 true，黑色则为 false。我们约定空链接为黑色。为了代码的清晰我们定义了两个常量 RED 和 BLACK 来设置和测试这个变量。我们利用私有方法 isRed() 来测试一个结点和它的父结点之间的链接的颜色。当我们提到一个结点的颜色时，我们指的是指向该结点的链接的颜色，反之亦然。颜色表示的代码实现如图 3.3.15 所示。
![/740943/image01356.jpeg)
图 3.3.15　红黑树的结点表示
3.3.2.5　旋转

在我们实现的某些操纵中大概会出现红色右链接或者两条连续的红链接，但在操纵完成前这些情况都会被小心地 旋转 并修复。旋转操纵会改变红链接的指向。首先，假设我们有一条红色的右链接需要被转化为 左链接（请见图 3.3.16）。这个操纵叫做 左旋转，它对应的方法接受一条指向红黑树中的某个结点的链接作为参数。假设被指向的结点的右链接是红色的，这个方法会对树举行必要的调解并返回一个指向包罗同一组键的子树且其左链接为红色的根结点的链接。如果你对照图示中调解前后的情况逐行阅读这段代码，你会发现这个操纵很轻易理解：我们只是将用两个键中的较小者作为根结点变为将较大者作为根结点。实现将一个红色左链接转换为一个红色右链接的一个 右旋转 的代码完全相同，只需要将 left 和 right 互换即可（如图 3.3.17 所示）。
![/740943/image01357.jpeg)
图 3.3.16　左旋转 h 的右链接
![/740943/image01358.gif)
图 3.3.17　右旋转 h 的左链接
3.3.2.6　在旋转后重置父结点的链接

无论左旋转还是右旋转，旋转操纵都会返回一条链接。我们总是会用 rotateRight() 或 rotateLeft() 的返回值重置父结点（或是根结点）中相应的链接。返回的链接大概是左链接也大概是右链接，但是我们总会将它赋予父结点中的链接。这个链接大概是红色也大概是黑色—— rotateLeft() 和 rotateRight() 都通过将 x.color 设为 h.color 保存它原来的颜色。这大概会产生两条连续的红链接，但我们的算法会继续用旋转操纵修正这种情况。比方，代码 h = rotateLeft(h); 将旋转结点 h 的红色右链接，使得 h 指向了旋转后的子树的根结点（构成该子树中的所有键和旋转前相同，只是根结点发生了变化）。这种简便的代码是我们利用递归实现二叉查找树的各种方法的主要原因。你会看到，它使得旋转操纵成为了普通插入操纵的一个简单增补。
在插入新的键时我们可以利用旋转操纵帮助我们包管 2-3 树和红黑树之间的一一对应关系，因为旋转操纵可以保持红黑树的两个重要性质： 有序性 和 完善平衡性。也就是说，我们在红黑树中举行旋转时无需为树的有序性或者完善平衡性担心。下面我们来看看应该如何利用旋转操纵来保持红黑树的另外两个重要性质（不存在两条连续的红链接和不存在红色的右链接）。我们先用一些简单的情况热热身。
3.3.2.7　向单个 2- 结点中插入新键

一棵只含有一个键的红黑树只含有一个 2- 结点。插入另一个键之后，我们马上就需要将它们旋转。如果新键小于老键，我们只需要新增一个红色的结点即可，新的红黑树和单个 3- 结点完全等价。如果新键大于老键，那么新增的红色结点将会产生一条红色的右链接。我们需要利用 root = rotateLeft(root); 来将其旋转为红色左链接并修正根结点的链接，插入操纵才算完成。两种情况的结果均为一棵和单个 3- 结点等价的红黑树，其中含有两个键，一条红链接，树的黑链接高度为 1，如图 3.3.18 所示。
![/740943/image01359.gif)
图 3.3.18　向单个 2- 结点中插入一个新键
3.3.2.8　向树底部的 2- 结点插入新键

用和二叉查找树相同的方式向一棵红黑树中插入一个新键会在树的底部新增一个结点（为了包管有序性），但总是用红链接将新结点和它的父结点相连。如果它的父结点是一个 2- 结点，那么刚才讨论的两种处理方法仍然适用。如果指向新结点的是父结点的左链接，那么父结点就直接成为了一个 3- 结点；如果指向新结点的是父结点的右链接，这就是一个错误的 3- 结点，但一次左旋转就可以大概修正它，如图 3.3.19 所示。
![/740943/image01360.gif)
图 3.3.19　向树底部的 2- 结点插入一个新键
3.3.2.9　向一棵双键树（即一个 3- 结点）中插入新键

这种情况又可分为三种子情况：新键小于树中的两个键，在两者之间，或是大于树中的两个键。每种情况中都会产生一个同时连接到两条红链接的结点，而我们的目标就是修正这一点。
![/740943/image01361.jpeg)
图 3.3.20　向一棵双键树（即一个 3- 结点）中插入一个新键的三种情况
总的来说，我们通过 0 次、1 次和 2 次旋转以及颜色的变化得到了期望的结果。在 2-3 树中， 请确认你完全理解了这些转换，它们是红黑树的动态变化的关键。
3.3.2.10　颜色转换

如图 3.3.21 所示，我们专门用一个方法 flipColors() 来转换一个结点的两个红色子结点的颜色。除了将子结点的颜色由红变黑之外，我们同时还要将父结点的颜色由黑变红。这项操纵最重要的性质在于它和旋转操纵一样是局部变换，不会影响 整棵树的黑色平衡性。根据这一点，我们马上可以大概在下面完整地实现红黑树。
![/740943/image01362.jpeg)
图 3.3.21　通过转换链接的颜色来分解 4- 结点
3.3.2.11　根结点总是黑色

在 3.3.2.9 所述的情况中，颜色转换会使根结点变为红色。这也大概出现在很大的红黑树中。严格地说，红色的根结点说明根结点是一个 3- 结点的一部门，但实际情况并不是如许。因此我们在每次插入后都会将根结点设为黑色。注意，每当根结点由红变黑时树的黑链接高度就会加 1。
3.3.2.12　向树底部的 3- 结点插入新键

现在假设我们需要在树的底部的一个 3- 结点下加入一个新结点。前面讨论过的三种情况都会出现，如图 3.3.22 所示。指向新结点的链接大概是 3- 结点的右链接（此时我们只需要转换颜色即可），或是左链接（此时我们需要举行右旋转然后再转换颜色），或是中链接（此时我们需要先左旋转下层链接然后右旋转上层链接，最后再转换颜色）。颜色转换会使到中结点的链接变红，相当于将它送入了父结点。这意味着在父结点中继续插入一个新键，我们也会继续用相同的办法解决这个问题。
![/740943/image01363.jpeg)
图 3.3.22 向树底部的 3- 结点插入一个新键
3.3.2.13　将红链接在树中向上传递

2-3 树中的插入算法需要我们分解 3- 结点，将中间键插入父结点，如此这般直到遇到一个 2- 结点或是根结点。我们所考虑过的所有情况都正是为了告竣这个目标：每次必要的旋转之后我们都会举行颜色转换，这使得中结点变红。在父结点看来，处理如许一个红色结点的方式和处理一个新插入的红色结点完全相同，即继续把红链接转移到中结点上去。图 3.3.23 中总结的三种情况显示了在红黑树中实现 2-3 树的插入算法的关键操纵所需的步骤：要在一个 3- 结点下插入新键，先创建一个临时的 4- 结点，将其分解并将红链接由中间键传递给它的父结点。重复这个过程，我们就能将红链接在树中向上传递，直至遇到一个 2- 结点或者根结点。
![/740943/image01364.jpeg)
图 3.3.23　红黑树中红链接向上传递
总之，只要谨慎地利用左旋转、右旋转和颜色转换这三种简单的操纵，我们就可以大概包管插入操纵后红黑树和 2-3 树的一一对应关系。在沿着插入点到根结点的路径向上移动时在所颠末的每个结点中次序完成以下操纵，我们就能完成插入操纵：
你应该花点时间确认以上步骤处理了前文描述的所有情况。请注意，第一个操纵表示将一个 2- 结点变为一个 3- 结点和插入的新结点与树底部的 3- 结点通过它的中链接相连的两种情况。
3.3.3　实现

因为保持树的平衡性所需的操纵是 由下向上 在每个所颠末的结点中举行的，将它们植入我们已有的实现中十分简单：只需要在递归调用之后完成这些操纵即可，如算法 3.4 所示。上一段中列出的三种操纵都可以通过一个检测两个结点的颜色的 if 语句完成。尽管实现所需的代码量很小，但如果没有我们学习过的两种抽象数据结构（2-3 树和红黑树）作为铺垫，这段实现仍然会非常难以理解。在检查了三到五个结点的颜色之后（也许还需要举行一两次旋转以及颜色转换），我们就可以得到一棵近乎完善平衡的二叉查找树。
算法 3.4　红黑树的插入算法
  1. public class RedBlackBST<Key extends Comparable<Key>, Value>
  2. {
  4. private Node root;
  6. private class Node // 含有color变量的Node对象（请见3.3.2.4节）
  8. private boolean isRed(Node h)    // 请见3.3.2.4节
  9. private Node rotateLeft(Node h)  // 请见图3.3.16
  10. private Node rotateRight(Node h) // 请见图3.3.17
  11. private void flipColors(Node h)  // 请见图3.3.21
  13. private int size()               // 请见算法3.3
  15. public void put(Key key, Value val)
  16. {  // 查找key，找到则更新其值，否则为它新建一个结点
  17.    root = put(root, key, val);
  18.    root.color = BLACK;
  19. }
  21. private Node put(Node h, Key key, Value val)
  22. {
  23.    if (h == null)  // 标准的插入操作，和父结点用红链接相连
  24.       return new Node(key, val, 1, RED);
  26.    int cmp = key.compareTo(h.key);
  27.    if      (cmp < 0) h.left  = put(h.left,  key, val);
  28.    else if (cmp > 0) h.right = put(h.right, key, val);
  29.    else h.val = val;
  31.    if (isRed(h.right) && !isRed(h.left))    h = rotateLeft(h);
  32.    if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
  33.    if (isRed(h.left) && isRed(h.right))     flipColors(h);
  35.    h.N = size(h.left) + size(h.right) + 1;
  36.    return h;
  37. }
  38. }
复制代码
除了递归调用后的三条 if 语句，红黑树中 put() 的递归实现和二叉查找树中 put() 的实现完全相同。它们在查找路径上包管了红黑树和 2-3 树的一一对应关系，使得树的平衡性靠近完善。第一条 if 语句会将任意含有红色右链接的 3- 结点（或临时的 4- 结点）向左旋转；第二条 if 语句会将临时的 4- 结点中两条连续红链接中的上层链接向右旋转；第三条 if 语句会举行颜色转换并将红链接在树中向上传递（详情请见正文）。
图 3.3.24 给出了利用我们的标准索引测试用例举行测试的轨迹和用同一组键按照升序构造一棵红黑树的测试轨迹。仅从红黑树的三种标准操纵的角度分析这些例子对我们理解问题很有帮助，之前我们也是如许做的。另一个基本训练是检查它们和 2-3 树的一一对应关系（可以对比图 3.3.10 中由同一组键构造的 2-3 树）。在两种情况中你都能通过思索 将 P 插入红黑树 所需的转换来检验你对算法的理解水平（请见训练 3.3.12）。
![/740943/image01365.jpeg)
图 3.3.24　红黑树的构造轨迹
3.3.4　删除操纵

算法 3.4 中的 put() 方法是本书中最复杂的实现之一，而红黑树的 deleteMin()、 deleteMax() 和 delete() 的实现更麻烦，我们将它们的完整实现留做训练，但这里仍然需要学习它们的基本原理。要描述删除算法，首先我们要回到 2-3 树。和插入操纵一样，我们也可以定义一系列局部变换来在删除一个结点的同时保持树的完善平衡性。这个过程比插入一个结点更加复杂，因为我们不仅要在（为了删除一个结点而）构造临时 4- 结点时沿着查找路径 向下 举行变换，还要在分解遗留的 4- 结点时沿着查找路径 向上 举行变换（同插入操纵）。
3.3.4.1　自顶向下的 2-3-4 树

作为第一轮热身，我们先学习一个沿查找路径既能向上也能向下举行变换的稍简单的算法：2-3-4 树的插入算法，2-3-4 树 中允许存在我们以前见过的 4- 结点。它的插入算法沿查找路径向下举行变换是为了包管当前结点不是 4- 结点（如许树底才有空间来插入新的键），沿查找路径向上举行变换是为了将之前创建的 4- 结点配平，如图 3.3.25 所示。向下的变换和我们在 2-3 树中分解 4- 结点所举行的变换 完全相同。如果根结点是 4- 结点，我们就将它分解成三个 2- 结点，使得树高加 1。在向下查找的过程中，如果遇到一个父结点为 2- 结点的 4- 结点，我们将 4- 结点分解为两个 2- 结点并将中间键传递给它的父结点，使得父结点变为一个 3- 结点；如果遇到一个父结点为 3- 结点的 4- 结点，我们将 4- 结点分解为两个 2- 结点并将中间键传递给它的父结点，使得父结点变为一个 4- 结点；我们不必担心会遇到父结点为 4- 结点的 4- 结点，因为插入算法自己就包管了这种情况不会出现。到达树的底部之后，我们也只会遇到 2- 结点或者 3- 结点，所以我们可以插入新的键。要用红黑树实现这个算法，我们需要：
![/740943/image01366.gif)
图 3.3.25　自顶向下的 2-3-4 树的插入算法中的变换
令人惊讶的是，你只需要移动算法 3.4 的 put() 方法中的一行代码就能实现 2-3-4 树中的插入操纵：将 colorFlip() 语句（及其 if 语句）移动到递归调用之前（ null 测试和比较操纵之间）。在多个进程可以同时访问同一棵树的应用中这个算法优于 2-3 树，因为它操纵的总是当前结点的一个或两个链接。我们下面要讲的删除算法和它的插入算法雷同，而且也适用于 2-3 树。
3.3.4.2　删除最小键

在第二轮热身中我们要学习 2-3 树中删除最小键的操纵。我们注意到从树底部的 3- 结点中删除键是很简单的，但 2- 结点则不然。从 2- 结点中删除一个键会留下一个空结点，一般我们会将它更换为一个空链接，但如许会破坏树的完善平衡性。所以我们需要如许做：为了包管我们不会删除一个 2- 结点，我们沿着左链接向下举行变换，确保当前结点不是 2- 结点（大概是 3- 结点，也大概是临时的 4- 结点）。首先，根结点大概有两种情况。如果根是 2- 结点且它的两个子结点都是 2- 结点，我们可以直接将这三个结点变成一个 4- 结点；否则我们需要包管根结点的左子结点不是 2- 结点，如有必要可以从它右侧的兄弟结点“借”一个键来。以上情况如图 3.3.26 所示。在沿着左链接向下的过程中，包管以下情况之一成立：
![/740943/image01367.gif)
图 3.3.26　删除最小键操纵中的变换
在遍历的过程中执行这个过程，最后可以大概得到一个含有最小键的 3- 结点或者 4- 结点，然后我们就可以直接从中将其删除，将 3- 结点变为 2- 结点，或者将 4- 结点变为 3- 结点。然后我们再回头向上分解所有临时的 4- 结点。
3.3.4.3　删除操纵

在查找路径上举行和删除最小键相同的变换同样可以包管在查找过程中任意当前结点均不是 2- 结点。如果被查找的键在树的底部，我们可以直接删除它。如果不在，我们需要将它和它的后继结点交换，就和二叉查找树一样。因为当前结点一定不是 2- 结点，问题已经转化为在一棵根结点不是 2- 结点的子树中删除最小的键，我们可以在这棵子树中利用前文所述的算法。和以前一样，删除之后我们需要向上回溯并分解余下的 4- 结点。
本节末尾的训练中有几道是关于这些删除算法的例子和实现的。有爱好理解或实现删除算法的读者应该掌握这些训练中的细节。对算法研究感爱好的读者应该认识到这些方法的重要性，因为这是我们见过的第一种可以大概同时实现高效的 查找、 插入 和 删除 操纵的符号表实现。下面我们将会验证这一点。
3.3.5　红黑树的性质

研究红黑树的性质就是要检查对应的 2-3 树并对相应的 2-3 树举行分析的过程。我们的最终结论是 所有基于红黑树的符号表实现都能包管操纵的运行时间为对数级别（范围查找除外，它所需的额外时间和返回的键的数目成正比）。我们重复并强调这一点是因为它十分重要。
3.3.5.1　性能分析

首先，无论键的插入次序如何，红黑树都险些是完善平衡的（请见图 3.3.27）。这从它和 2-3 树的一一对应关系以及 2-3 树的重要性质可以得到。
![/740943/image01368.jpeg)
图 3.3.27　利用随机键构造的典型红黑树，没有画出空链接
命题 G。一棵大小为 ![N/740943/image00798.gif) 的红黑树的高度不会超过 ![2\lg N/740943/image01224.gif)。
简略的证明。红黑树的最坏情况是它所对应的 2-3 树中构成最左边的路径结点全部都是 3- 结点而其余均为 2- 结点。最左边的路径长度是只包罗 2- 结点的路径长度（![\sim\lg N/740943/image00914.gif)）的两倍。要按照某种次序构造一棵均匀路径长度为 ![2\lg N/740943/image01224.gif) 的最差红黑树虽然大概，但并不轻易。如果你喜欢数学，你也许会喜欢在训练 3.3.24 中探究这个问题的答案。
这个上界是比较守旧的。利用随机的键序列和典型应用中常见的键序列举行的实行都证明，在一棵大小为 ![N/740943/image00798.gif) 的红黑树中一次查找所需的比较次数约为（![1.00\lg N-0.5/740943/image01369.gif)）。另外，在实际情况下你不太大概遇到比这个数字高得多的均匀比较次数，如表 3.3.1 所示。
表 3.3.1　利用 RedBlackBST 的 FrequencyCounter 的每次 put() 操纵均匀所需的比较次数
tale.txtleipzig1M.txt单词数不同单词数比较次数单词数不同单词数比较次数模型预测实际次数模型预测实际次数所有单词135 63510 67913.613.521 191 455534 58019.419.1长度大于等于 8 的单词14 3505 13112.612.14 239 597299 59318.718.4长度大于等于 10 的单词4 5822 26011.411.51 610 829165 55517.517.3
命题 H。一棵大小为 ![N/740943/image00798.gif) 的红黑树中，根结点到任意结点的均匀路径长度为 ![\sim1.00\lg N/740943/image01370.gif)。
例证。和典型的二叉查找树（比方图 3.2.8 中所示的树）相比，一棵典型的红黑树的平衡性是很好的，比方图 3.3.27 所示（甚至是图 3.3.28 中由升序键列构造的红黑树）。表 3.3.1 显示的数据表明 FrequencyCounter 在运行中构造的红黑树的路径长度（即查找本钱）比初等二叉查找树低 40% 左右，和预期符合。自红黑树的发明以来，无数的实行和实际应用都印证了这种性能改进。
![/740943/image01371.jpeg)
图 3.3.28　利用升序键列构造的一棵红黑树，没有画出空链接
以利用 FrequencyCounter 在处理长度大于等于 8 的单词时 put() 操纵的本钱为例，我们可以看到均匀本钱低沉得更多（如图 3.3.29 所示）。这又一次验证了理论模型所预测的对数级别的运行时间，只不过这次的惊喜比二叉查找树的小，因为性质 G 已经向我们包管了这一点。节约的总本钱低于在查找上节约的 40% 的本钱，因为除了比较我们也统计了旋转和颜色变换的次数。
![/740943/image01372.jpeg)
图 3.3.29　利用 RedBlackBST，运行 java FrequencyCounter 8 < tale.txt 的本钱
红黑树的 get() 方法不会检查结点的颜色，因此平衡性相关的操纵不会产生任何负担；因为树是平衡的，所以查找比二叉查找树更快。每个键只会被插入一次，但却大概被查找无数次，因此最后我们只用了很小的代价（和二分查找不同，我们可以包管插入操纵是对数级别的）就取得了和最优情况近似的查找时间（因为树是靠近完善平衡的，且查找过程中不会举行任何平衡性的操纵）。查找的内循环只会举行一次比较并更新一条链接，非常简短，和二分查找的内循环雷同（只有比较和索引运算）。这是我们见到的第一个可以大概包管对数级别的查找和插入操纵的实现，它的内循环更紧凑。它通过了各种应用的考验，包括许多库实现。
3.3.5.2　有序符号表 API

红黑树最吸引人的一点是它的实现中最复杂的代码仅限于 put()（和删除）方法。二叉查找树中的查找最大和最小键、 select()、 rank()、 floor()、 ceiling() 和范围查找方法 不做任何变动 即可继续利用，因为红黑树也是二叉查找树而这些操纵也不会涉及结点的颜色。算法 3.4 和这些方法（以及删除方法）一起完整地实现了我们的有序符号表 API。这些方法都能从红黑树近乎完善的平衡性中受益，因为它们最多所需的时间都和树高成正比。因此命题 G 和命题 E 一起包管了 所有操纵 的运行时间是对数级别的。
命题 I。在一棵红黑树中，以下操纵在最坏情况下所需的时间是对数级别的：查找（ get()）、插入（ put()）、查找最小键、查找最大键、 floor()、 ceiling()、 rank()、 select()、删除最小键（ deleteMin()）、删除最大键（ deleteMax()）、删除（ delete()）和范围查询（ range()）。
证明。我们已经讨论过 put()、 get() 和 delete() 方法。对于其他方法，代码可以从 3.2 节中照搬（它们不涉及结点颜色）。命题 G 和命题 E 可以包管算法是对数级别的，所有操纵在所颠末的结点上只会举行常数次数的操纵也说明白这一点。
各种符号表实现的性能总结如表 3.3.2 所示。
表 3.3.2　各种符号表实现的性能总结
算法（数据结构）最坏情况下的运行时间的增长数目级（ N 次插入之后）均匀情况下的运行时间的增长数目级（ N 次随机插入之后）是否支持有序性相关的操纵查找插入查找插入次序查询（无序链表）![/740943/image00798.gif)![/740943/image00798.gif)![/740943/image00986.gif)![/740943/image00798.gif)否二分查找（有序数组）![/740943/image00915.gif)![/740943/image00798.gif)![/740943/image00915.gif)![/740943/image00986.gif)是二叉树查找（BST）![/740943/image00798.gif)![/740943/image00798.gif)![/740943/image01317.gif)![/740943/image01317.gif)是2-3 树查找（红黑树）![/740943/image01224.gif)![/740943/image01224.gif)![/740943/image01373.gif)![/740943/image01373.gif)是
想想看，如许的包管是一个非凡的成就。在信息世界的汪洋大海中，表的大小大概上千亿，但我们仍可以大概确保在几十次比较之内就完成这些操纵。
答疑

问　为什么不允许存在红色右链接和 4- 结点？
答　它们都是可用的，并且已经应用了几十年了。在训练中你会遇到它们。只允许红色左链接的存在可以大概减少大概出现的情况，因此实现所需的代码会少得多。
问　为什么不在 Node 类型中利用一个 Key 类型的数组来表示 2- 结点、3- 结点和 4- 结点？
答　问得好。这正是我们在 B- 树（请见第６章）的实现中利用的方案，它的每个结点中可以保存更多的键。因为 2-3 树中的结点较少，数组所带来的额外开销太高了。
问　在分解一个 4- 结点时，我们偶然会在 rotateRight() 中将右结点的颜色设为 RED（红）然后立即在 flipColors() 中将它的颜色变为 BLACK（黑）。这不是浪费时间吗？
答　是的，偶然我们还会不必要地反复改变中结点的颜色。从整体来看，多余的几次颜色变换和将所有方法的运行时间的增长数目级从线性级别提升到对数级别不是一个级别的。当然，在有性能要求的应用中，你可以将 rotateRight() 和 flipColors() 的代码在所需要的地方展开来消除那些额外的开销。我们在删除中也会利用这两个方法。在可以大概包管树的完善平衡的条件下，它们更加轻易利用、理解和维护。
训练

3.3.1　将键 E A S Y Q U T I O N 按次序插入一棵空 2-3 树并画出结果。
3.3.2　将键 Y L P M X H C R A E S 按次序插入一棵空 2-3 树并画出结果。
3.3.3　利用什么次序插入键 S E A C H X M 可以大概得到一棵高度为 1 的 2-3 树？
3.3.4　证明含有 ![N/740943/image00798.gif) 个键的 2-3 树的高度在 ![\sim\lfloor\log_3N\rfloor/740943/image01374.gif) 即 ![0.63\lg N/740943/image01375.gif)（树完全由 3- 结点构成）和 ![\sim\lfloor\lg N\rfloor/740943/image01376.gif)（树完全由 2- 结点构成）之间。
3.3.5　右图显示了 ![N=1/740943/image01163.gif) 到 6 之间大小为 ![N/740943/image00798.gif) 的所有 不同的 2-3 树（无先后次序）。请画出 ![N=7/740943/image01377.gif)、8、9 和 10 的大小为 ![N/740943/image00798.gif) 的所有不同的 2-3 树。
![/740943/image01378.gif)
3.3.6　计算用 ![N/740943/image00798.gif) 个随机键构造训练 3.3.5 中每棵 2-3 树的概率。
3.3.7　以图 3.3.9 为例为图 3.3.8 中的其他 5 种情况画出相应的示意图。
3.3.8　画出利用三个 2- 结点和红链接一起表示一个 4- 结点的所有大概方法（不一定只能利用红色左链接）。
3.3.9　下图中哪些是红黑树（粗的链接为红色）？
![/740943/image01379.gif)
3.3.10　将含有键 E A S Y Q U T I O N 的结点按次序插入一棵空红黑树并画出结果。
3.3.11　将含有键 Y L P M X H C R A E S 的结点按次序插入一棵空红黑树并画出结果。
3.3.12　在我们的标准索引测试用例中插入键 P 并画出插入的过程中每次变换（颜色转换或是旋转）后的红黑树。
3.3.13　真假判定：如果你按照升序将键次序插入一棵红黑树中，树的高度是单调递增的。
3.3.14　用字母 A 到 K 按次序构造一棵红黑树并画出结果，然后大致说明在按照升序插入键来构造一棵红黑树的过程中发生了什么（可以参考正文中的图例）。
3.3.15　在键按照降序插入红黑树的情况下重新答复上面两道训练。
3.3.16　向右图所示的红黑树（黑色加粗部门的链接为红色）中插入 n 并画出结果（图中只显示了插入时的查找路径，你的解答中只需包罗这些结点即可）。
![/740943/image01380.gif)
3.3.17　随机生成两棵均含有 16 个结点的红黑树。画出它们（手绘或者代码绘制均可）并将它们和利用同一组键构造的（非平衡的）二叉查找树举行比较。
3.3.18　对于 2 到 10 之间的 ![N/740943/image00798.gif)，画出所有大小为 ![N/740943/image00798.gif) 的不同红黑树（请参考训练 3.3.5）。
3.3.19　每个结点只需要 1 位来保存结点的颜色即可表示 2- 结点、3- 结点和 4- 结点。利用二叉树，我们在每个结点需要几位信息才能表示 5- 结点、6- 结点、7- 结点和 8- 结点？
3.3.20　计算一棵大小为 ![N/740943/image00798.gif) 且完善平衡的二叉查找树的内部路径长度，其中 ![N/740943/image00798.gif) 为 2 的幂减 1。
3.3.21　基于你为训练 3.2.10 给出的答案编写一个测试用例 TestRB.java。
3.3.22　找出一组键的序列使得用它次序构造的二叉查找树比用它次序构造的红黑树的高度更低，或者证明如许的序列不存在。
进步题

3.3.23 没有平衡性限制的 2-3 树。利用 2-3 树（不一定平衡）作为数据结构实现符号表的基本 API。树中的 3- 结点中的红链接可以左斜也可以右斜。树底部的 3- 结点和新结点通过 黑色 链接相连。实行并估计随机构造的如许一棵大小为 ![N/740943/image00798.gif) 的树的均匀路径长度。
3.3.24 红黑树的最坏情况。找出如何构造一棵大小为 ![N/740943/image00798.gif) 的最差红黑树，其中从根结点到险些所有空链接的路径长度均为 ![2\lg N/740943/image01224.gif)。
3.3.25 自顶向下的 2-3-4 树。利用平衡 2-3-4 树作为数据结构实现符号表的基本 API。在树的表示中利用红黑链接并实现正文所述的插入算法，其中在沿查找路径向下的过程中分解 4- 结点并举行颜色转换，在回溯向上的过程中将 4- 结点配平。
3.3.26 自顶向下一遍完成。修改你为训练 3.3.25 给出的答案， 倒霉用 递归。在沿查找路径向下的过程中分解并平衡 4- 结点（以及 3- 结点），最后在树底插入新键即可。
3.3.27 允许红色右链接。修改你为训练 3.3.25 给出的答案，允许红色右链接的存在。
3.3.28 自底向上的 2-3-4 树。利用平衡 2-3-4 树作为数据结构实现符号表的基本 API。在树的表示中利用红黑链接并用和算法 3.4 相同的递归方式实现 自底向上 的插入。你的插入方法应该只需要分解查找路径底部的 4- 结点（如果有的话）。
3.3.29 最优存储。修改 RedBlackBST 的实现，用下面的技巧实现无需为结点颜色的存储利用额外的空间：要将结点标记为红色，只需交换它的左右链接。要检测一个结点是否是红色，检测它的左子结点是否大于它的右子结点。你需要修改一些比较语句来适应链接的交换。这个技巧将变量的比较变成了键的比较，显然本钱会更高，但它说明在需要的情况下这个变量是可以被删掉的。
3.3.30 缓存。修改 RedBlackBST 的实现，将近来访问的结点 Node 保存在一个变量中，如许 get() 或 put() 在再次访问同一个键时就只需要常数时间了（请参考训练 3.1.25）。
3.3.31 树的绘制。为 RedBlackBST 添加一个 draw() 方法，像正文一样绘制出红黑树。
3.3.32 AVL 树。AVL 树是一种二叉查找树，其中任意结点的两棵子树的高度最多相差 1（最早的平衡树算法就是基于利用旋转保持 AVL 树中子树高度的平衡）。证明将其中由高度为偶数的结点指向高度为奇数的结点的链接设为红色就可以得到一棵（完善平衡的）2-3-4 树，其中红色链接可以是右链接。 附加题：利用 AVL 树作为数据结构实现符号表的 API。一种方法是在每个结点中保存它的高度并在递归调用后利用旋转来根据需要调解这个高度；另一种方法是在树的表示中利用红黑链接并利用雷同训练 3.3.39 和训练 3.3.40 的 moveRedLeft() 和 moveRedRight() 的方法。
3.3.33 验证。为 RedBlackBST 实现一个 is23() 方法来检查是否存在同时和两条红链接相连的结点和红色右链接，以及一个 isBalanced() 方法来检查从根结点到所有空链接的路径上的黑链接的数目是否相同。将这两个方法和训练 3.2.32 的 isBST() 方法联合起来实现一个 isRedBlackBST() 来检查一棵树是否是红黑树。
3.3.34 所有的 2-3 树。编写一段代码来生成高度为 2、3 和 4 的所有结构不同的 2-3 树，分别共有 2、7 和 122 种（ 提示：利用符号表）。
3.3.35 2-3 树。编写一段程序 TwoThreeST.java，利用两种结点类型来直接表示和实现 2-3 查找树。
3.3.36 2-3-4-5-6-7-8 树。说明平衡的 2-3-4-5-6-7-8 树中的查找和插入算法。
3.3.37 无记忆性。请证明红黑树不是 没有记忆 的。比方，如果你向树中插入一个小于所有键的新键，然后立即删除树的最小键，你大概得到一棵不同的树。
3.3.38 旋转的基础定理。请证明，利用一系列左旋转或者右旋转可以将一棵二叉查找树转化为由同一组键生成的其他任意一棵二叉查找树。
3.3.39 删除最小键。实现红黑树的 deleteMin() 方法，在沿着树的最左路径向下的过程中实现正文所述的变换，包管当前结点不是 2- 结点。
解答：
  1. private Node moveRedLeft(Node h)
  2. {  // 假设结点h为红色，h.left和h.left.left都是黑色，
  3.    // 将h.left或者h.left的子结点之一变红
  4.    flipColors(h);
  5.    if (isRed(h.right.left))
  6.    {
  7.       h.right = rotateRight(h.right);
  8.       h = rotateLeft(h);
  9.    }
  10.    return h;
  11. }
  12. public void deleteMin()
  13. {
  14.    if (isRed(root.left) && !isRed(root.right))
  15.       root.color = RED;
  16.    root = deleteMin(root);
  17.    if (!isEmpty()) root.color = BLACK;
  18. }
  19. private Node deleteMin(Node h)
  20. {
  21.    if (h.left == null)
  22.       return null;
  23.    if (!isRed(h.left) && !isRed(h.left.left))
  24.       h = moveRedLeft(h);
  25.    h.left = deleteMin(h.left);
  26.    return balance(h);
  27. }
复制代码
其中的 balance() 方法由下一行代码和算法 3.4 的递归 put() 方法中的最后 5 行代码构成：
  1. if (isRed(h.right)) h = rotateLeft(h);
复制代码
这里的 flipColors() 方法将会补全三条链接的颜色，而不是正文中实现插入操纵时实现的 flipColors() 方法。对于删除，我们会将父结点设为 BLACK（黑）而将两个子结点设为 RED（红）。
3.3.40 删除最大键。实现红黑树的 deleteMax() 方法。需要注意的是因为红链接都是左链接，所以这里用到的变换和上一道训练中的稍有不同。
解答：
  1. private Node moveRedRight(Node h)
  2. {  // 假设结点h为红色，h.right和h.right.left都是黑色，
  3.    // 将h.right或者h.right的子结点之一变红
  4.    flipColors(h)
  5.    if (!isRed(h.left.left))
  6.       h = rotateRight(h);
  7.    return h;
  8. }
  9. public void deleteMax()
  10. {
  11.    if (!isRed(root.left) && !isRed(root.right))
  12.       root.color = RED;
  13.    root = deleteMax(root);
  14.    if (!isEmpty()) root.color = BLACK;
  15. }
  16. private Node deleteMax(Node h)
  17. {
  18.    if (isRed(h.left))
  19.        h = rotateRight(h);
  20.    if (h.right == null)
  21.       return null;
  22.    if (!isRed(h.right) && !isRed(h.right.left))
  23.       h = moveRedRight(h);
  24.    h.right = deleteMax(h.right);
  25.    return balance(h);
  26. }
复制代码
3.3.41 删除操纵。将上两题中的方法和二叉查找树的 delete() 方法联合起来，实现红黑树的删除操纵。
解答：
  1. public void delete(Key key)
  2. {
  3.    if (!isRed(root.left) && !isRed(root.right))
  4.       root.color = RED;
  5.    root = delete(root, key);
  6.    if (!isEmpty()) root.color = BLACK;
  7. }
  8. private Node delete(Node h, Key key)
  9. {
  10.    if (key.compareTo(h.key) < 0)
  11.    {
  12.       if (!isRed(h.left) && !isRed(h.left.left))
  13.          h = moveRedLeft(h);
  14.       h.left =  delete(h.left, key);
  15.    }
  16.    else
  17.    {
  18.       if (isRed(h.left))
  19.          h = rotateRight(h);
  20.       if (key.compareTo(h.key) == 0 && (h.right == null))
  21.          return null;
  22.       if (!isRed(h.right) && !isRed(h.right.left))
  23.          h = moveRedRight(h);
  24.       if (key.compareTo(h.key) == 0)
  25.       {
  26.          h.val = get(h.right, min(h.right).key);
  27.          h.key = min(h.right).key;
  28.          h.right = deleteMin(h.right);
  29.       }
  30.       else h.right = delete(h.right, key);
  31.    }
  32.    return balance(h);
  33. }
复制代码
实行题

3.3.42 统计红色结点。编写一段程序，统计给定的红黑树中红色结点所占的比例。对于 ![N=104/740943/image01337.gif)、![105/740943/image00848.gif) 和 ![10^6/740943/image00849.gif)，用你的程序统计至少 100 棵随机构造的大小为 ![N/740943/image00798.gif) 的红黑树并得出一个猜想。
3.3.43 本钱图。改造 RedBlackBST 的实现来绘制本节中可以大概显示计算中每次 put() 操纵的本钱的图（请参考训练 3.1.38）。
3.3.44 均匀查找用时。用实行研究和计算在一棵由 ![N/740943/image00798.gif) 个随机结点构造的红黑树中到达一个随机结点的均匀路径长度（内部路径长度除以 ![N/740943/image00798.gif) 再加 1）的均匀差和标准差，对于 1 到 10 000 之间的每个 ![N/740943/image00798.gif) 至少重复实行 1000 遍。将结果绘制成和图 3.3.30 相似的 Tufte 图，并画上函数 ![\lg N-0.5/740943/image01381.gif) 的曲线。
![/740943/image01382.jpeg)
图 3.3.30　随机构造的红黑树中到达一个随机结点的均匀路径长度
3.3.45 统计旋转。改进你为训练 3.3.43 给出的程序，用图像绘制出在构造红黑树的过程中旋转和分解结点的次数并讨论结果。
3.3.46 红黑树的高度。改进你为训练 3.3.43 给出的程序，用图像绘制出所有红黑树的高度并讨论结果。
本文由博客一文多发平台 OpenWrite 发布！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/) Powered by Discuz! X3.4