Lab 7：BSTMap

• 介绍
• BSTMap
• 所以……它到底有多快？
• 可选练习
• 实验总结与提交
• 可选渐近分析题

介绍#

在本实验中，你将创建 BSTMap：它是 Map61B 接口的一种基于 BST 的实现，表示一个基本的、基于树的映射。你会完全从零开始创建它，并把所提供的接口当作指南。

完成实现后，你会把自己的实现性能与基于列表的 Map 实现 ULLMap 以及 Java 内置的 TreeMap 类（它也使用 BST）进行比较。

BSTMap#

创建一个名为 BSTMap 的类，使用 BST（二叉搜索树，Binary Search Tree）作为核心数据结构，实现 Map61B 接口。你必须在名为 BSTMap.java 的文件中完成它。除 remove、iterator 和 keySet 外，你的实现必须实现 Map61B 中给出的所有方法。对于这几个方法，应抛出 UnsupportedOperationException。

在创建 BSTMap 类并实现 Map61B 的所有方法之前，你的代码无法编译。你可以一次实现一个方法：先写出所有必需方法的方法签名，但在实现中抛出 UnsupportedOperationException；等轮到实际编写某个方法时，再完成它。

你的 BSTMap 还应额外添加一个 printInOrder() 方法（该方法没有在 Map61B 接口中给出），按 Key 递增顺序打印 BSTMap。我们不会测试这个方法的结果，但你会发现它有助于测试自己的实现！

在实现中，你应当假定 BSTMap<K, V> 中的泛型键 K 扩展了 Comparable ↗。换句话说，你可以假定泛型键 K 具有 compareTo 方法。在 Java 中，可以使用有界类型参数 ↗强制满足这一条件。考虑下面这个摘自 Oracle 文档的示例：

/*
 * Bounded type parameters allow you to invoke methods defined in the bounds:
 * The `isEven` method invokes the `intValue` method defined in the
 * `Integer` class through `n`.
 */

public class NaturalNumber<T extends Integer> {

    private T n;

    public NaturalNumber(T n)  { this.n = n; }

    public boolean isEven() {
        return n.intValue() % 2 == 0;
    }

    // ...
}

我们还建议你使用一个私有的嵌套 BSTNode 类，以帮助完成实现。如何设计和使用这个内部类由你决定！

你可以使用 TestBSTMap.java 测试自己的实现。

下面这些资源可能会有帮助：

• Lecture 16 的幻灯片 ↗。
• 课程资源页面中《Data Structures Into Java》第 109 页和第 111 页的 BST 代码。
• 可选教材 ↗中的 BST 代码。
• ULLMap.java（已提供）：一个能够正常工作的、基于无序链表的 Map61B 实现。

所以……它到底有多快？#

InsertRandomSpeedTest.java 和 InsertInOrderSpeedTest.java 中提供了两个交互式速度测试。在完成 BSTMap 之前，不要尝试运行这些测试。准备好后，可以在 IntelliJ 中运行它们。

InsertRandomSpeedTest 类会测试你的 BSTMap、已提供的 ULLMap、Java 内置 TreeMap 和 Java 内置 HashMap（你会在下一个实验中进一步探索它）在插入元素时的速度。它会询问用户：要插入的每个 String 所需的长度，以及输入规模（要执行的插入次数）。然后，它会生成指定数量、指定长度的 String，并将它们作为 <String, Integer> 对插入映射中。

尝试运行它，看看随着插入次数增加，你的数据结构与朴素实现和工业级实现相比如何扩展。请记住，在小样本上，渐近分析并不具有代表性；如果看到令人困惑的趋势，请确保输入足够大。把结果记录在名为 speedTestResults.txt 的文件中。结果没有规定的标准格式，也没有规定所需的数据点数量。

现在尝试运行 InsertInOrderSpeedTest。它的行为与 InsertRandomSpeedTest 类似，但这一次，<String, Integer> 键值对中的 String 会按照字典序递增顺序 ↗插入。如果你观察到任何有趣现象（希望你观察到了），应当与其他学生和/或 TA 讨论。

可选练习#

这一部分不会评分，但你仍然可以从自动评分器获得反馈。

在 BSTMap 类中实现 iterator()、keySet()、remove(K key) 和 remove(K key, V value)。实现 iterator 方法时，应当返回一个遍历键的迭代器。实现 remove() 相当有挑战性。作为额外挑战，请在不使用第二个实例变量存储键集合的情况下实现 keySet() 和 iterator。

对于 remove，如果参数键在 BSTMap 中不存在，应返回 null。否则，删除键值对 (key, value) 并返回 value。

实验总结与提交#

实验结束时，你的 TA 会讲解参考解答。如果你尚未完成实验，这会很有帮助，因为我们不希望你在实验课之外被这个实验困住太久。（这也是鼓励你参加实验课的一个理由！）

确保提交完成的 BSTMap.java 和 speedTestResults.txt，并像往常一样通过 Git 和 Gradescope 提交。

可选渐近分析题#

给定 B——一个包含 N 个键值对的 BSTMap——以及 (K, V)——一个随机键值对——回答下列问题。

除非另有说明，“大 O”界（例如 O(N)）和“大 Θ”界（例如 Θ(N)）指给定方法调用中的比较次数。

对于第 1–7 题，说明陈述是真还是假。对于第 8 题，给出运行时间界。

1. B.put(K, V) ∈ O(log(N))。

2. B.put(K, V) ∈ Θ(log(N))。

3. B.put(K, V) ∈ Θ(N)。

4. B.put(K, V) ∈ O(N)。

5. B.put(K, V) ∈ O(N²)。

6. 令 g(N) 表示：随机调用 B.put(K, V) 共 N 次，随后调用 B.containsKey(K)，完成这些操作所需的平均比较次数。那么，g(N) ~ 2(ln(N))。

   注意：我们写作 g(N) ~ f(N)，表示当 N 变大时，g(N) / f(N) -> 1。

7. 对于键 C != K，同时运行 B.containsKey(K) 和 B.containsKey(C) ∈ Ω(log(N))。

8. 设 BSTMap b 由一个 root Node（Key、Value 对）和两个名为 left 与 right 的 BSTMap 子树组成。进一步假定，方法 numberOfNodes(BSTMap b) 返回以 b.root 为根的 BSTMap 的节点数；它的运行时间是 Θ(n)，其中 n 是以 b 为根的 BSTMap 中的 Node 数量。对于某个正整数 z，mystery(b, z) 的运行时间（以大 O 记号表示）是多少？假定 b 有 N 个节点，请给出尽可能紧的界。

你的答案不应包含任何不必要的乘法常数或加法因子。

public Key mystery(BSTMap b, int z) {
    if (z > numberOfNodes(b) || z <= 0)
        return null;
    if (numberOfNodes(b.left) == z-1)
        return b.root.key;
    else if (numberOfNodes(b.left) > z)
        return mystery(b.left, z);
    else
        return mystery(b.right, z-numberOfNodes(b.left) - 1);
}

原始页面：https://sp21.datastructur.es/materials/lab/lab7/lab7 ↗