【UCB CS 61B SP24】Lecture 16 - Data Structures 2: ADTs, BSTs学习笔记

本文首先介绍了抽象数据类型与树的概念，接着重点讲解二叉搜索树的定义与操作方式，并用 Java 实现一个标准的二叉搜索树结构。

1. 抽象数据类型

首先引入一个概念叫做抽象数据类型（Abstract Data Type，ADT），本课程中我们所实现的各种数据结构其实都设计为了 ADT，那么 ADT 到底是什么概念？它有什么作用？

ADT 是计算机科学中一种重要的设计概念，它通过封装数据结构和操作来隐藏实现细节，仅对外暴露操作接口。在 Java 中，ADT 通过接口（Interface）和类的组合实现。

ADT 只暴露操作（如增删查改），隐藏具体存储方式（如数组、链表或树）。例如：List 接口定义了 add() 和 get()，但不关心底层是 ArrayList（数组）还是 LinkedList（链表）。

这样用户仅需关注“能做什么”，而非“如何实现”。例如：Queue 的 offer() 和 poll() 方法，无论是用循环数组还是链表实现，调用方式完全一致。

ADT 的核心优势如下：

• 降低复杂度：用户无需关心底层实现，例如使用 Map 时不必了解哈希表或红黑树的细节。
• 提高代码复用性：同一接口可适配多种实现，例如 List 可动态切换为数组或链表实现。
• 增强可维护性：修改底层实现（如优化性能）不会影响外部调用代码。
• 强制数据完整性：通过封装避免非法操作，例如栈不允许随机访问中间元素。

2. 树

树是一种非线性数据结构，由一组节点（Node）和连接这些节点的边（Edge）组成，与图相对比，树具有以下性质：

• 层级结构：存在唯一的根节点（Root），作为树的起点；
• 父子关系：除根节点外，每个节点有且仅有一个父节点（Parent），由于树具有层级结构与父子关系，因此可以看作是有方向的，而图的边既可以有方向也可以没方向；
• 无环性：树中不存在环路（无法从某节点出发沿边回到自身），因此树的边数为节点数减一，而图可以形成环路；
• 连通性：所有节点通过边连通（全连通），不存在孤立的子结构，而图可以存在孤立子图。

树的核心术语如下：

• 根节点：树的顶层节点，没有父节点；
• 子节点：直接连接在当前节点下方的节点；
• 父节点：直接连接在当前节点上方的节点；
• 叶子节点：没有子节点的节点（树的末端）；
• 内部节点：至少有一个子节点的节点；
• 边：连接两个节点的路径；
• 子树：某个节点及其所有后代组成的子结构；
• 深度：从根节点到当前节点的路径长度（根节点的深度为0或1，取决于定义）；
• 高度：从当前节点到最远叶子节点的路径长度（叶子节点的高度为0）；
• 度：一个节点拥有的子节点数量。

常见的树有以下这些类型：

• 二叉树：每个节点最多有两个子节点（左/右）；
• 二叉搜索树：左子树节点值 < 根节点值 < 右子树节点值；
• 平衡树：通过旋转等操作保持左右子树高度差可控（如 AVL 树、红黑树）；
• 多叉树：每个节点可以有多个子节点（如 B 树、文件系统树）；
• 堆：完全二叉树，满足父节点值 ≥ 或 ≤ 子节点值（最大堆/最小堆）。

树常用链式存储：

class TreeNode<T> {
    T data;
    List<TreeNode<T>> children;  // 多叉树
    TreeNode<T> left, right;  // 二叉树
}

完全二叉树也能用数组存储，父节点索引为 i，则左子节点为 2 * i + 1，右子节点为 2 * i + 2。

树具有四种遍历方式：

• 前序遍历：根 → 左子树 → 右子树，适用于复制树结构；
• 中序遍历：左子树 → 根 → 右子树，适用于二叉搜索树的有序输出；
• 后序遍历：左子树 → 右子树 → 根，适用于释放树内存；
• 层序遍历：按层级从上到下、从左到右，适用于求树的高度/宽度。

树的常见应用场景如下：

• 文件系统：目录和文件的层级管理；
• 数据库索引：B/B+ 树加速查询；
• 游戏 AI：决策树模拟行为逻辑；
• XML/HTML 解析：DOM 树表示文档结构；
• 机器学习：决策树分类算法。

3. 二叉搜索树

3.1 基础介绍

