普林斯顿算法讲义（二）（3）

普林斯顿算法讲义（二）（2）https://developer.aliyun.com/article/1484173

在有序数组中进行二分查找

. 程序 BinarySearchST.java 实现了有序符号表 API。底层数据结构是两个并行数组，键按顺序保存。实现的核心是rank()方法，它返回小于给定键的键数。对于get()，rank 告诉我们如果键在表中，则键应该被找到的确切位置（如果不在表中，则不在表中）。对于put()，rank 告诉我们当键在表中时精确更新值的位置，当键不在表中时精确放置键的位置。我们将所有较大的键向后移动一个位置以腾出空间（从后向前工作），并将给定的键和值插入到各自数组中的适当位置。

• 二分查找. 我们将键保持在有序数组中的原因是为了可以使用数组索引来显著减少每次搜索所需的比��次数，使用一种著名的经典算法称为二分查找。基本思想很简单：我们维护索引到排序键数组的指示符，限定可能包含搜索键的子数组。要搜索，我们将搜索键与子数组中间的键进行比较。如果搜索键小于中间键，则在子数组的左半部分搜索；如果搜索键大于中间键，则在子数组的右半部分搜索；否则中间键等于搜索键。
  
• 其他操作. 由于键保持在有序数组中，大多数基于顺序的操作都是紧凑且简单的。
  

命题 B.

在具有 N 个键的有序数组中进行二分查找，在最坏情况下搜索（成功或失败）不会超过 lg N + 1 次比较。

命题 C.

将新键插入有序数组中在最坏情况下使用 ~ 2N 个数组访问，因此将 N 个键插入到最初为空的表中在最坏情况下使用 ~ N² 个数组访问。

练习

1. 编写一个客户端程序 GPA.java，创建一个将字母等级映射到数字分数的符号表，如下表所示，然后从标准输入读取字母等级列表，并计算并打印 GPA（对应等级的数字分数的平均值）。

A+    A     A-    B+    B     B-    C+    C     C-    D     F
4.33  4.00  3.67  3.33  3.00  2.67  2.33  2.00  1.67  1.00  0.00

1. 开发一个符号表实现 ArrayST.java，它使用（无序）数组作为底层数据结构来实现我们的基本符号表 API。
   
2. 为 SequentialSearchST.java 实现size()、delete()和keys()。
   
3. 为 BinarySearchST.java 实现delete()方法。
   
4. 为 BinarySearchST.java 实现floor()方法。
   

创意问题

1. **测试客户端。**编写一个测试客户端 TestBinarySearchST.java，用于测试min()、max()、floor()、ceiling()、select()、rank()、deleteMin()、deleteMax()和keys()的实现。
   
2. **认证。**在 BinarySearchST.java 中添加assert语句，以检查每次插入和删除后的算法不变性和数据结构完整性。例如，每个索引i应始终等于rank(select(i))，并且数组应始终保持有序。
   

网页练习

1. **电话号码数据类型。**编写一个实现美国电话号码的数据类型 PhoneNumber.java，包括一个equals()方法。
   
2. **学生数据类型。**编写一个实现具有姓名和班级的学生的数据类型 Student.java，包括一个equals()方法。
   

3.2 二叉搜索树

原文：algs4.cs.princeton.edu/32bst

译者：飞龙

协议：CC BY-NC-SA 4.0

我们研究了一种符号表实现，它将链表中的插入灵活性与有序数组中的搜索效率结合起来。具体来说，每个节点使用两个链接会导致基于二叉搜索树数据结构的高效符号表实现，这被认为是计算机科学中最基本的算法之一。

定义. 二叉搜索树（BST）是一种二叉树，其中每个节点都有一个Comparable键（和一个相关联的值），并满足一个限制条件，即任何节点中的键都大于该节点左子树中所有节点的键，且小于该节点右子树中所有节点的键。

基本实现。

程序 BST.java 使用二叉搜索树实现了有序符号表 API。我们定义一个内部私有类来定义 BST 中的节点。每个节点包含一个��、一个值、一个左��接、一个右链接和一个节点计数。左链接指向具有较小键的项目的 BST，右链接指向具有较大键的项目的 BST。实例变量N给出了根节点下子树中的节点计数。这个字段有助于实现各种有序符号表操作，你将看到。

• 搜索. 一个递归算法用于在 BST 中搜索键，直接遵循递归结构：如果树为空，则搜索未命中；如果搜索键等于根节点的键，则搜索命中。否则，我们在适当的子树中搜索（递归）。递归的get()方法直接实现了这个算法。它以一个节点（子树的根）作为第一个参数，以一个键作为第二个参数，从树的根和搜索键开始。
  
