CS61B 课程笔记（Lecture 21 Trees, BSTs)

抽象数据类型（ADTs）

抽象数据类型（ADT）是通过其操作而非具体实现进行定义的。这种定义方式使我们能够专注于数据结构的行为而不是其内部细节。例如，在项目 proj1a 中，我们实现了两个具体的 Deque（双端队列）：ArrayDeque 和 LinkedListDeque。虽然这两个类提供了相同的方法接口，但它们的实现方式却截然不同。在这种情况下，我们可以说 ArrayDeque 和 LinkedListDeque 是 Deque ADT 的具体实现。通过这种描述，我们可以看到 ADT 和接口之间的关系：在概念上，Deque 是一个接口，而 ArrayDeque 和 LinkedListDeque 是其具体实现。因此，在代码中，我们通过让 ArrayDeque 和 LinkedListDeque 类继承自 Deque 接口来表达这种关系。

常用的 ADT 示例

栈（Stack）
- 栈是一种支持后进先出（LIFO）元素检索的结构。
- 主要操作：
  - push(int x)：将元素 x 放入栈顶。
  - int pop()：取出栈顶的元素并返回。
列表（List）
- 列表是一个有序的元素集合，可以包含重复元素。
- 主要操作：
  - add(int i)：在索引 i 处添加一个元素。
  - int get(int i)：获取索引 i 处的元素。
集合（Set）
- 集合是一个无序的、唯一元素的集合，不允许重复。
- 主要操作：
  - add(int i)：向集合中添加一个元素。
  - boolean contains(int i)：检查集合是否包含元素 i。
映射（Map）
- 映射是一组键/值对的集合，每个键对应一个值。
- 主要操作：
  - put(K key, V value)：将键值对放入映射中。
  - V get(K key)：获取与键对应的值。

这些加粗的 ADT 是更大接口 Collections 的子接口，显示了它们之间的层级关系和归属。

ADTs 的优势

ADT 使我们能够以高效和优雅的方式使用面向对象编程。例如，在 proj1b 中，你可以看到如何在不影响使用的情况下交换 OffByOne 和 OffByN 比较器，因为它们都实现了相同的接口。这种灵活性使得不同的实现可以互换使用，而不需要改变客户端代码的其他部分。类似地，你也可以交替使用 ArrayDeque 或 LinkedListDeque，因为它们都实现了 Deque ADT。

在接下来的章节中，我们将定义一些新的 ADT，并列举它们的不同实现，进一步探讨它们在编程中的应用和优势。这种方式不仅提升了代码的可读性和可维护性，还增强了程序的灵活性。通过深入理解和使用 ADT，我们可以更有效地解决复杂问题。

发明二叉搜索树

虽然链表在某些方面很好，但即使链表已排序，查找一个项目的效率仍然很低。例如，如果项目位于链表的末尾，那么查找这个项目将需要线性时间 \(O(n)\)。这种查找效率显然不够理想。

二分搜索的优势

我们知道，对于数组来说，可以使用二分搜索来更快地找到元素。具体而言，二分搜索的时间复杂度为 \(O(\log n)\)。其基本思想是利用数组的有序性，通过逐步缩小搜索范围来快速找到目标元素。

二分搜索的工作原理：

选择中间元素：首先，我们查看数组的中间元素。
比较与决策：
- 如果中间元素大于目标元素，则目标元素在左半部分，接着我们在左半部分继续搜索。
- 如果中间元素小于目标元素，则目标元素在右半部分，我们在右半部分继续搜索。
递归或迭代：我们继续重复这一过程，直到找到目标元素，或者确定目标元素不在数组中。

通过这种方式，二分搜索显著提高了查找效率。

在链表中进行二分搜索的困难

然而，在链表中实施二分搜索并不简单。由于链表的特点，我们无法直接访问中间元素，必须从头开始遍历链表，直至到达中间节点。这意味着在链表中查找目标元素的时间复杂度仍然是线性的 \(O(n)\)。

优化思路

一个可能的优化方法是在链表中保留对中间节点的引用。这种方式可以让我们在常量时间内直接访问中间节点。接着，如果我们能够反转节点的指针，使得我们可以同时访问左半部分和右半部分，那么理论上可以将搜索时间缩短。

更进一步，我们可以在每个递归调用的中间节点上添加指针，这样不仅可以访问当前的中间节点，还能更高效地查找。

视觉化树结构

将这种优化结构纵向拉伸，你将会看到一个树形结构。这种树被称为二叉树（Binary Tree），因为每个节点都可以有两个子节点。这种结构不仅提高了查找效率，还提供了更多灵活性，使得我们可以更高效地实现数据的插入和删除操作。

二叉搜索树（BST）

为了进一步提高查找效率，我们引入了二叉搜索树（BST）的概念。在二叉搜索树中，节点的排列遵循以下规则：

每个节点的左子树包含的所有键值都小于该节点的键值。
每个节点的右子树包含的所有键值都大于该节点的键值。

