前言
实验文档：https://sp21.datastructur.es/materials/lab/lab7/lab7
在本实验中，你将实现 BSTMap——一个基于二叉搜索树（BST）的 Map61B 接口实现，该接口代表一种基础的基于树的映射结构。你需要完全从零开始实现它，并按照教程提供的接口进行开发。
完成实现后，你需要将你的 BSTMap 与基于链表的映射实现 ULLMap 以及 Java 内置的 TreeMap 类（同样基于 BST）进行性能对比分析。
BSTMap
你需要创建一个 BSTMap 类来实现 Map61B 接口，该类以二叉搜索树（BST）作为核心数据结构。代码文件必须命名为 BSTMap.java。
除以下方法外，必须实现 Map61B 接口中的所有方法：
remove()iterator()keySet()
对于上述未实现的方法，应抛出 UnsupportedOperationException 异常。
初始阶段，你的代码可能无法编译，因为尚未实现所有必要方法。可先写出所有方法签名，暂时为未完成的方法抛出 UnsupportedOperationException，随后逐步实现具体逻辑。
除此之外，你还需要在 BSTMap 中添加一个非接口要求的方法 printInOrder()，用于按照键的递增顺序打印 BSTMap 的内容。此方法不会作为测试依据，但有助于调试你的实现。
在实现中，你需要假设 BSTMap<K,V> 中的泛型键 K 继承自 Comparable 接口，即所有泛型键 K 均要实现 compareTo 方法。
可通过 Java 中的有界类型参数（bounded type parameter）强制这一约束（参考下方 Oracle 文档示例）：
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 来测试你的实现。
下面的资料可能会对你有帮助：
有界类型参数
按照有界类型参数的要求，我们在声明 BSTMap 的时候需要这样写：
public class BSTMap<K extends Comparable<K>, V>
|
Key extends Comparable<Key> 的意思？
这是一个有界类型参数（bounded type parameter），它告诉编译器：
任何作为 Key 的类型，都必须是 Comparable<Key> 的子类型（或者本身实现了这个接口）。
换句话说，Key 可以是任何类，只要它实现了：
public int compareTo(Key other)
|
这样的接口方法。
- 为什么
Key 自己没有 compareTo 方法也可以这样写？
因为在声明泛型类的时候，Key 只是一个占位符，它并不是一个具体的类，所以它没法去“重写”方法。
约束写在这里，是为了保证当你真正使用 BSTMap 时，传入的类型满足要求，比如：
BSTMap<String, Integer> bst = new BSTMap<>();
BSTMap<Integer, String> bst = new BSTMap<>();
BSTMap<Object, String> bst = new BSTMap<>();
|
具体实现
第一点：在编码前，首先需要明确对 null 值的处理：
key 值不允许为 null，但 value 值可以为 null。- 当
get() 方法没有找到目标节点时会返回 null。
- 当
remove() 方法没有找到要删除的节点时也会返回 null。
因此，将 “值为 null 的节点” 与 “未找到节点时返回的 null” 区分开是十分必要的。
第二点：必须得先弄明白每个方法的作用，才能写好递归：
- 对于广义上的 getter 类方法
- 如
get() 只会读取 BST 的内部节点，不会对 BST 的内部结构做出任何修改。
- 这种方法在调用递归时，每层递归会将下一层递归返回的结果直接 return，而不需要进行存储，所以 每层递归返回的都是最后一次递归的结果 。
- 最后一次递归会找到目标键，结束递归并将对应值直接返回。整个方法的返回值就是最后一次递归返回的结果。
- 对于广义上的 setter 类方法
- 如
put() 和 remove() 会将 BST 的内部节点进行增加和删除，导致 BST 发生结构上的变化。
- 这种方法在调用递归时，每层递归都会对本层状态进行一系列修改，所以每层递归都必须用下一层递归返回的结果更新自己的引用。也就是说必须用
node.left = ... 或 node.right = ... 对下层返回的结果进行保存，接着对本层字段进行一系列更新，最后将更新的结果返回给上一层递归。所以 每层递归返回的都是本层更新后的结果 。
- 最后一次递归会找到目标节点，就目标节点进行一系列修改，将修改结果返回给上一层递归，接着上一层递归会接着进行修改和返回······ 整个方法的返回值将是经过一系列修改后的最初调用时的根（不是根号，可以理解为根节点）。
package bstmap;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
public class BSTMap<K extends Comparable<K>, V> implements Map61B<K, V> {
private BSTNode root;
private class BSTNode {
private K key;
private V value;
private BSTNode left, right;
private int size;
public BSTNode(K key, V value, int size) {
this.key = key;
this.value = value;
this.size = size;
}
}
public BSTMap() {
root = null;
}
@Override
public void clear() {
root = null;
}
@Override
public boolean containsKey(K key) {
if (key == null) {
throw new IllegalArgumentException("calls containsKey() with a null key");
}
return getNode(key, root) != null;
}
@Override
public V get(K key) {
if (key == null) {
throw new IllegalArgumentException("calls get() with a null key");
}
BSTNode node = getNode(key, root);
return (node == null) ? null : node.value;
}
private BSTNode getNode(K key, BSTNode node) {
if (node == null) {
return null;
}
int cmp = key.compareTo(node.key);
if (cmp == 0) {
return node;
} else if (cmp < 0) {
return getNode(key, node.left);
} else {
return getNode(key, node.right);
}
}
@Override
public int size() {
return size(root);
}
private int size(BSTNode node) {
return (node == null) ? 0 : node.size;
}
@Override
public void put(K key, V value) {
if (key == null) {
throw new IllegalArgumentException("calls put() with a null key");
}
root = put(key, value, root);
}
private BSTNode put(K key, V value, BSTNode node) {
if (node == null) {
return new BSTNode(key, value, 1);
}
int cmp = key.compareTo(node.key);
if (cmp < 0) {
node.left = put(key, value, node.left);
} else if (cmp > 0) {
node.right = put(key, value, node.right);
} else {
node.value = value;
}
node.size = 1 + size(node.left) + size(node.right);
return node;
}
@Override
public V remove(K key) {
if (key == null) {
throw new IllegalArgumentException("calls remove() with a null key");
}
BSTNode node = getNode(key, root);
if (node == null) {
return null;
}
V value = node.value;
root = remove(key, root);
return value;
}
private BSTNode remove(K key, BSTNode node) {
if (node == null) {
return null;
}
int cmp = key.compareTo(node.key);
if (cmp < 0) {
node.left = remove(key, node.left);
} else if (cmp > 0) {
node.right = remove(key, node.right);
} else {
if (node.left == null) {
return node.right;
}
if (node.right == null) {
return node.left;
}
BSTNode t = node;
node = min(t.right);
node.right = deleteMin(t.right);
node.left = t.left;
}
node.size = 1 + size(node.left) + size(node.right);
return node;
}
private BSTNode min(BSTNode node) {
if (node == null) {
return null;
}
return (node.left == null) ? node : min(node.left);
}
private BSTNode deleteMin(BSTNode node) {
if (node == null) {
return null;
}
if (node.left == null) {
return node.right;
}
node.left = deleteMin(node.left);
node.size = 1 + size(node.left) + size(node.right);
return node;
}
@Override
public V remove(K key, V value) {
if (key == null) {
throw new IllegalArgumentException("calls remove() with a null key");
}
BSTNode node = getNode(key, root);
if (node != null && (value == null ? node.value == null : value.equals(node.value))) {
return remove(key);
}
return null;
}
@Override
public Set<K> keySet() {
TreeSet<K> keys = new TreeSet<>();
inOrder(root, keys);
return keys;
}
private void inOrder(BSTNode node, TreeSet<K> keys) {
if (node == null) {
return;
}
inOrder(node.left, keys);
keys.add(node.key);
inOrder(node.right, keys);
}
@Override
public Iterator<K> iterator() {
return keySet().iterator();
}
public void printInOrder() {
StringBuilder s = new StringBuilder();
printInOrder(root, s);
System.out.println(s);
}
private void printInOrder(BSTNode node, StringBuilder s) {
if (node == null) {
return;
}
printInOrder(node.left, s);
s.append(node.key);
s.append(" ");
s.append(node.value == null ? "null" : node.value.toString());
s.append("\n");
printInOrder(node.right, s);
}
}
|
有多快？
在 InsertRandomSpeedTest.java 和 InsertInOrderSpeedTest.java 中提供了两个交互式速度测试程序。注意：在完成 BSTMap 的实现之前，不要尝试运行这些测试。完成后，你可以在 IntelliJ 中运行它们。
InsertRandomSpeedTest 类将用于比较：你实现的 BSTMap、提供的 ULLMap（基于链表的简单实现）、Java 内置的 TreeMap（基于平衡 BST）、Java 内置的 HashMap（基于哈希表，将在后续实验学习）的元素插入速度。程序会要求你输入：字符串长度（要插入的键的长度）、数据规模（插入的键值对数量）、程序会生成指定数量的随机字符串，并将它们作为 <String, Integer> 键值对插入各个 Map 中。
比较你的实现与工业级强度的实现之间的性能差异。注意：小规模数据可能无法准确反映渐近复杂度，因此请确保测试数据足够大（如 10,000 或 100,000 级别），以避免结果不符合预期。将测试结果记录在 speedTestResults.txt 中，格式不限，数据点数量无硬性要求。
接着尝试运行 InsertInOrderSpeedTest，该测试与 InsertRandomSpeedTest 类似，但所有字符串按照键的 字典序递增 插入。如果发现有趣的现象，可以和同学或助教讨论原因。
选做练习
以下内容不参与评分，但自动评分器仍会给你反馈。
请在 BSTMap 类中实现以下方法：
iterator()keySet()remove(K key)remove(K key, V value)
方法说明：
iterator()：应返回一个遍历所有键（Key）的迭代器。remove(K key)：若 key 不存在于 BSTMap 中，返回 null；若存在，则删除该键值对并返回对应的 value。remove(K key, V value)：扩展功能，仅在键值完全匹配时删除。
注意：
- 实现
keySet() 和 iterator() 时，不得使用额外的实例变量存储键集合（即需动态生成）。
remove() 的实现难度较高，建议作为深入练习。
提交
确保你完成了 BSTMap.java 与 speedTestResults.txt 并像往常一样通过 git 提交到 Gradescope 上。