• 插入. 插入比搜索实现稍微困难一些。实际上，对于树中不存在的键的搜索会在一个空链接处结束，我们需要做的就是用包含键的新节点替换该链接。递归的put()方法使用了与递归搜索相似的逻辑来完成这个任务：如果树为空，我们返回一个包含键和值的新节点；如果搜索键小于根节点的键，我们将左链接设置为将键插入左子树的结果；否则，我们将右链接设置为将键插入右子树的结果。
  

分析。

算法在二叉搜索树上的运行时间取决于树的形状，而树的形状又取决于键的插入顺序。

对于许多应用程序来说，使用以下简单模型是合理的：我们假设键是（均匀）随机的，或者等效地说，它们是以随机顺序插入的。

命题。

在由 N 个随机键构建的 BST 中，搜索命中平均需要约 2 ln N（约 1.39 lg N）次比较。

命题。

在由 N 个随机键构建的 BST 中，插入和搜索未命中平均需要约 2 ln N（约 1.39 lg N）次比较。

下面的可视化展示了以随机顺序向二叉搜索树中插入 255 个键的结果。它显示了键的数量（N）、从根到叶子节点的路径上节点的最大数量（max）、从根到叶子节点的路径上节点的平均数量（avg）、在完全平衡的二叉搜索树中从根到叶子节点的路径上节点的平均数量（opt）。

您的浏览器不支持视频标签。

基于顺序的方法和删除。

二叉搜索树被广泛使用的一个重要原因是它们可以让我们保持键有序。因此，它们可以作为实现有序符号表 API 中众多方法的基础。

• 最小值和最大值。 如果根节点的左链接为空，则二叉搜索树中的最小键是根节点的键；如果左链接不为空，则二叉搜索树中的最小键是左链接引用的节点为根的子树中的最小键。查找最大键类似，向右移动而不是向左移动。
  
• 下取整和上取整。 如果给定的键 key 小于二叉搜索树根节点的键，则 key 的下取整（小于或等于 key 的二叉搜索树中的最大键）必须在左子树中。如果 key 大于根节点的键，则 key 的下取整可能在右子树中，但只有在右子树中存在小于或等于 key 的键时才可能；如果没有（或者 key 等于根节点的键），则根节点的键就是 key 的下取整。查找上取整类似，交换右子树和左子树。
  
• 选择。 假设我们寻找排名为 k 的键（即 BST 中恰好有 k 个其他键比它小）。如果左子树中的键数 t 大于 k，我们在左子树中查找排名为 k 的键；如果 t 等于 k，我们返回根节点的键；如果 t 小于 k，我们在右子树中查找排名为 k - t - 1 的键。

• 排名。 如果给定的键等于根节点的键，则返回左子树中键数 t；如果给定的键小于根节点的键，则返回左子树中键的排名；如果给定的键大于根节点的键，则返回 t 加一（计算根节点的键）再加上右子树中键的排名。
  
• 删除最小值和最大值。 对于删除最小值，我们向左移动直到找到一个具有空左链接的节点，然后用其右链接替换指向该节点的链接。对于删除最大值，对称方法适用。
  
• 删除。我们可以类似地删除任何只有一个子节点（或没有子节点）的节点，但是如何删除具有两个子节点的节点呢？我们剩下两个链接，但是父节点只有一个位置可以放置它们中的一个。1962 年 T. Hibbard 首次提出的解决这个困境的方法是通过用其后继替换节点 x 来删除节点 x。因为x有一个右子节点，其后继是其右子树中具有最小键的节点。替换保持了树中的顺序，因为在x.key和后继的键之间没有其他键。我们通过四个（！）简单的步骤完成了用其后继替换 x 的任务：

• 在 t 中保存要删除的节点的链接
  
• 将 x 设置为其后继 min(t.right)。
  
• 将 x 的右链接（应指向包含所有大于 x.key 的键的二叉搜索树）设置为 deleteMin(t.right)，即删除后包含所有大于 x.key 的键的二叉搜索树的链接。
  
• 将 x 的左链接（原本为空）设置为 t.left（所有小于被删除键和其后继的键）。
  

• 尽管这种方法能够完成任务，但它有一个缺点，在某些实际情况下可能会导致性能问题。问题在于使用后继者是任意的，而不是对称的。为什么不使用前任者呢？

每个二叉查找树包含 150 个节点。然后我们通过 Hibbard 删除方法重复删除和随机插入键。二叉查找树向左倾斜。

您的浏览器不支持视频标签。

• 范围搜索。 为了实现返回给定范围内键的keys()方法，我们从一个基本的递归二叉查找树遍历方法开始，称为中序遍历。为了说明这种方法，我们考虑按顺序打印二叉查找树中所有键的任务。为此，首先打印左子树中的所有键（根据二叉查找树的定义，这些键小于根键），然后打印根键，然后打印右子树中的所有键（根据二叉查找树的定义，这些键大于根键）。
  

private void print(Node x) {
   if (x == null) return;
   print(x.left);
   StdOut.println(x.key);
   print(x.right);
}

