# 第九章 平衡搜索 > 译者：[Abel-Huang](https://github.com/Abel-Huang) 我们之前已经看到二叉搜索树有一个弱点：左右子树趋向于不平衡，因此无法将它们所表示的数据集划分成两个同样大小的部分。我们考虑一下我们可以对此做些什么改进。 当然，我们总是可以通过简单地将所有节点按顺序进行排序，然后重新插入它们以生成一个新的平衡二叉树。然而这种操作需要花费树节点数线性规模的复杂度，并且可以看出在 插入N个元素很难避免退化为$\Theta(N^2)$的复杂度。相比之下，如果数据碰巧以保持树遍历的顺序，则进行N次插入仅需要$\Theta(N\lgN)$的时间。因此，让我们首先看看重新平衡树(或保持平衡)的操作，而不将其拆开并重新构建。 ## 9.1 平衡构造：B-树 保持搜索树平衡的另一种方法是始终小心"在一个正确的位置插入新的树节点"，以便树通过构造器保持平衡。数据库社区长期以来一直使用完全符合这个要求的数据结构：*B-tree*。我们将在这里抽象地描述这种数据结构和相关操作，而不是直接给出代码，因为这种数据结构用于实践中大量用于提高速度的存储设备。 *m阶B-树*是具有以下属性的多叉树： 1. 每个节点孩子数最多为m个。 2. 除根之外的所有节点至少有m/2个子节点(我们也可以说除根节点外的每个节点至少包含⌈m/2⌉个子节点)。 3. 一个节点的孩子$C_0$, $C_1$, ..., $C_(n-1)$用键$K_1$, ..., $K_(n-1)$标记(认为$K_i$在$C_(i-1)$和$C_i$之间)，其中$k_1$<$k_2$<...<$k_(n-1)$； 4. B-树是一种搜索树：对于任何一个节点，以$C_i$为根的子树中所有键都严格地小于$K_(i+1)$，并且(对于i > 0)严格地大于$K_i$。 5. 所有空孩子都出现在树的同一层。 图9.1包含一个4阶排序树的示例。在实际实现中，B-树一般用在在二级存储（如磁盘等）上，根据实际需要读入它们的节点。我们选择m阶树(多叉数)的目的是尽可能快地从二级存储器传输数据。对于磁盘操作而言更关注的是单次磁盘访问所需要时间越小越好， 因此m的值范围越大，从不同节点中读取的时间差异越小。在这种情况下，**m**取的值过小很明显不是一个很好的主意。__ 我们将用一个被称为**BTreeNode**的结构来表示B-树的节点，并且有如下的定义： **B.child(i)**：B-树节点**B**的第*i*个孩子，**0 <= i < m**。 **B.key(i)**：B-树节点**B**的第*i*个关键字Key，**1 <= i < m**。 **B.parent()**：B-树节点**B**的父节点。 **B.index()**：B-树节点**B**的索引*i*，**B == B.parent().child(i)**。 **B.arity()**：B-树节点**B**的孩子数。 然后，整个B-树由指向根的指针组成，可能还包含一些额外的有用信息，例如B-树当前的大小。 基于属性2和属性5，一个拥有N个关键字的B-树一定有$\Theta(\log_(m/2)N)$层节点。基于属性1，搜索单个节点的关键字需要O(1)时间(保证m为固定值)。因此通过下面的递归算法搜索B-树是一个$\Theta(\lgN)$级别的操作。 ```java boolean search (BTreeNode B, Key X) { if (B is the empty tree) return false; else { Find largest c such that B.key(i) ≤ X, for all 1 ≤ i ≤ c. if (c > 0 && X.equals (B.key (c))) return true; else return search (B.child (c), K); } ``` ![figure_9_1](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_1.png) 图9.1: 键为整型的4阶B-树示例。圆圈代表空节点，它们出现在树的同一层级。每个节点拥有2到4个子节点，每个节点用于1到3个关键字。每个键都大于其左侧子节点中的所有键，并且小于右侧子节点中的所有键。 ### 9.1.1 插入 最初，我们插入B树的底部，就像二叉搜索树一样。但是我们通过节点填充和分离来避免树的深度扩展，防止出现"scrawny" 的情形，即每层树节点过少。这个想法很简单：我们在树的底部找到一个合适的位置来插入给定的键，并执行插入 操作(还添加一个额外的空孩子)。如果这使得节点太大(因为它有**m**个键和**m+1**(空)子节点)，我们会对节点进行分裂，具体的代码在图9.2中。图9.3说明了该过程。 ### 9.1.2 删除 从B-树中删除通常比插入操作更复杂，但也不是太糟糕。和之前一样，在真实的产品实现中，为了提升速度会引入更多复杂的内容。为了简单起见，我将描述一种简单，理想化的方法。从插入的工作方式中获得启发，我们首先将待删除的键移动到树的底部(删除很简单)。然后，如果删除后使得原始节点太小，我们将其与兄弟节点合并，拉下用于将两者与父节点分开的关键字。图9.4中的伪代码描述了该过程，如图9.5所示。 ![figure_9_2](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_2.jpg) 图9.2：B-树节点分裂。图9.3是过程示意图。 ![figure_9_3](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_3.jpg) 图9.3：B-树插入操作。在图9.1所示的B-树上进行插入操作，分别插入15，145和35三个关键字。 ![figure_9_4](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_4.jpg) 图9.4：B-树删除操作。图9.5是过程示意图。 ![figure_9_5](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_5.jpg) 图9.5：B-树删除操作。这个示例基于图9.3中的(c)部分。在(a)中，我们删除了关键字25。首先，移动25到底部并与其子节点合并。然后，删除关键字25，如果合并后的节点过大，我们需要进行分裂，并将关键字15提升为父节点。接下来，(b)在(a)删除的基础上，删除关键字10。从底部节点删除10会使该节点变小小，因此我们合并它，从父节点向下移动关键字15。这样会导致父节点变小，因此我们继续进行合并，将关键字35从根节点往下移动，得到最终的树。 ### 9.1.3 红黑树：二分查找的(2, 4)树 一般B-树使用的节点实际上是关键字的有序数组。有序4阶B-树(也称为(2,4)树)，这种我们一般也称为红黑树。每一个(2,4)树会被映射成一个特定的二叉树，使得每个(2,4)树节点对应于1-3个二叉搜索树节点组成的小集群。因此，二叉搜索树大致平衡，从根节点到叶子节点的所有路径的长度最多相差2倍。图9.6显示了每个可能的(2,4)节点的表示。在一棵完整树中，我们可以仅在每个群集的根节点中设置布尔值来确定群集的边界。但是，习惯上我们将此布尔值为true的节点（以及空叶节点）描述为“黑色”，将其他节点描述为“红色”。 通过考虑图9.6和（2,4）树的结构，你可以推导出红黑树是二叉搜索树，它还遵循以下约束(在红黑树的标准处理中作为它们的定义)： A. 根节点和所有（null）叶子节点都是黑色的。 B. 红色节点的子节点都是黑色节点； C. 从根节点到叶子节点的任何路径都遍历相同数量的黑色节点。 同样，属性B和C表明红黑树是“bushy”的，即红黑树是平衡的。 当然，红黑树的搜索过程与普通的二叉树搜索相同。由于图中所示的(2,4)树和红黑树之间的映射，插入操作和删除操作的算法可以从用于4阶B-树的算法中推导出。红黑树的常用操作的实现通常不直接使用此对应关系，对于基本的操作视作普通的二叉搜索树操作，然后通过旋转重新平衡(参见§9.3)，根据当前节点及其相邻节点的颜色的重新着色。我们不会在这里详述。 ## 9.2 字典树 一般来说，在一个包含N个关键字的平衡的二叉搜索树中查找某个特定的关键字所需时间为$\Theta(\lgN)$。当然这并不是完全正确的，因为可能忽略了关键字之间进行比较所花费的时间。例如，比较两个字符串所需要的时间取决于较短的那个串的长度。因此，我再此之前说到的"$\Theta(\lgN)$"都是指$\Theta(L\lgN)$，其中L是指关键字所包含的字节数。 在大多数应用中，这并不重要，因为L相对于N，L的增长速度而言几乎可以忽略。尽管如此，我们想到一个有趣的问题： 显然，在这里我们不能轻易忽略L这个因素的影响(具体取决于你正在查找的这个关键字)，但是我们是否可以摆脱$\lgN$的影响吗？ ![figure_9_6](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_6.jpg) 图9.6：带有"红黑"节点的二叉树(2,4)节点的表示。左边是单个(2,4)节点的三种情形(1到3个关键字，或者2到4个子节点)。在右边是其对应的二叉查找树。在每一种情形下，顶部的二叉节点被涂成黑色，其他的节点均为红色。 ### 9.2.1 字典树: 基本属性和算法 这个结果说明我们可以通过字典树*trie*这种数据结构来避免$\lgN$的影响。一个纯粹的字典树是一种树，由一些固定大小的字符组成的字符串表示，A = {$a_0$，$a_1$，...，$a_(M-1)$}。其中一个字符是只出现在单词末尾的特殊分隔符，'□'。例如，A可能是一组可打印的ASCII字符，'□'表示一个不能打印的字符，例如'\000'(NUL)。一棵字典树T，可以被下面的方式抽象的递归定义。 1. 空； 2. 一个叶子节点包含一个字符串； 3. 一个内部结点包含M个孩子也是字典树。通向这些孩子的边界用字母表中的字符标记，$a_i$，像这样：$C_(a_0)$，$C_(a_1)$，... $C_(a_(m-1))$。 我们可以认为字典树是叶子节点由字符串组成的树。除此外我们还附加了另外一个条件： * 如从字典树的根开始，并且接下来的边标记为$s_0$，$s_1$，...，$s_(h-1)$，我们访问到的每一个字符串为$s_0$$s_1$$s_(h-1)$。 因此，可以将字典树的每个内部节点看作是它下面叶中所有字符串的前缀：具体地说，k级的内部节点代表其下每个字符串的前k个字符。 如果字典树T中从T的根节点开始，并且接下来的0个或者更多的边使用$s_0$，$s_1$，...，$s_(h-1)$标记，一个字符串S=$s_0$$s_1$$s_(m-1)，我们得到了这个字符串S。我们将假设T中的所有字符串都以'□'结尾，它只作为字符串的最后一个字符出现。 ![figure_9_7](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_7.jpg) 图9.7：包含一些列字符串的字典树{a, abase, abash, abate，abbas， axe，axolotl，fabric，facet}。内部节点被标记为显示它们对应的字符串前缀。 ![figure_9_8](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_8.jpg) 图9.8：图9.7中字符串"bat"和"faceplate"插入后的结果。 图9.7表示了一个一组小规模字符串的字典树。为了查看字符串是否在集合中，我们从字典树的根开始，沿着用我们要查找的字符串中的连续字符标记的边(连接接到子节点),包括末尾的虚拟字符'□'。如果我们沿着这条路径成功地找到了一个字符串，它等于我们要搜索的字符串，那么我们要搜索的字符串就在字典树中，否则我们要找的这个字符串就不在其中。对于每个单词，我们只需要内部节点，因为存储的多个单词以遍历到该点的字符开头。以特殊字符结束一切事物的惯例允许我们区分三个词包含两个词的情况，一个词是另一个词的前缀（如“a”和“abate”），而三个词只包含一个长词。 从字典树用户的角度来看，它看起来像一种带有字符串标签的树： ```java public abstract class Trie { /** The empty Trie. */ public static final Trie EMPTY = new EmptyTrie(); /** The label at this node. Defined only on leaves. */ abstract public String label(); /** True if X is in this Trie. */ public boolean isIn(String x) ... /** The result of inserting X into this Trie, if it is not * already there, and returning this. This trie is * unchanged if X is in it already. */ public Trie insert(String x) ... /** The result of removing X from this Trie, if it is present. * The trie is unchanged if X is not present. */ public Trie remove(String x) ... /** True if this Trie is a leaf (containing a single String). */ abstract public boolean isLeaf(); /** True if this Trie is empty */ abstract public boolean isEmpty(); /** The child numbered with character K. Requires that this node * not be empty. Child 0 corresponds to ✷. */ abstract public Trie child(int k); /** Set the child numbered with character K to C. Requires that * this node not be empty. (Intended only for internal use. */ abstract protected void setChild(int k, Trie C); } ``` 接下来的算法描述了字典树的搜索过程： ```java /** True if X is in this Trie. */ public boolean isIn(String x) { Trie P = longestPrefix(x, 0); return P.isLeaf() && x.equals(P.label()); } /** The node representing the longest prefix of X.substring(K) that * matches a String in this trie. */ private Trie longestPrefix(String x, int k) { if (isEmpty() || isLeaf()) return this; int c = nth(x, k); if (child(c).isEmpty()) return this; else return child(c).longestPrefix(x, k+1); } /** Character K of X, or ✷ if K is off the end of X. */ static char nth(String x, int k) { if (k >= x.length()) return (char) 0; else return x.charAt(k); } ``` 从以下步骤可以清楚地看出，寻找关键字所需的时间与关键字的长度成正比。事实上，需要遍历的字典树的数量级别可以大大小于键的长度，特别是在存储的关键字的数量很少的情况下。但是，如果字符串在字典树中，则必须查看其所有字符，因此*isIn*方法的最坏时间复杂度为$\Theta(x.length)$。 为了在字典树中插入关键字X，我们再次在字典树中查找X的最长前缀，它对应于某个节点P。然后，如果P是一个叶子，我们插入足够多的内部节点来区分X和*P.label()*。否则，我们可以在P节点的适当子元素中插入X的叶子节点。图9.8表示字符串"bat"和"faceplate"插入图9.7后的结果。添加"bat"只需要向现有节点添加一个叶子。添加"faceplate"需要先插入两个新节点。 下面的方法是字典树的插入方法*insert()*。 ```java /** The result of inserting X into this Trie, if it is not * already there, and returning this. This trie is * unchanged if X is in it already. */ public Trie insert(String X){ return insert(X, 0); } /** Assumes this is a level L node in some Trie. Returns the * result of inserting X into this Trie. Has no effect (returns * this) if X is already in this Trie. */ private Trie insert(String X, int L) { if (isEmpty()) return new LeafTrie(X); int c = nth(X, L); if (isLeaf()) { if (X.equals(label())) return this; else if (c == label().charAt(L)) return new InnerTrie(c, insert(X, L+1)); else { Trie newNode = new InnerTrie(c, new LeafTrie(X)); newNode.child(label().charAt(L), this); return newNode; } } else { child(c, child(c).insert(X, L+1)); return this; } } ``` 这里是**InnerTrie(c, T)** 的构造器，用于提供一个其中**child(c)** 为T,其他子节点为空的字典树。 从字典树中删除一个节点使该过程的逆过程。每当一个字典树节点被减少到包含一个叶子时，它就可以被那个叶子代替。以下程序表示该过程： ```java public Trie remove(String x){ return remove(x, 0); } /** Remove x from this Trie, which is assumed to be level L, and * return the result. */ private Trie remove(String x, int L){ if (isEmpty()) return this; if (isLeaf(T)) { if (x.equals(label())) return EMPTY; else return this; } int c = nth(x, L); child(c, child(c).remove(x, L+1)); int d = onlyMember(); if (d >= 0) return child(d); return this; } /** If this Trie contains a single string, which is in * child(K), return K. Otherwise returns -1. */ private int onlyMember() { /* Left to the reader. */ } ``` ### 9.2.2 字典树: 表示 我们剩下的问题是如何表示这些字典树。当然，主要的困难在于节点所包含的子节点数量是可变的。如果每个节中子节点的数量较少，那么可以使用5.2节中描述链表树。但是，为了快速访问，传统上使用数组来保存节点的子节点，并通过标记边缘的字符进行索引。 这会导致如下情况： ```java class EmptyTrie extends Trie { public boolean isEmpty() { return true; } public boolean isLeaf() { return false; } public String label() { throw new Error(...); } public Trie child(int c) { throw new Error(...); } protected void child(int c, Trie T) { throw new Error(...); } } class LeafTrie extends Trie { private String L; /** A Trie containing just the string S. */ LeafTrie(String s) { L = s; } public boolean isEmpty() { return false; } public boolean isLeaf() { return true; } public String label() { return L; } public Trie child(int c) { return EMPTY; } protected void child(int c, Trie T) { throw new Error(...); } } class InnerTrie extends Trie { // ALPHABETSIZE has to be defined somewhere */ private Trie[] kids = new kids[ALPHABETSIZE]; /** A Trie with child(K) == T and all other children empty. */ InnerTrie(int k, Trie T) { for (int i = 0; i < kids.length; i += 1) kids[i] = EMPTY; child(k, T); } public boolean isEmpty() { return false; } public boolean isLeaf() { return false; } public String label() { throw new Error(...); } public Trie child(int c) { return kids[c]; } protected void child(int c, Trie T) { kids[c] = T; } } ``` ### 9.2.3 表压缩 实际上，我们的字母表中可能有一些“漏洞”，这些编码的延伸部分与我们插入的字符串中出现的任何字符都不对应。 我们可以通过执行字符到压缩编码的初步映射来减少内部节点(子数组)的大小。例如，如果字符串中的字符是仅仅是数字0–9，则可以按如下方式重构**InnerTrie** ： ```java class InnerTrie extends Trie { private static char[] charMap = new char[’9’+1]; static { charMap[0] = 0; charMap[’0’] = 1; charMap[’1’] = 1; ... } public Trie child(int c) { return kids[charMap[c]]; } protected void child(int c, Trie T) { kids[charMap[c]] = T; } } ``` 这是有帮助的，但即便如此，可以用键中所有有效字符索引的数组可能相对较大(对于树节点)，例如m=60字节的顺序，即使对于只能包含数字的节点(假设每个指针有4个字节，每个对象有4个字节的开销，数组中的长度字段有4个字节)。如果所有键中总共有N个字符，那么所需的空间将以大约NM/2为界。只有在高度相似的情况下才能达边界(其中字典树只包含两个非常长的字符串，除了最后一个字符外，这些字符串是相同的)。然而，在字典树中的数组可能依然非常稀疏。 解决这个问题的一种方法是压缩表。这尤其适用于在容纳一些初始化字符串集后，插入很少的情况。顺便说一下，下面描述的技术通常适用于任何这样的稀疏数组，而不仅仅是字典树。 其基本思想是，稀疏数组(即那些主要包含空或“空”项的数组)可以通过确保其中一个非空项落在另一个空项的顶部而相互覆盖。我们将所有数组分配到一个大数组中，并在每个条目中存储额外的信息，这样我们就可以知道该条目所属的重叠数组中的哪一个。图9.9显示了适当的替代数据结构。 我们的想法是，当我们将每个节点的孩子数组存储在一起，并存储一个边缘标签，告诉我们每个字符应该对应哪个节点。这使得我们能够区分不同节点之间对应的字符。我们通过确保第0个子节点（对应于）始终满来安排每个节点的Me字段是唯一的。 作为一个例子，图9.10显示了图9.8中重叠在一起的字典树的十个内部节点。如图所示，这种表示可以非常紧凑。 右侧所需的额外空条目数量（防止索引数组越界）限制为M−1，因此当数组足够大时，可以忽略不计。(旁白：当希望以这种方式处理一组压缩的数组时，最好先分配一个满数组(最少稀疏)。) 如此精密的封装是有代价的：这将使插入操作变得很复杂。当向现有节点添加新的子节点时，所需的槽可能已被其他数组使用，首先从打包的存储区域中删除非空条目，从而有必要将节点移动到新位置。找到另一个点并将其条目移动到该点，最后更新指向父节点中正在移动的节点的指针。有一些方法可以消除这种情况，但我们不会在这里讨论它们。 ## 9.3 旋转自平衡树 另一种二叉树平衡的方法是通过选择一个新的根节点，将子树高度较深一侧的节点移动到子树高度较低的一侧从而达到平衡，并且依然保持二叉搜索树的属性。 最简单的实现方式就是树的**旋转(rotations)**。图9.11展示了两棵节点元素集合相同的二叉搜索树。首先考虑右旋转(左旋转是镜像操作)。首先，旋转之后依然需要保证二叉树的属性，在未旋转的树中，A节点小于右侧的B节点，D节点大于 B节点，而且右子树C节点也是大于B节点的。你需要保证，在进行旋转后D节点下面的子节点仍然保持二叉树的性质。 ![figure_9_9](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_9.jpg) 图9.9：使用压缩字典树的数据结构。 让我们使用符号$\H_A$，$\H_C$，$\H_E$，$\H_B$和$\H_D$来表示子树A，C和E以及根是节点B和D的子树的高度。子树A，C，E可以为空，这种情况下我们将其高度设为-1。左边树的高度为1+max($\H_E$, 1 + $\H_A$, 1 + $\H_C$ )。右边树的高度为1+max($\H_A$, 1 + $\H_C$, 1 + $\H_E$ )。因此，只要$\H_A$ > max($\H_C$ + 1, $\H_E$)(例如，在左倾树中就会出现这种情况)，右侧树的高度将小于左侧树的高度。另一个方向也是相似的情况。 实际上，可以通过旋转将任何二叉搜索树转换为任何其他包含相同键的二叉搜索树。这相当于通过旋转，我们可以将二叉搜索树的任何节点移动到树的根节点，同时保留二叉搜索树属性(为什么这是一个充分条件？)。这个论点是对树结构的归纳。 * 对于空树或者只有根节点的树显然是成立。 * 对于一个更大的树，我们假设可以旋转所有较小的树以使它们的任何节点成为根节点，进行如下假设： * 如果我们期望的新的根节点已经是根节点，那么我们就完成该操作； * 如果我们期望的新的根节点在左子树(归纳假设)，然后在整个树上执行右旋转； * 如果该节点在右子树会进行类似的操作。 ### 9.3.1 AVL树 当然，知道通过旋转可以重排列二叉搜索树，但是我们并不知道如何具体进行旋转操作。AVL树是该技术的一种具体示例，用于跟踪子树的高度并在它们差距过大时执行旋转操作。AVL树是一种二叉搜索树，并且满足**AVL属性** :任意节点的左子树和右子树的高度差小于1。 在这种树的底部增加或者删除节点(正如6.1节点简单二叉搜索树的插入和删除操作)会破坏所谓的AVL属性，但是可以通过从插入或删除点开始向根处理并执行某些选定的旋转来恢复，这取决于需要纠正的不平衡的性质。在下面的图示中，子树中的表达式代表它们的高度。 ![figure_9_A](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_A.jpg) 一个不平衡的子树可以通过单次做旋转重新平衡，如下图所示的AVL树形式： ![figure_9_B](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_B.jpg) 最后我们在考虑一个不平衡的二叉树的示例 ![figure_9_C](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_C.jpg) $\h^'$和$\h^''$中至少有一个是h，并且另外一个也是h或者h-1。这里我们可以通过两次旋转实现平衡，首先是在节点C进行右旋转，然后在节点进行左旋转，得到正确的AVL树 ![figure_9_D](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_D.jpg) 另外可能的通过增加或者删除单个节点导致的重新平衡是上述的镜像操作。 因此，我们跟踪所有子树的高度，我们总是可以恢复AVL属性，从树的底部插入或删除的点开始并向上进行旋转实现平衡。事实上证明，我们没有必要知道所有子树精确的高度，仅仅需要每个节点属于三种情况：两棵子树有相同的高度，左子树比右子树高度高一层，或者左子树比右子树高度低一层。 ## 9.4 伸展树 旋转允许我们在保持二叉树的属性的前提下，尽可能的将二叉树的节点移动到离根节点更近的位置。因此，至少我们可以在不平衡树中使用旋转来快速查找经常搜索的关键字。事实证明，我们可以做的更好。伸展树(Splay Tree)是一种自调整二叉搜索树，即使不通过改变树内容的操作也可以调整其结构以加速后续操作。这种数据结构具有一些有趣的特性，即某些单独的操作可能花费$\Theta(N)$时间(对于树中的N个节点)，但是对于K个同样操作的均摊时间成本(参考1.4节点)仍然是$\Theta(\lgK)。此外，它是基础(不平衡)二叉搜索树的特别简单的修改。 不出所料，此树中的定义操作是splaying，以特定方式将特定节点旋转成根节点。伸展节点意味着使用一系列展开步骤，以便将节点置于树的顶部。伸展具体有三种类型： 1. 给定节点**t** **y** 是其子节点之一，围绕**t** 旋转**y** (即，根据需要向左或向右旋转，以使**y** 到达顶部)。 2. 给定一个节点**t** ，它的一个子节点**y** 和**y** 的子节点**z** 在同一侧，然后绕**y** 旋转**z** 。 3. 给定一个节点**t**，它的一个子节点**y** 和**y** 的子节点**z** 在不同侧，先围绕**y**旋转**z**，然后绕**t**旋转。 图9.12展示了这具体的三种步骤。 我们通常会从二叉搜索树根节点开始的遍历查找给定值，从而找到接受此操作的节点。要了解这种特定操作背后的动机，请考虑图9.13。 图左侧的树是典型的最坏时间复杂度的二叉搜索树。在展开节点0之后，我们得到图右侧的树，其大约是前者的一半高度。确实，我们必须进行7次旋转以伸展此节点，但是为了在左侧创建树，我们进行了8次常数时间的插入，因此(到目前为止)，所有9次操作的摊销成本(8次插入加1次))每个只有2个左右。 从普通二叉搜索树中搜索，插入和删除的操作都涉及搜索包含特定值的节点，或者尽可能接近特定值的节点。在伸展树中，找到此节点后，我们将其展开，将其带到树的根部并重新组织树的其余部分。为此，可以方便地修改用于在BST中搜索值的通常算法，以便它同时适用于伸展树。图9.15显示了一种在BST类型的树上可能的实现方式，如图9.14所示。这种特殊类型提供了旋转和替换将执行左或右操作的子节点的操作，允许我们将案例嵌套折叠成几个。 **splayFind** 函数是我们可以用来在二叉搜索树上实现通用操作的工具，如图9.16和9.17所示。 ### 9.4.1 伸展树分析 创建非常不平衡的伸展树很容易。按顺序向树中插入数据项就可以实现。因此，将按顺序搜索树中的所有数据项。因此，如果N是树中节点（及关键字）的数量，则隔离的任何特定操作的代价是θ(N)。但是，你永远不会在一棵大树上执行单个操作；毕竟，你必须先创建树，而这当然必须花费至少与其大小成比例的时间。因此，如果我们要求在整个序列上分摊操作的时间，我们可能会得到不同的结果。在本节中，我们将展示实际上在伸展树上搜索，插入和删除操作的分摊时间界限为O(lgN)，就像其他平衡二叉树的最坏情况边界一样。 为此，我们首先在树上定义一个势函数，如§1.4所述，它将跟踪我们执行了多少便宜（和不平衡）操作，从而表明我们可以花多少时间在 昂贵的操作上，同时仍然保证一系列操作的总累积代价保持在适当的限制内。正如我们在公式1.1所做的，我们定义序列中第i个操作的摊余成本ai为 ci为实际的开销，φk是第k次操作之前数据结构中“存储电位”的数量。对于ci，我们可以很方便用旋转执行的次数来表示，当一个操作不涉及旋转时用1表示。这为我们提供了与实际工作量成比例的ci值。挑战是我们要找到一个φ允许我们吸收ci的峰值;当ai>ci时，我们保存φ中的“操作信用”并在ci变大的步骤中释放它（导致φ(i + 1) <φi）。 为了合适，我们必须一直确保φi>φ0。 对于包含一组节点的伸展树T，我们将使用它作为我们的势函数 其中s(x)是以x为根的子树的大小（节点数）。r(x) = lgs(x)称为x的等级。 因此，对于图9.13左侧的完全线性树，φ = P1≤i≤8lg i = lg8！≈15.3，而该图右侧的树具有 φ=4lg1+lg3+lg5+lg7+lg8≈9.7，表明通过降低电位来大大抵消了展开0的成本。 每个操作（搜索，插入或删除）中的所有工作都在splayFind中进行，因此分析它就足够了。我声明在根为t的树中查找和展开节点x的摊销代价 ≤3(r(t)-r(x))+1。因为t是根，我们知道r(t)≥r(x)≥0。此外，由于s(t)=N，N为树中节点的数量，证明展开的摊销代价必须为O(lgN)，如期望的那样。 我们用C(t,x)表示在以t为根的树中查找并展开节点x的分摊代价。即： C(t, x) = max(1, 执行的旋转数) + 树的最终电位 − 树的初始电位. 我们按照图9.15中程序的结构递归地进行，以表明 C(t, x) ≤ 3(r(t) − r(x)) + 1 = 3 lg(s(t)/s(x)) + 1. (9.1) 我们很方便使用符号s'(z)表示“在展开步骤结束时s(z)的值”，且r'(z)表示“r(z)在结束处的值"。 1. 当t是空树或v在它的根时，没有旋转，电位没有变化，我们将实际成本设为1。在这种情况下，断言9.1显然是正确的。 2. 当x=y是t的孩子时（“zig”情况，如图9.12顶部所示），我们执行一次旋转，总实际代价为1.为了计算电位的变化，我们首先注意到我们必须考虑的节点只有t和x，因为所有其他节点的等级不会改变，因此当我们从旧节点中减去新的电位时会取消。因此，电位的变化是 r′(t) + r′(x) − r(t) − r(x) = r′(t) − r(x), since r′(x) = r(t) < r(t) − r(x), since r′(t) < r(t) < 3(r(t) − r(x)), since r(t) − r(x) > 0 因此，加上一个旋转的开销，摊销代价 <3(r(t) - r(x))+ 1。 3. 在zig-zig的例子中，开销包括首先将x展开为t的孙子（图9.12的第二行中的节点z），然后执行两次旋转。根据假设，第一个展开步骤的摊余代价是C(z，x)≤3(r(z)-r(x))+ 1 (r(z)是在展开到z的前一个位置之后的x的等级，因为展开不会改变树的根的等级。我们会稍微滥用符号并将此展开后的节点x称为z，这样我们仍然可以使用r(x)作为x的原始等级)。旋转的代价是2，并且由这两个旋转引起的电位的变化仅取决于它在t，y和z的等级中引起的变化。 总结这些，这个例子的摊销成本是 C(t, x) = 2 + r′(t) + r′(y) + r′(z) − r(t) − r(y) − r(z) + C(z, x) = 2 + r′(t) + r′(y) − r(y) − r(z) + C(z, x), since r′(z) = r(t) ≤ 2 + r′(t) + r′(y) − r(y) − r(z) + 3(r(z) − r(x)) + 1 通过归纳假设 = 3(r(t) − r(x)) + 1 + 2 + r′(t) + r′(y) − r(y) + 2r(z) − 3r(t) 所以我们想要的结果如下 2 + r′(t) + r′(y) − r(y) + 2r(z) − 3r(t) ≤ 0. (9.2) 9.2展示如下： 2 + r′(t) + r′(y) − r(y) + 2r(z) − 3r(t) ≤ 2 + r′(t) + r(z) − 2r(t) since r(y) > r(z) and r(t) > r′(y). = 2 + lg(s′(t)/s(t)) + lg(s(z)/s(t)) 通过r的定义和lg的属性。 现在，如果你在图9.12的zig-zig情况下检查树，你可以看到s'(t)+ s(z)+ 1 = s(t)，所以s'(t)/s(t)+s(z)/s(t)<1。因为lg是一个凹的，增加的函数，这反过来告诉我们(如§1.6中所讨论的), 2 + lg(s′(t)/s(t)) + lg(s(z)/s(t)) ≤ 2 + 2 lg(1/2) = 0. 4. 最后，在zig-zig的例子中，如果我们能够证明上面的不等式9.2，我们再次得到想要的结果。 这次，我们有s'(y)+s'(t)+1 = s(t)，所以我们可以继续 2 + r′(t) + r′(y) − r(y) + 2r(z) − 3r(t) ≤ 2 + r′(t) + r′(y) − 2r(t) since r(y) > r(z) and r(t) > r(z). = 2 + lg(s′(t)/s(t)) + lg(s′(y)/s(t)) 结果遵循与zig-zig例子相同的推理。 从而结束了证明。 插入和搜索的操作为展开时间增加了一个常数时间，删除时增加了常量和常数因子2(因为它涉及两个展开操作)。因此，对展开树的所有操作都具有O(lgN)的摊销时间(对于任何给定的操作序列，使用N为最大值)。 这种界限实际上是悲观的。正如我们所见，遍历有序树要花费树大小的线性时间。由于展开树只是一个BST，我们可以得到相同的界限。如果我们在遍历它们时将每个节点展开到根（这对于伸展树来说似乎是自然的），我们的分摊界限是O(NlgN)而不是O(N)。不仅如此，在遍历之后，我们的树将被转换为“串状”链表。然而，奇怪的是，可以证明，当遍历每个节点时，顺序遍历BST的成本实际上是O(N)。 然而，作者认为他已经将这个问题打败了，并且会为您提供详细信息。 ## 9.5 跳表 B树是搜索树的一个例子，其中节点具有可变数量的子节点，每个子节点代表一些有序的键集。它通过将每个节点上的键细分为不相交的键范围来加速搜索，并且设法使这些序列具有可比较的长度，从而平衡树。在这里，我们看看另一个结构做了很多相同的事情，除了它根据需要使用旋转来近似平衡树，它只是以高概率而不是确定性实现这种平衡。考虑图9.1中的同一组整数键，排列在搜索树中，其中每个节点都有一个键和任意数量的子节点，并且任何节点的子节点都具有至少与其父节点一样大的键。图9.18显示了一种可能的安排。 键出现的最大高度根据规则独立地选择，该规则给出出现在高度k(0为底部)的键的(1 - p)p^k的概率。也就是说，0 < p < 1是任意常数，其表示高度大于等于e的所有高度的大于等于e的节点的大致比例。我们在左边添加了一个最小的(-∞)键高度作为整棵树的根。图9.18显示了使用p = 0.5创建的示例。为了查找一个关键字，我们可以从任何级别开始从左到右扫描此树并向下工作。从底部开始(0层)只是给我们一个简单的线性搜索。在更高层级，我们搜索树木森林，根据其根节点的值选择更密切地检查哪个森林。例如，要查看127是否在其中，我们可以看： * 0级的前15个条目（不包括-∞）[15个条目]; 或者 * 前7个1级条目，然后是120个[9个条目]下面的2个0级项目; 或者 * 前3个2级条目，然后是1级条目140，然后是120个[6个条目]下的2个0级项目; 或者 * 等级3条目90，然后是等级2条目120，然后是等级1条目140，然后是低于120 [5个条目]的2个等级0项目。 我们可以将这个树表示为一种有序的线性节点列表（见图9.19），其中节点具有随机数的下一个链接，并且每个节点中的第i个下一个链接（从0开始编号）连接到 具有至少i + 1个链接的下一个节点。这个类似列表的表示，有一些链接“跳过”任意数量的列表元素，这个数据结构被称为：跳跃链表，简称跳表。 搜索非常简单。如果我们将这些节点之一的值表示为**L.value**(这里，我们将使用整数键)，并将高度为k的下一个指针表示为**L.next [k]**，则： ```java /** True iff X is in the skip list beginning at node L at * a height <= K, where K>=0. */ static boolean contains (SkipListNode L, int k, int x) { if (x == L.next[k].value) return true; else if (x > L.next[k].value) return contains (L.next[k], k, x); else if (k > 0) return contains (L, k-1, x); else return false; } ``` 我们可以在k≥0的任何级别开始直到树的高度。 事实证明，开始包含N个节点的列表的合理位置是$\log(1/p)*N$，如下所述。 要在列表中插入或删除，我们可以找到上述过程要添加或删除的节点的位置，跟踪我们遍历的节点。 添加或删除项目时，这些是可能需要更新其指针的节点。当我们插入节点时，我们随机选择一个高度，使得高度为k + 1的节点数大致为pk，其中p是一些概率（典型值可能是0.5或0.25）。也就是说，如果我们正在操作一个n层的搜索树，我们让p = 1 / n。 合适的过程可能如下所示： ```java /** A random integer, h, in the range 0 .. MAX such that * Pr(h ≥ k) = Pk, 0 ≤ k ≤ MAX. */ static int randomHeight (double p, int max, Random r) { int h; h = 0; while (h < max && r.nextDouble () < p) h += 1; return h; } ``` 一般来说，容纳任意大的高度是没有意义的，所以我们施加一些最大值，通常是人们期望需要的最大关键字个数的对数（基数1/p）。直观地，任何其高度至少为k的M个插入节点的序列将围绕每个1/p个节点随机地断开一个高度严格大于k的节点。同样，对于高度至少为k+1的节点，依此类推。 因此，如果我们的列表包含N个数据项，并且我们开始查看$\log(1/p)*N$层，我们期望看大多数(1/p)$\log(1/p)*N$个关键字(也就是说，每个$\log(1/p)*N$级别的1/p个关键字)。换句话说，θ(lgN)平均来说，这就是我们想要的。不可否认，这种分析有点过时，但真正的差距并没有很大。由于插入和删除包括查找节点，加上与节点高度成比例的一些插入或删除时间，因此我们实际上在搜索，插入和删除时具有θ(lgN)预期界限。 ## 练习 **9.1** 根据注释完善代码 ```java /** Return a modified version of T containing the same nodes * with the same inorder traversal, but with the node containing * label X at the root. Does not create any new Tree nodes. */ static Tree rotateUp (Tree T, Object X) { // FILL IN } ``` **9.2** 包含N个节点的5-B树的最大高度是多少？ 最小高度是多少？ 什么序列的关键字获得最大高度（即，给出这些序列的一般特征）。 什么序列的关键字获得最小高度？ **9.3** 图9.15中给出的splayFind算法几乎不是人们可以想象的这个过程的最有效版本。 原始论文具有相同函数的迭代版本，它使用常量额外空间而不是我们的splayFind版本的线性递归。 它跟踪两棵树：L，包含小于v的节点，R，包含大于v的节点。当它从根向下迭代地向下进行时，它将当前节点的子树添加到L和R，直到它 到达它正在寻找的节点x。 此时，它通过将x的左右子树分别附加到L和R，然后将L和R作为新子项来完成。 在此过程中，子树附加到L以便增加标签，并按照标签减少的顺序附加到R. 重写splayFind以使用此策略。 **9.4** 为跳表编写包含函数的非递归版本（第9.5节）。 **9.5** 定义使用跳表表示的SortedSet接口的实现。 ![figure_9_10](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_10.jpg) 图9.8中的trie的打包版本。 该图中的每个trie节点表示为由字符索引的子节点数组，作为子节点索引的字符存储在上面的行中（对应于数组**edgeLabels**）。 指向子项本身的指针位于下一行（对应于**allKids**数组）。 顶部的空框表示未使用的位置（**NOEDGE**值）。 为了压缩图表，我改变了字符集编码，使□为0，'a'为1，'b'为2，等等。下排的交叉框表示空节点。右侧（未示出）还必须有另外24个空条目记录存储的最右边的trie节点的c-z条目。 搜索算法使用edgeLabel来确定条目实际上何时属于它当前正在检查的节点。 例如，根节点应包含“a”，“b”和“f”的条目。事实上，如果您从上面的“根”框中算出1,2和6，您将找到边标签为'a'，'b'和'f'的条目。另一方面，如果从根盒中计算超过3，查找不存在的'c'边缘，则会找到边缘标签'e'，告诉您根节点没有'c'边缘。 ![figure_9_11](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_11.jpg) 二叉搜索树中的旋转。 三角形表示子树，圆圈表示单个节点。 二进制搜索树关系由两个操作维护，但各个节点的级别受到影响。 ![figure_9_12](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_12.jpg) 基本的展开步骤。 当y在t的另一侧时，存在镜像图像。 最后一行说明了完整的splaying操作（在节点3上）。 从底部开始，我们执行“zig”步骤，然后执行“zig-zig”，最后在节点3上执行“Zig-zag”，最后是右侧的树。 ![figure_9_13](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_13.jpg) 在完全不平衡的树中伸展节点0。 结果树大约变成原高度的一半，这样大大加快了后续搜索速度。 ![figure_9_14](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_14.jpg) 用于我们的伸展树的二叉搜索树结构。 这只是一个普通的二叉搜索树，为旋转或更换孩子节点提供统一的操作。 ![figure_9_15](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_15.jpg) 用于查找和展开节点的**splayFind** 方法。 用于插入，删除和搜索。 ![figure_9_16](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_16.jpg) 伸展树上的标准集合操作。 该接口采用Java集合类的样式。 图9.17说明了这些方法。 ![figure_9_17](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_17.jpg) 展开树上的基本BST操作。(a)是原始树。(b)是对值21或24中的任何一个执行**splayFind**的结果。(c)是将值21加到(a)中的结果; 第一步是创建展开的树(b)。(d)是从原树(a)中删除24的结果; 再次，第一步是创建(b)，之后我们将24的左子项显示为值24，这保证大于该子项中的任何值。 ![figure_9_18](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_18.jpg) 跳过列表的抽象视图，显示其与（非二进制）搜索树的关系。 除-∞之外的每个密钥都复制到随机高度。 我们可以从任何级别开始搜索这个结构。 在最好的情况下，要搜索（失败）目标值127，我们只需要查看着色节点中的键。 较暗的阴影节点表示大于127的键绑定搜索。 ![figure_9_19](https://github.com/Abel-Huang/cs61b-textbook-zh/blob/master/zh/img/figure_9_19.jpg) 图9.18中的跳过列表，显示了可能的表示。 数据结构是一个有序列表，其节点包含指向后面节点的随机数量的指针（允许在搜索期间跳过列表中的中间项;因此名称）。 如果一个节点至少有k个指针，那么它包含一个指向下一个节点的指针，该节点至少有k个指针。 右边的∞节点允许我们避免测试null。 同样，在搜索127期间查看的节点是阴影; 较暗的阴影表示限制搜索的节点。