假设我们有一个排好序的有序链表如下图所示，如果像查找 G 在哪则需要从头遍历到结尾才能找到，搜索路径为 A -> B -> C -> D -> E -> F -> G：

有什么办法能快点找到这个节点呢？假设我们将链表首部指针移到中间并翻转左半部分的连接，那么搜索时间就会减半！首先我们找到了 D，判断 G 是大于 D 的，那么我们就向右边继续寻找，搜索路径为 D -> E -> F -> G：

既然这样，那么我们继续这样对半分，那么搜索时间就能继续减半，也就构成了二叉搜索树，搜索路径为 D -> F -> G：

二叉搜索树（Binary Search Tree，BST）是一种有序的二叉树数据结构，满足以下性质：

• 左子树所有节点值小于根节点值；
• 右子树所有节点值大于根节点值；
• 左右子树也必须是二叉搜索树。

其核心特性为：

• 有序性：中序遍历结果为升序序列；
• 动态操作效率：插入、删除、查找的平均时间复杂度为 $O(logn)$，最坏情况为 $O(n)$；
• 内存效率：非连续存储，动态扩展；
• 支持范围查询：可快速找到区间内的所有值。

3.2 操作方法及实现

（1）查找

想查找某个值是否在树中，可以从根节点递归地往下找，一共会有以下几种情况：

• 当前节点为 null，则已经查完整棵树了还未找到，不存在目标值，返回 false；
• 当前节点值 = 目标值，已找到，返回 true；
• 当前节点值 > 目标值，说明要查找的目标值在左子树上，递归查找左子树；
• 当前节点值 < 目标值，说明要查找的目标值在右子树上，递归查找右子树。

（2）插入

插入新值时同样也是采用递归的思想从根节点开始寻找插入的位置，流程不难理解：

• 若树为空，新节点直接成为根节点；
• 若树非空，则比较新值与当前节点值，有以下几种情况：
  • 新值 = 当前节点值：根据需求处理（通常不做处理，也就是不插入重复值）；
  • 新值 < 当前节点值：向左子树递归插入；
  • 新值 > 当前节点值：向右子树递归插入；
  • 当前节点为 null：找到了插入位置，创建新节点并返回。

（3）删除

删除操作相对复杂一点，我们可以将其分为三种情况来讨论：

• 删除叶节点：直接删除即可，即将其父节点所指向它的指针置为 null；

• 删除有一个子节点（或一边子树）的节点：将其父节点直接连接到该节点的子节点上，为什么这样构建新指针一定是对的？因为假如该节点在父节点的左侧，那么该节点及其子树一定也小于其父节点，因此父节点指向该节点的子树作为左子树一定是合理的，同理假如在右侧也一样。例如我们删除下面这棵树的 "flat"：
  
  

• 删除有两个子节点的节点：这种情况最复杂，我们需要选出一个节点顶替到当前节点的位置上，也就是将所选节点的值覆盖到当前节点后再将所选节点删除。那么选哪个节点最方便？答案是右子树中的最小节点（或左子树中的最大节点）。因为这两种类型的节点替换到当前节点上都能保证当前节点左子树中的所有值都小于自身，且右子树中的所有值的都大于自身，这两种类型的节点一定满足没有子树或最多只有一棵子树。例如我们删除下面这棵树的 k，最适合替代 k 的值为 g 与 m：
  
  我们选择用 g 替代 k，然后将 g 删除（回到了第二种情况，直接将 e 指向 f 即可完成 g 的删除）：
  

3.3 Java实现BinarySearchTree

根据前面的讲解，我们就可以实现二叉搜索树的每个操作：

package CS61B.Lecture16;

public class BinarySearchTree<T extends Comparable<T>> {
    private class Node {
        private T val;
        private Node left;
        private Node right;

        public Node(T val) {
            this.val = val;
            left = null;
            right = null;
        }
    }

    private Node root;

    public BinarySearchTree() {
        root = null;
    }

    public void insert(T val) {
        root = insertRecursive(root, val);
    }

    private Node insertRecursive(Node node, T val) {
        if (node == null) return new Node(val);  // 已找到插入位置

        int cmp = val.compareTo(node.val);
        if (cmp < 0) node.left = insertRecursive(node.left, val);  // 往左子树递归寻找插入位置
        else if (cmp > 0) node.right = insertRecursive(node.right, val);  // 往右子树递归寻找插入位置
        // 若值已存在则不做处理

        return node;
    }