• 要实现带有两个参数的keys()方法，我们修改这段代码，将在范围内的每个键添加到一个Queue中，并跳过不能包含范围内键的子树的递归调用。

建议。

搜索、插入、查找最小值、查找最大值、floor、ceiling、rank、select、删除最小值、删除最大值、删除和范围计数操作在最坏情况下都需要时间与树的高度成比例。

练习

1. 给出五种键A X C S E R H的排序方式，当插入到一个初始为空的二叉查找树时，产生最佳情况的树。
   解决方案。 任何首先插入 H；在 A 和 E 之前插入 C；在 R 和 X 之前插入 S 的序列。
   
2. 在 BST.java 中添加一个计算树高度的方法height()。开发两种实现：一个递归方法（需要与树高成比例的线性时间和空间），以及像size()那样为树中的每个节点添加一个字段的方法（需要线性空间和每次查询的常数时间）。
   
3. 为了测试文本中给出的min()、max()、floor()、ceiling()、select()、rank()、deleteMin()、deleteMax()和keys()的实现，编写一个测试客户端 TestBST.java。
   
4. 给出二叉查找树的get()、put()和keys()的非递归实现。
   *解决方案：*NonrecursiveBST.java
   

创意问题

1. 完美平衡。 编写一个程序 PerfectBalance.java，将一组键插入到一个初始为空的二叉查找树中，使得生成的树等同于二叉搜索，即对于二叉查找树中任何键的搜索所做的比较序列与二叉搜索对相同键集的比较序列相同。
   提示：将中位数放在根节点，并递归构建左子树和右子树。
   
2. 认证。 在 BST.java 中编写一个名为isBST()的方法，该方法以一个Node作为参数，并在参数节点是二叉查找树根节点时返回true，否则返回false。
   
3. 子树计数检查。 在 BST.java 中编写一个递归方法isSizeConsistent()，该方法以一个Node作为参数，并在该节点根的数据结构中N字段一致时返回true，否则返回false。
   
4. 选择/排名检查。 在 BST.java 中编写一个名为isRankConsistent()的方法，检查对于所有i从0到size() - 1，是否i等于rank(select(i))，以及对于二叉查找树中的所有键，是否key等于select(rank(key))。
   

Web 练习

1. 伟大的树-列表递归问题。 二叉搜索树和循环双向链表在概念上都是由相同类型的节点构建的 - 一个数据字段和两个指向其他节点的引用。 给定一个二叉搜索树，重新排列引用，使其成为一个循环双向链表（按排序顺序）。 尼克·帕兰特将其描述为有史以来设计的最整洁的递归指针问题之一。 提示：从左子树创建一个循环链接列表 A，从右子树创建一个循环链接列表 B，并使根节点成为一个节点的循环链接列表。 然后合并这三个列表。
   
2. BST 重建。 给定 BST 的前序遍历（不包括空节点），重建树。
   
3. 真或假。 给定 BST，设 x 是叶节点，y 是其父节点。 那么 y 的键要么是大于 x 的键中最小的键，要么是小于 x 的键中最大的键。 答案：真。
   
4. 真或假。 设 x 是 BST 节点。 可以通过沿着树向根遍历直到遇到具有非空右子树的节点（可能是 x 本身）；然后在右子树中找到最小键来找到 x 的下一个最大键（x 的后继）。
   
5. 具有恒定额外内存的树遍历。 描述如何使用恒定额外内存（例如，没有函数调用堆栈）执行中序树遍历。
   提示：在树下行的过程中，使子节点指向父节点（并在树上行的过程中反转它）。
   
6. 反转 BST。 给定一个标准 BST（其中每个键都大于其左子树中的键，小于其右子树中的键），设计一个线性时间算法将其转换为反转 BST（其中每个键都小于其左子树中的键，大于其右子树中的键）。 结果树形状应对称于原始形状。
   
7. BST 的层序遍历重建。 给定一系列键，设计一个线性时间算法来确定它是否是某个 BST 的层序遍历（并构造 BST 本身）。
   
8. 在 BST 中查找两个交换的键。 给定一个 BST，其中两个节点中的两个键已被交换，找到这两个键。
   解决方案。 考虑 BST 的中序遍历 a[]。 有两种情况需要考虑。 假设只有一个索引 p，使得 a[p] > a[p+1]。 然后交换键 a[p]和 a[p+1]。 否则，存在两个索引 p 和 q，使得 a[p] > a[p+1]和 a[q] > a[q+1]。 假设 p < q。 然后，交换键 a[p]和 a[q+1]。
   

3.3 平衡搜索树

原文：algs4.cs.princeton.edu/33balanced

译者：飞龙

协议：CC BY-NC-SA 4.0

本节正在大力施工中。

我们在本节介绍了一种类型的二叉搜索树，其中成本保证为对数。我们的树几乎完美平衡，高度保证不会大于 2 lg N。

2-3 搜索树。