这种结构使得我们在进行查找、插入和删除操作时，都能保持 \[O(\log n)\] 的时间复杂度（前提是树保持平衡）。

通过引入二叉搜索树，我们解决了链表查找效率低下的问题，并提供了一种更优雅的数据组织方式。

树的性质

树是数据结构中的一种重要形式，由以下部分构成：

节点：树的基本元素，存储数据。
边：连接节点的线，用于表示节点之间的关系。

树的基本特征

唯一路径：任意两个节点之间只有一条路径，确保了树的层次结构和连通性。
根节点：树中选定的特殊节点，没有父节点，通常作为树的起始点。
叶子节点：没有子节点的节点，表示树的末端。

树的结构是递归的，因此每个节点可以视为树的根，子节点形成新的子树。

特定类型的树

根据特定的约束，我们可以引入新的树类型：

1. 二叉树

二叉树是树的一种特殊形式，满足以下条件：

每个节点最多有两个子节点，分别称为左子节点和右子节点。
这意味着每个节点可以是：
- 叶子节点（没有子节点）
- 只有左子节点
- 只有右子节点
- 同时有左、右两个子节点

这种限制使得树的结构更加简单，并便于实现各种操作。

2. 二叉搜索树（BST）

在二叉树的基础上，二叉搜索树添加了更多的约束，以提高查找效率：

键的排列规则：
- 每个节点 \(X\) 的左子树中的每个键都小于 \(X\) 的键。
- 每个节点 \(X\) 的右子树中的每个键都大于 \(X\) 的键。

这种结构使得在树中查找、插入和删除操作都能保持 \(O(\log n)\) 的时间复杂度（假设树是平衡的）。这一属性是理解和实现二叉搜索树的关键。

注意：我们将在本模块及后续的学习中频繁引用这一属性。

二叉搜索树的实现

以下是我们在模块中将使用的二叉搜索树（BST）类的简单实现：

private class BST<Key> {
    private Key key;       // 存储节点的键值
    private BST left;      // 指向左子树
    private BST right;     // 指向右子树

    // 构造函数，接受键值和左右子树
    public BST(Key key, BST left, BST right) {
        this.key = key;
        this.left = left;
        this.right = right;
    }

    // 只接受键值的构造函数，左右子树默认为 null
    public BST(Key key) {
        this.key = key;
    }
}

关键点解析

节点属性：
- key：表示当前节点存储的值或键。
- left：指向左子节点，如果没有则为 null。
- right：指向右子节点，如果没有则为 null。
构造函数：
- 第一个构造函数允许创建一个完整的节点，包括其子树。
- 第二个构造函数允许只创建一个单独的节点，其左右子树默认为 null。

二叉搜索树操作

在二叉搜索树（BST）中，基本的操作包括搜索、插入和删除。每个操作都依赖于 BST 的性质，以高效地维护数据结构的完整性。

1. 搜索

搜索操作利用了 BST 的特性，即左子树的所有元素都小于父节点，右子树的所有元素都大于父节点。我们从根节点开始，逐步向下比较：

如果要查找的元素 \(X\) 等于当前节点的键，则找到了该元素。
如果 \(X\) 小于当前节点的键，则在左子树中继续查找。
如果 \(X\) 大于当前节点的键，则在右子树中继续查找。

这个过程直到找到目标元素，或者到达一个叶子节点（即当前节点为空），表示树中不存在该元素。

static BST find(BST T, Key sk) {
   if (T == null)
      return null;  // 元素未找到
   if (sk.equals(T.key))
      return T;      // 找到元素
   else if (sk ≺ T.key)
      return find(T.left, sk);  // 在左子树中查找
   else
      return find(T.right, sk); // 在右子树中查找
}

在理想情况下（即树是平衡的），搜索操作的时间复杂度为 \[O(\log n)\]。

2. 插入

插入新元素的操作与搜索相似。首先，我们搜索要插入的元素：

如果找到该元素，则不进行任何操作（BST 不允许重复元素）。
如果未找到，则我们将在树中适当的位置插入新节点。

在确定新节点的位置时，保持 BST 的属性非常重要。我们始终将新节点插入到叶子节点的位置。

static BST insert(BST T, Key ik) {
  if (T == null)
    return new BST(ik);  // 创建新节点
  if (ik ≺ T.key)
    T.left = insert(T.left, ik);  // 在左子树中插入
  else if (ik ≻ T.key)
    T.right = insert(T.right, ik); // 在右子树中插入
  return T;  // 返回树的根节点
}

同样，插入操作的平均时间复杂度为 \[O(\log n)\]。

3. 删除

删除操作比插入和搜索要复杂，尤其是在要删除的节点有子节点时。删除操作可以分为三种情况：

(1) 删除没有子节点的节点

如果要删除的节点是叶子节点，我们只需将其父节点指向其 null，然后该节点会被垃圾收集器回收。

(2) 删除有一个子节点的节点