    public boolean search(T val) {
        return searchRecursive(root, val);
    }

    private boolean searchRecursive(Node node, T val) {
        if (node == null) return false;  // 未找到目标值

        int cmp = val.compareTo(node.val);
        if (cmp < 0) return searchRecursive(node.left, val);  // 往左子树递归查找
        else if (cmp > 0) return searchRecursive(node.right, val);  // 往右子树递归查找
        else return true;  // 当前值等于目标值，已找到
    }

    public void delete(T val) {
        root = deleteRecursive(root, val);
    }

    private Node deleteRecursive(Node node, T val) {
        if (node == null) return null;

        int cmp = val.compareTo(node.val);
        if (cmp < 0) node.left = deleteRecursive(node.left, val);
        else if (cmp > 0) node.right = deleteRecursive(node.right, val);
        else {  // 已找到要删除的目标值
            // Case 1 & 2：没有子树或只有一棵子树
            if (node.left == null) return node.right;  // 如果没有子树则返回 null，如果有右子树则返回右子树
            if (node.right == null) return node.left;  // 如果有左子树则返回左子树

            // Case 3：既有左子树也有右子树
            Node minNodeInRight = findMinNodeInRight(node.right);  // 找出右子树中的最小值
            node.val = minNodeInRight.val;  // 替换到当前节点上
            node.right = deleteRecursive(node.right, minNodeInRight.val);  // 递归地在右子树中删除这个最小值
        }

        return node;
    }

    private Node findMinNodeInRight(Node node) {
        while (node.left != null) node = node.left;
        return node;
    }

    // 中序遍历，用于验证二叉搜索树是否正确
    public void inOrderTraversal() {
        inOrderTraversalRecursive(root);
        System.out.println();
    }

    private void inOrderTraversalRecursive(Node node) {
        if (node == null) return;

        inOrderTraversalRecursive(node.left);  // 先递归遍历左子树
        System.out.print(node.val + " ");  // 输出当前节点的值
        inOrderTraversalRecursive(node.right);  // 再递归遍历右子树
    }

    public static void main(String[] args) {
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();

        bst.insert(50);
        bst.insert(30);
        bst.insert(20);
        bst.insert(40);
        bst.insert(70);
        bst.insert(60);
        bst.insert(80);
        bst.inOrderTraversal();  // 20 30 40 50 60 70 80

        System.out.println(bst.search(10));  // false
        System.out.println(bst.search(20));  // true

        bst.delete(50);
        bst.delete(20);
        bst.delete(30);
        bst.inOrderTraversal();  // 40 60 70 80
    }
}

注意代码中的 T extends Comparable<T> 这是表示强制泛型类型 T 实现比较逻辑，确保二叉搜索树的核心操作（插入、查找、删除）可以正确执行，因为 BST 中需要对值进行比较：val.compareTo(node.val)。

假设我们定义一个 Person 类，并尝试用 BinarySearchTree<Person> 存储，只要我们这个类是可比较的，那么就可以正常使用 BST：

class Person implements Comparable<Person> {
    String name;
    int age;

    @Override
    public int compareTo(Person other) {
        return this.age - other.age;  // 按年龄比较
    }
}

// 合法：Person 实现了 Comparable<Person> 接口，并重写了 compareTo 方法，具有合法的比较逻辑
BinarySearchTree<Person> bst = new BinarySearchTree<>();
bst.insert(new Person("Alice", 18));

3.4 二叉搜索树与集合

我们回顾一下集合的特性：

• 不允许重复元素。
• 支持高效插入、删除和查找操作。
• 可以有序（如 TreeSet）或无序（如 HashSet）。

这么一看我们的二叉搜索树是不是就是类似集合的数据结构？二叉搜索树确实可以用来实现集合，但它的应用不仅限于此。

利用 BST 的有序性和动态操作特性，可以实现一个有序集合。例如 Java 的 TreeSet 底层通过红黑树（一种平衡二叉搜索树）实现，保证了插入、删除、查找的时间复杂度为 $O(logn)$。

普通 BST 存在退化为链表的可能（例如从小到大插入元素），即时间复杂度退化为 $O(n)$，因此实际应用中通常使用平衡二叉搜索树（如 AVL 树、红黑树），这些数据结构在后面马上就会讲到。

以下是一些直接或间接基于 BST 的经典数据结构：