获得我们需要保证搜索树平衡的灵活性的主要步骤是允许我们树中的节点保存多个键。

定义。

一个2-3 搜索树是一棵树，要么为空，要么：

• 一个2 节点，带有一个键（和相关值）和两个链接，一个指向具有较小键的 2-3 搜索树的左链接，一个指向具有较大键的 2-3 搜索树的右链接
  
• 一个3 节点，带有两个键（和相关值）和三个链接，一个指向具有较小键的 2-3 搜索树的左链接，一个指向具有节点键之间的键的 2-3 搜索树的中间链接，一个指向具有较大键的 2-3 搜索树的右链接。
  

一个完美平衡的 2-3 搜索树（或简称 2-3 树）是指其空链接与根之间的距离都相同。

• 搜索。 要确定 2-3 树中是否存在一个键，我们将其与根处的键进行比较：如果它等于其中任何一个键，则有一个搜索命中；否则，我们跟随从根到对应于可能包含搜索键的键值区间的子树的链接，然后在该子树中递归搜索。
  
• 插入到 2 节点中。 要在 2-3 树中插入新节点，我们可能会进行一次不成功的搜索，然后挂接到底部的节点，就像我们在二叉搜索树中所做的那样，但新树不会保持完美平衡。如果搜索终止的节点是一个 2 节点，要保持完美平衡很容易：我们只需用包含其键和要插入的新键的 3 节点替换该节点。
  
• 插入到由单个 3 节点组成的树中。 假设我们想要插入到一个仅由单个 3 节点组成的微小 2-3 树中。这样的树有两个键，但在其一个节点中没有新键的空间。为了能够执行插入操作，我们暂时将新键放入一个4 节点中，这是我们节点类型的自然扩展，具有三个键和四个链接。创建 4 节点很方便，因为很容易将其转换为由三个 2 节点组成的 2-3 树，其中一个带有中间键（在根处），一个带有三个键中最小的键（由根的左链接指向），一个带有三个键中最大的键（由根的右链接指向）。
  
• 插入到父节点为 2 节点的 3 节点中。 假设搜索在底部结束于其父节点为 2 节点的 3 节点。在这种情况下，我们仍然可以为新键腾出空间，同时保持树的完美平衡，方法是制作一个临时的 4 节点，然后按照刚才描述的方式拆分 4 节点，但是，而不是创建一个新节点来保存中间键，将中间键移动到节点的父节点。
  
• 插入到父节点为 3 节点的 3 节点中。 现在假设搜索结束于父节点为 3 节点的节点。同样，我们制作一个临时的 4 节点，然后将其拆分并将其中间键插入父节点。父节点是 3 节点，所以我们用刚刚拆分的临时新 4 节点替换它，其中包含来自 4 节点拆分的中间键。然后，我们对该节点执行完全相同的转换。也就是说，我们拆分新的 4 节点并将其中间键插入其父节点。扩展到一般情况很明显：我们沿着树向上移动，拆分 4 节点并将它们的中间键插入它们的父节点，直到达到一个 2 节点，我们用一个不需要进一步拆分的 3 节点替换它，或者直到达到根节点处的 3 节点。
  
• 拆分根节点。 如果从插入点到根节点沿着整个路径都是 3 节点，我们最终会在根节点处得到一个临时的 4 节点。在这种情况下，我们将临时的 4 节点拆分为三个 2 节点。
  
• 局部转换。 2-3 树插入算法的基础是所有这些转换都是纯粹局部的：除了指定的节点和链接之外，不需要检查或修改 2-3 树的任何部分。每次转换更改的链接数量受到小常数的限制。这些转换中的每一个都将一个键从 4 节点传递到树中的父节点，然后相应地重构链接，而不触及树的任何其他部分。
  
• 全局属性。 这些局部转换保持了树是有序和平衡的全局属性：从根到任何空链接的路径上的链接数量是相同的。
  

命题。

在具有 N 个键的 2-3 树中，搜索和插入操作保证最多访问 lg N 个节点。

然而，我们只完成了实现的一部分。虽然可以编写代码来对表示 2 和 3 节点的不同数据类型执行转换，但我们描述的大部分任务在这种直接表示中实现起来很不方便。

红黑 BST。

刚刚描述的 2-3 树插入算法并不难理解。我们考虑一种简单的表示法，称为红黑 BST，可以自然地实现。

• 编码 3 节点。 红黑 BST 背后的基本思想是通过从标准 BST（由 2 节点组成）开始，并添加额外信息来编码 3 节点，从而对 2-3 树进行编码。我们认为链接有两种不同类型：红色链接，将两个 2 节点绑在一起表示 3 节点，以及黑色链接，将 2-3 树绑在一起。具体来说，我们将 3 节点表示为由单个向左倾斜的红色链接连接的两个 2 节点。我们将以这种方式表示 2-3 树的 BST 称为红黑 BST。
  使用这种表示的一个优点是，它允许我们在不修改的情况下使用我们的get()代码进行标准 BST 搜索。
  
  