如果要删除的节点只有一个子节点，我们只需将其父节点的指针重新指向该子节点，这样就保留了 BST 的性质。

(3) 删除有两个子节点的节点

这是最复杂的情况。我们不能简单地将一个子节点替代被删除的节点，因为这会破坏 BST 的性质。相反，我们需要找到一个合适的替代节点。常用的替代方法有：

从左子树中找到最右的节点（即左子树的最大值）。
从右子树中找到最左的节点（即右子树的最小值）。

这些节点的键值在 BST 中符合要求：它们大于左子树中的所有元素，并小于右子树中的所有元素。

以下是删除有两个子节点的节点的示例：

找到替代节点，例如，从左子树中找到最右的节点。
用替代节点替换要删除的节点。
递归删除替代节点，确保 BST 的结构不被破坏。

以下是删除操作的示例代码：

static BST delete(BST T, Key dk) {
    if (T == null) return null; // 树为空

    if (dk.equals(T.key)) {
        // 找到要删除的节点
        if (T.left == null && T.right == null) {
            return null; // 情况 1：无子节点
        } else if (T.left == null) {
            return T.right; // 情况 2：只有右子节点
        } else if (T.right == null) {
            return T.left; // 情况 2：只有左子节点
        } else {
            // 情况 3：两个子节点
            Key successorKey = findMin(T.right).key; // 找到右子树的最小值
            T.key = successorKey; // 替换节点的键
            T.right = delete(T.right, successorKey); // 删除右子树中的最小值节点
        }
    } else if (dk ≺ T.key) {
        T.left = delete(T.left, dk); // 在左子树中删除
    } else {
        T.right = delete(T.right, dk); // 在右子树中删除
    }
    return T; // 返回树的根节点
}

static BST findMin(BST T) {
    while (T.left != null) {
        T = T.left; // 找到最左节点（最小值）
    }
    return T;
}

BST 作为集合和映射

二叉搜索树（BST）不仅可以用作集合（Set）数据结构的实现，也可以扩展为映射（Map）数据结构。

1. BST 作为集合

集合是一个无序的唯一元素集合，通常支持以下基本操作：

添加元素：将一个新元素插入集合。
删除元素：从集合中移除一个元素。
查找元素：检查某个元素是否在集合中。

使用 BST 实现集合

通过使用 BST，我们可以高效地实现这些操作。由于 BST 的性质，使得每个节点的左子树的所有元素都小于父节点，而右子树的所有元素都大于父节点，我们可以利用这一点来优化查找、插入和删除操作：

查找（contains）：查找某个元素时，始终从根节点开始，根据元素与当前节点键的比较决定向左或向右子树移动。由于树的高度在理想情况下为 \(O(\log n)\)，因此查找的时间复杂度为 \(O(\log n)\)。
插入：插入新元素时，类似于查找，从根节点开始，找到合适的位置将新元素插入。由于 BST 的结构特性，插入操作也可以在 \(O(\log n)\) 的时间内完成。
删除：如前所述，删除操作可能需要处理三种情况，但在平均情况下，删除操作的复杂度也为 \(O(\log n)\)。

因此，使用 BST 实现的集合不仅支持快速查找，还能高效管理元素的添加和删除。

2. BST 作为映射

映射（Map）是一种将键（key）映射到值（value）的数据结构。每个键都是唯一的，通过键可以快速查找对应的值。

使用 BST 实现映射

通过在 BST 的每个节点中存储 (key, value) 对，可以将 BST 转换为映射。每个节点不仅有一个键，还包含一个与之对应的值。

实现步骤：

节点结构：定义一个节点结构，包含键、值、左子节点和右子节点。

private class MapNode<Key, Value> {
    private Key key;
    private Value value;
    private MapNode left;
    private MapNode right;

    public MapNode(Key key, Value value, MapNode left, MapNode right) {
        this.key = key;
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public MapNode(Key key, Value value) {
        this.key = key;
        this.value = value;
    }
}

查找（get）：与集合中的查找操作相似，通过键值比较确定在树中的位置。如果找到了该键，返回对应的值；如果未找到，则返回 null。

static Value get(MapNode<Key, Value> T, Key k) {
    if (T == null) return null; // 键未找到
    if (k.equals(T.key)) return T.value; // 找到键，返回值
    if (k ≺ T.key) return get(T.left, k); // 在左子树中查找
    else return get(T.right, k); // 在右子树中查找
}

插入（put）：插入新的键值对时，首先查找该键。如果键已存在，则更新其值；如果键不存在，则在适当位置插入新的节点。

static MapNode<Key, Value> put(MapNode<Key, Value> T, Key k, Value v) {
    if (T == null) return new MapNode(k, v); // 创建新节点
    if (k.equals(T.key)) {
        T.value = v; // 更新值
    } else if (k ≺ T.key) {
        T.left = put(T.left, k, v); // 在左子树中插入
    } else {
        T.right = put(T.right, k, v); // 在右子树中插入
    }
    return T; // 返回树的根节点
}