CS61B 课程笔记（Disc 09 Disjoint Sets, Trees, and Hashing)

1. WQU 和路径压缩

题目：
假设我们有 8 个集合，表示为整数 1 到 8，初始状态为完全不相交的集合。经过一系列 union() 和 find() 操作（使用路径压缩），画出 WQU（加权快速合并）树，并写下 find() 操作的结果。每次合并时，若存在相同的根节点，则选择较小的整数作为根节点。

操作顺序：

  • union(2, 3)
  • union(1, 6)
  • union(5, 7)
  • union(8, 4)
  • union(7, 2)
  • find(3)
  • union(6, 4)
  • union(6, 3)
  • find(7)
  • find(8)

答案：

  • find(3) 结果是 2
  • find(7) 结果是 1
  • find(8) 结果是 1

最终的树结构如下：

1
2
3
4
5
6
7
      1
     / \
    6   2
   /     \
  4       3
 / \     /
8   5   7

2. 判断是否为二叉搜索树（BST）

题目：
给定方法 isBSTBad 用于检查一个二叉树是否为二叉搜索树 (BST)，但在某些情况下会返回错误。举例说明 isBSTBad 方法为何出错。然后编写 isBSTGood 方法，确保对任何二叉树都能正确判断是否为 BST。

以下是二叉树的节点类定义：

1
2
3
4
5
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

解答：

  • 错误例子：

    1
    2
    3
    4
    5
      10
     /  \
    5    15
       /
      12

    isBSTBad 方法会错误地认为这是一个 BST，因为它只检查节点值是否大于左子节点且小于右子节点，而没有检查节点值是否大于左子树的所有节点且小于右子树的所有节点。

  • 正确的 isBSTGood 实现：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public static boolean isBSTGood(TreeNode T) {
        return isBSTHelper(T, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    public static boolean isBSTHelper(TreeNode T, int min, int max) {
        if (T == null) {
            return true;
        } else if (T.val < min || T.val > max) {
            return false;
        } else {
            return isBSTHelper(T.left, min, T.val) && isBSTHelper(T.right, T.val, max);
        }
    }

3. 2-3 树和左倾红黑树 (LLRB)

3.1 插入操作

题目：
给定一个 2-3 树，依次插入 18, 38, 12, 和 13，绘制出最终的 2-3 树。

解答：

插入后的树结构：

1
2
3
4
5
6
7
8
9
    8             8             8             8 14
   / \           / \           / \           /   \
  4   6         4   6         4   6         4     6
 /     \       /     \       /     \       /       \
3       7     3       7     3       7     3         7
                      10    14    10       12
                            15    18       10 13
                                         16
                                         15 18 38
3.2 转换为左倾红黑树

题目：
将上述生成的 2-3 树转换为左倾红黑树 (LLRB)。

解答：

转换后的左倾红黑树：

1
2
3
4
5
6
7
8
       14
      /  \
     8    16
    / \     \
   6  12    18
  / \ / \   /
 4  7 10 13 15 38
3
3.3 最大比较次数

题目：
如果 2-3 树的深度为 $ H $，在对应的左倾红黑树中，找到某个键所需的最大比较次数是多少？

解答： 最大比较次数为 $ 2H $。在左倾红黑树中，最坏情况下沿着从根到叶子的路径经过最多 $ 2H $ 个节点。

4. 哈希

4.1 hashCode() 实现

题目：
以下是 Integer 类中 hashCode() 方法的三种实现。分别判断每种实现是否有效，并解释其优缺点。

  1. ```java public int hashCode() { return -1; } 

    1
    2
    3
    4
    5

    2. ```java
       public int hashCode() {
           return intValue() * intValue();
       }

  2. public int hashCode() {
    return super.hashCode();
}

解答：

  1. 有效，但哈希冲突非常频繁，所有整数都会映射到相同的哈希值，冲突率为 100%。
  2. 有效，但绝对值相同的整数（如 5 和 -5）会产生碰撞。建议直接返回 intValue()。
  3. 无效，因为 super.hashCode() 返回的是对象在内存中的位置，相等的整数不会有相同的哈希值。
4.2 HashMap 相关问题

题目：
以下两种情况下，是否可以检索已插入到 HashMap 的条目？回答 总是、有时 或 从不 并解释原因。

  1. 修改已插入 HashMap 中的键后，能否检索到该条目？

  2. 修改已插入 HashMap 中的值后，能否检索到该条目？

解答： (a) 有时。如果修改键后导致其 hashCode() 发生变化，则无法再检索到该条目。

  1. 总是。HashMap 中条目的检索由键决定，修改值不会影响检索。