• 1-1 对应关系。 给定任何 2-3 树，我们可以立即推导出相应的红黑 BST，只需按照指定的方式转换每个节点即可。反之，如果我们在红黑 BST 中水平绘制红色链接，所有空链接距离根节点的距离相同，然后将由红色链接连接的节点合并在一起，结果就是一个 2-3 树。
  红黑 BST 和 2-3 树](…/Images/2a82ce5ba078c8217adc45ad5e5d7a47.png)
  
• 颜色表示。 由于每个节点只被一个链接（从其父节点）指向，我们通过在节点中添加一个boolean实例变量颜色来编码链接的颜色，如果来自父节点的链接是红色，则为true，如果是黑色，则为false。按照惯例，空链接为黑色。
  
• 旋转。 我们将考虑的实现可能允许右倾斜的红链接或操作中连续两个红链接，但它总是在完成之前纠正这些条件，通过巧妙使用称为旋转的操作来切换红链接的方向。首先，假设我们有一个需要旋转以向左倾斜的右倾斜红链接。这个操作称为左旋转。实现将左倾斜的红链接转换为右倾斜的右旋转操作等同于相同的代码，左右互换。
  
• 翻转颜色。 我们将考虑的实现也可能允许黑色父节点有两个红色子节点。颜色翻转操作将两个红色子节点的颜色翻转为黑色，并将黑色父节点的颜色翻转为红色。

• 插入到单个 2 节点中。
  
• 在底部插入到 2 节点。
  
• 在具有两个键的树中（在 3 节点中）插入。
  
• 保持根节点为黑色。
  
• 在底部插入到 3 节点。
  
• 将红链接向上传递树。
  

实现。

程序 RedBlackBST.java 实现了一个左倾斜的红黑 BST。程序 RedBlackLiteBST.java 是一个更简单的版本，只实现了 put、get 和 contains。

删除。

命题。

具有 N 个节点的红黑 BST 的高度不超过 2 lg N。

命题。

在红黑 BST 中，以下操作在最坏情况下需要对数时间：搜索、插入、查找最小值、查找最大值、floor、ceiling、rank、select、删除最小值、删除最大值、删除和范围计数。

属性。

具有 N 个节点的红黑 BST 中从根到节点的平均路径长度约为~1.00 lg N。

可视化。

以下可视化展示了 255 个键按随机顺序插入到红黑 BST 中。

练习

1. 哪些是合法的平衡红黑 BST？
   解决方案。 (iii) 和 (iv)。 (i) 不平衡，(ii) 不是对称顺序或平衡的。
   
2. 真或假：如果您将键按递增顺序插入到红黑 BST 中，则树的高度是单调递增的。
   解决方案。 真的，请看下一个问题。
   
3. 描述当按升序插入键构建红黑 BST 时，插入字母A到K时产生的红黑 BST。然后，描述当按升序插入键构建红黑 BST 时通常会发生什么。
   解决方案。 以下可视化展示了 255 个键按升序插入到红黑 BST 中。
   
4. 回答前两个问题，当键按降序插入时的情况。
   解决方案。 错误。以下可视化展示了 255 个键按降序插入到红黑 BST 中。
   
5. 创建一个测试客���端 TestRedBlackBST.java。
   

创造性问题

1. 认证. 在 RedBlackBST.java 中添加一个方法is23()，以检查没有节点连接到两个红链接，并且没有右倾斜的红链接。 添加一个方法isBalanced()，以检查从根到空链接的所有路径是否具有相同数量的黑链接。 将这些方法与isBST()结合起来创建一个方法isRedBlackBST()，用于检查树是否是 BST，并且满足这两个条件。
   
2. 旋转的基本定理. 证明任何 BST 都可以通过一系列左旋和右旋转变换为具有相同键集的任何其他 BST。
   解决方案概述: 将第一个 BST 中最小的键旋转到根节点沿着向左的脊柱；然后对结果的右子树进行递归，直到得到高度为 N 的树（每个左链接都为 null）。 对第二个 BST 执行相同的操作。 备注：目前尚不清楚是否存在一种多项式时间算法，可以确定将一个 BST 转换为另一个 BST 所需的最小旋转次数（即使对于至少有 11 个节点的 BST，旋转距离最多为 2N - 6）。
   
3. 删除最小值. 通过保持与文本中给出的向树的左脊柱下移的转换的对应关系，同时保持当前节点不是 2 节点的不变性，为 RedBlackBST.java 实现deleteMin()操作。
   
4. 删除最大值. 为 RedBlackBST.java 实现deleteMax()操作。 请注意，涉及的转换与前一个练习中的转换略有不同，因为红链接是向左倾斜的。
   
