跳转至

Lab 7：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。

  1. 对于键 C != K，同时运行 B.containsKey(K) 和 B.containsKey(C) ∈ Ω(log(N))。
  2. 设 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