5. 删除. 为 RedBlackBST.java 实现delete()操作，将前两个练习的方法与 BST 的delete()操作结合起来。
   

网络练习

1. 给定一个排序的键序列，描述如何在线性时间内构建包含这些键的红黑 BST。
   
2. 假设在红黑 BST 中进行搜索，在从根节点开始跟踪 20 个链接后终止，以下划线填写下面关于任何不成功搜索的最佳（整数）界限，您可以从这个事实中推断出来

• 从根节点至少要遵循 ______ 条链接
  
• 从根节点最多需要遵循 _______ 条链接
  

3. 使用每个节点 1 位，我们可以表示 2、3 和 4 节点。 我们需要多少位来表示 5、6、7 和 8 节点。
   
4. 子串反转. 给定长度为 N 的字符串，支持以下操作：select(i) = 获取第 i 个字符，并且 reverse(i, j) = 反转从 i 到 j 的子串。
   解决方案概述. 在平衡搜索树中维护字符串，其中每个节点记录子树计数和一个反转位（如果从根到节点的路径上存在奇数个反转位，则交换左右子节点的角色）。 要实现 select(i)，从根节点开始进行二分搜索，使用子树计数和反转位。 要实现 reverse(i, j)，在 select(i)和 select(j)处拆分 BST 以形成三个 BST，反转中间 BST 的位，并使用连接操作将它们重新组合在一起。 旋转时维护子树计数和反转位。
   
5. BST 的内存. BST、RedBlackBST 和 TreeMap 的内存使用情况是多少？
   解决方案. MemoryOfBSTs.java.
   
6. 随机化 BST. 程序 RandomizedBST.java 实现了一个随机化 BST，包括删除操作。 每次操作的预期 O(log N)性能。 期望仅取决于算法中的随机性； 它不依赖于输入分布。 必须在每个节点中存储子树计数字段； 每次插入生成 O(log N)个随机数。
   命题. 树具有与按随机顺序插入键时相同的分布。
   
7. 连接. 编写一个函数，该函数以两个随机化 BST 作为输入，并返回包含两个 BST 中元素并集的第三个随机化 BST。 假设没有重复项。
   
8. 伸展 BST。 程序 SplayBST.java 实现了一个伸展树。
   
9. 随机队列。 实现一个 RandomizedQueue.java，使得所有操作在最坏情况下都需要对数时间。
   
10. 具有许多更新的红黑色 BST。 当在红黑色 BST 中执行具有已经存在的键的put()时，我们的 RedBlackBST.java 会执行许多不必要的isRed()和size()调用。优化代码，以便在这种情况下跳过这些调用。
    

3.4 哈希表

原文：algs4.cs.princeton.edu/34hash

译者：飞龙

协议：CC BY-NC-SA 4.0

如果键是小整数，我们可以使用数组来实现符号表，通过将键解释为数组索引，以便我们可以将与键 i 关联的值存储在数组位置 i 中。在本节中，我们考虑哈希，这是一种处理更复杂类型键的简单方法的扩展。我们通过进行算术运算将键转换为数组索引来引用键值对。

使用哈希的搜索算法由两个独立部分组成。第一步是计算哈希函数，将搜索键转换为数组索引。理想情况下，不同的键将映射到不同的索引。这种理想通常超出我们的能力范围，因此我们必须面对两个或更多不同键可能哈希到相同数组索引的可能性。因此，哈希搜索的第二部分是处理这种情况的冲突解决过程。

哈希函数。

如果我们有一个可以容纳 M 个键值对的数组，则需要一个函数，可以将任何给定的键转换为该数组的索引：在范围[0, M-1]内的整数。我们寻求一个既易于计算又均匀分布键的哈希函数。

• 典型例子。 假设我们有一个应用程序，其中键是美国社会安全号码。例如，社会安全号码 123-45-6789 是一个分为三个字段的 9 位数。第一个字段标识发放号码的地理区域（例如，第一个字段为 035 的号码来自罗德岛，第一个字段为 214 的号码来自马里兰），其他两个字段标识个人。有十亿个不同的社会安全号码，但假设我们的应用程序只需要处理几百个键，因此我们可以使用大小为 M = 1000 的哈希表。实现哈希函数的一种可能方法是使用键中的三位数。使用右侧字段中的三位数可能比使用左侧字段中的三位数更可取（因为客户可能不均匀地分布在地理区域上），但更好的方法是使用所有九位数制成一个整数值，然后考虑下面描述的整数的哈希函数。
  
• 正整数。 用于哈希整数的最常用方法称为模块化哈希：我们选择数组大小 M 为素数，并且对于任何正整数键 k，计算 k 除以 M 的余数。这个函数非常容易计算（在 Java 中为 k % M），并且在 0 和 M-1 之间有效地分散键。
  
• 浮点数。 如果键是介于 0 和 1 之间的实数，我们可能只需乘以 M 并四舍五入到最接近的整数以获得 0 和 M-1 之间的索引。尽管这是直观的，但这种方法有缺陷，因为它给予键的最高有效位更多权重；最低有效位不起作用。解决这种情况的一种方法是使用键的二进制表示进行模块化哈希（这就是 Java 所做的）。
  
• 字符串。 模块化哈希也适用于长键，如字符串：我们只需将它们视为巨大的整数。例如，下面的代码计算了一个 String s 的模块化哈希函数，其中 R 是一个小素数（Java 使用 31）。

int hash = 0;
for (int i = 0; i < s.length(); i++)
    hash = (R * hash + s.charAt(i)) % M;

• 复合键。 如果键类型具有多个整数字段，我们通常可以像刚才描述的String值一样将它们混合在一起。例如，假设搜索键的类型为 USPhoneNumber.java，其中包含三个整数字段：区域（3 位区号）、交换（3 位交换）和分机（4 位分机）。在这种情况下，我们可以计算数字

int hash = (((area * R + exch) % M) * R + ext) % M; 

• Java 约定。 Java 帮助我们解决了每种数据类型都需要一个哈希函数的基本问题，要求每种数据类型必须实现一个名为hashCode()的方法（返回一个 32 位整数）。对象的hashCode()实现必须与equals一致。也就是说，如果a.equals(b)为真，则a.hashCode()必须与b.hashCode()具有相同的数值。如果hashCode()值相同，则对象可能相等也可能不相等，我们必须使用equals()来确定哪种情况成立。
  
• 将hashCode()转换为数组索引。 由于我们的目标是一个数组索引，而不是 32 位整数，因此我们在实现中将hashCode()与模块化哈希结合起来，以产生 0 到 M-1 之间的整数，如下所示：

private int hash(Key key) {
   return (key.hashCode() & 0x7fffffff) % M;
}

• 该代码掩盖了符号位（将 32 位整数转换为 31 位非负整数），然后通过除以 M 来计算余数，就像模块化哈希一样。
• 用户定义的hashCode()。 客户端代码期望hashCode()在可能的 32 位结果值中均匀分散键。也就是说，对于任何对象x，你可以编写x.hashCode()，并且原则上期望以相等的可能性获得 2³² 个可能的 32 位值中的任何一个。Java 为许多常见类型（包括String、Integer、Double、Date和URL）提供了渴望实现此功能的hashCode()实现，但对于您��己的类型，您必须自己尝试。程序 PhoneNumber.java 演示了一种方法：从实例变量中生成整数并使用模块化哈希。程序 Transaction.java 演示了一种更简单的方法：使用实例变量的hashCode()方法将每个转换为 32 位int值，然后进行算术运算。
  

在为给定数据类型实现良好的哈希函数时，我们有三个主要要求：

• 它应该是确定性的—相同的键必须产生相同的哈希值。
  
• 计算效率应该高。
  
• 它应该均匀分布键。
  

为了分析我们的哈希算法并对其性能提出假设，我们做出以下理想化假设。

假设 J（均匀哈希假设）。

我们使用的哈希函数在 0 和 M-1 之间的整数值之间均匀分布键。

使用分离链接进行哈希。

哈希函数将键转换为数组索引。哈希算法的第二个组成部分是冲突解决：处理两个或更多个要插入的键哈希到相同索引的情况的策略。冲突解决的一个直接方法是为 M 个数组索引中的每一个构建一个键-值对的链表，这些键的哈希值为该索引。基本思想是选择足够大的 M，使得列表足够短，以便通过两步过程进行有效搜索：哈希以找到可能包含键的列表，然后顺序搜索该列表以查找键。

程序 SeparateChainingHashST.java 实现了一个带有分离链接哈希表的符号表。它维护了一个 SequentialSearchST 对象的数组，并通过计算哈希函数来选择哪个SequentialSearchST可以包含键，并然后使用SequentialSearchST中的get()和put()来完成工作。程序 SeparateChainingLiteHashST.java 类似，但使用了一个显式的Node嵌套类。

命题 K。 在具有 M 个列表和 N 个键的分离链接哈希表中，假设 J 下，列表中键的数量在 N/M 的小常数因子范围内的概率极其接近 1。N/M 的小常数因子范围内的概率极其接近 1。 （假设一个理想的哈希函数。）

这个经典的数学结果很有说服力，但它完全依赖于假设 J。然而，在实践中，相同的行为发生。

性质 L. 在具有 M 个列表和 N 个键的分离链接哈希表中，搜索和插入的比较次数（相等测试）与 N/M 成正比。

使用线性探测进行哈希。

实现哈希的另一种方法是将 N 个键值对存储在大小为 M > N 的哈希表中，依赖表中的空条目来帮助解决冲突。这种方法称为开放寻址哈希方法。最简单的开放寻址方法称为线性探测：当发生冲突（当我们哈希到已经被不同于搜索键的键占据的表索引时），我们只需检查表中的下一个条目（通过增加索引）。有三种可能的结果：

• 键等于搜索键：搜索命中
  
• 空位置（索引位置处的空键）：搜索未命中
  
• 键不等于搜索键：尝试下一个条目
  

程序 LinearProbingHashST.java 是使用这种方法实现符号表 ADT 的实现。

与分离链接一样，开放寻址方法的性能取决于比率 α = N/M，但我们对其进行了不同的解释。对于分离链接，α 是每个列表的平均项目数，通常大于 1。对于开放寻址，α 是占用的表位置的百分比；它必须小于 1。我们将 α 称为哈希表的负载因子。

命题 M. 在大小为 M 的线性探测哈希表中，N = α M 个键，平均探测次数（在假设 J 下）对于搜索命中约为 ~ 1/2 (1 + 1 / (1 - α))，对于搜索未命中或插入约为 ~ 1/2 (1 + 1 / (1 - α)²)。

问与答。

1. 为什么 Java 在 String 的 hashCode() 中使用 31？
   
2. 它是质数，因此当用户通过另一个数字取模时，它们没有公共因子（除非它是 31 的倍数）。31 也是梅森素数（如 127 或 8191），是一个比某个 2 的幂少 1 的素数。这意味着如果机器的乘法指令很慢，那么取模可以通过一次移位和一次减法完成。
   
3. 如何从类型为double的变量中提取位以用��哈希？
   
4. Double.doubleToLongBits(x)返回一个 64 位的long整数，其位表示与double值x的浮点表示相同。
   
5. 使用(s.hashCode() % M)或Math.abs(s.hashCode()) % M进行哈希到 0 到 M-1 之间的值有什么问题？
   
6. 如果第一个参数为负数，则%运算符返回一个非正整数，这将导致数组索引越界错误。令人惊讶的是，绝对值函数甚至可以返回一个负整数。如果其参数为Integer.MIN_VALUE，那么由于生成的正整数无法用 32 位的二进制补码整数表示，这种情况就会发生。这种错误将非常难以追踪，因为它只会发生 40 亿分之一的时间！[字符串"polygenelubricants"的哈希码为-2³¹。]
   

练习

1. 下面的hashCode()实现是否合法？

public int hashCode() {
   return 17;
}

1. 解决方案。 是的，但这将导致所有键都哈希到相同的位置，这将导致性能不佳。
2. 分析使用分离链接、线性探测和二叉搜索树（BSTs）处理double键的空间使用情况。将结果呈现在类似第 476 页上的表中。解决方案。

• 顺序搜索。 24 + 48N. SequentialSearch 符号表中的 Node 占用 48 字节的内存（16 字节开销，8 字节键，8 字节值，8 字节下一个，8 字节内部类开销）。SequentialSearch 对象占用 24 字节（16 字节开销，8 字节第一个）加上节点的内存。
  请注意，booksite 版本每个SequentialSearch对象额外使用 8 字节（4 用于 N，4 用于填充）。
  
• 分离链接。 56 + 32M + 48N。SeparateChaining符号表消耗 8M + 56 字节（16 字节开销，20 字节数组开销，8 字节指向数组，每个数组条目的引用 8 字节，4 字节 M，4 字节 N，4 字节填充），再加上 M 个SequentialSearch对象的内存。
  

创意练习

1. 哈希攻击。 找到 2^N 个长度为 N 的字符串，它们具有相同的hashCode()值，假设String的hashCode()实现（如Java 标准中指定的）如下：

public int hashCode() {
   int hash = 0;
   for (int i = 0; i < length(); i++)
      hash = (hash * 31) + charAt(i);
   return hash;
}

1. 解决方案。 很容易验证"Aa"和"BB"哈希到相同的hashCode()值（2112）。现在，任何由这两个字符串以任何顺序连接在一起形成的长度为 2N 的字符串（例如，BBBBBB，AaAaAa，BBAaBB，AaBBBB）将哈希到相同的值。这里是一个具有相同哈希值的 10000 个字符串的列表。
2. 糟糕的哈希函数。 考虑以下用于早期 Java 版本的String的hashCode()实现：

public int hashCode() {
   int hash = 0;
   int skip = Math.max(1, length() / 8);
   for (int i = 0; i < length(); i += skip)
      hash = (hash * 37) + charAt(i);
   return hash;
}

1. 解释为什么你认为设计者选择了这种实现，然后为什么你认为它被放弃，而选择了上一个练习中的实现。
   解决方案。 这样做是希望更快地计算哈希函数。确实，哈希值计算得更快，但很可能许多字符串哈希到相同的值。这导致在许多真实输入（例如，长 URL）上性能显著下降，这些输入都哈希到相同的值，例如，http://www.cs.princeton.edu/algs4/34hash/*****java.html。

普林斯顿算法讲义（二）（4）https://developer.aliyun.com/article/1484178