第 10 章抽象数据类型与树¶

原作：Josh Hug，UC Berkeley CS61B Spring 2021 配套读本。
中文翻译版，仅供非商业学习；采用 CC BY-NC-SA 4.0 许可。
原始网站：https://joshhug.gitbooks.io/hug61b/content/

10.1 ADT 入门¶

抽象数据类型（ADT）只由它支持的操作定义，而不由具体实现定义。

例如，项目 1A 中的 ArrayDeque 和 LinkedListDeque 提供相同方法，但内部代码完全不同。它们都是 Deque ADT 的实现。

ADT 与接口密切相关：

从概念上，Deque 是一组行为规范；
在 Java 代码中，可以用 Deque 接口表达该规范；
ArrayDeque 和 LinkedListDeque 实现这个接口。

常见 ADT：

栈（Stack）：后进先出；
push(x)：把 x 放到栈顶；
pop()：取出栈顶元素。
列表（List）：有顺序的元素集合；
add(i)：添加元素；
get(i)：获得索引 i 的元素。
集合（Set）：无序且元素唯一；
add(i)：添加元素；
contains(i)：判断是否包含某值。
映射（Map）：键值对集合；
put(key, value)：加入或更新键值对；
get(key)：获得键对应的值。

List、Set 等接口位于更大的集合框架中。下图白色为接口，蓝色为具体类：

ADT 让面向对象编程更灵活、更优雅。项目 1B 中，OffByOne 与 OffByN 可以互换，是因为它们实现同一接口。同理，调用者可以在不改变主要代码的情况下，在 ArrayDeque 与 LinkedListDeque 之间切换。

后续章节将定义更多 ADT，并比较它们的不同实现。

10.2 树¶

下面学习计算机科学中最重要的数据结构之一：树。

链表很好用，但即使链表有序，查找元素仍可能很慢。若元素在末尾，就需要线性时间。

有序数组可以使用二分查找，在 Θ(log N) 时间内寻找元素。但链表无法常数时间访问中间位置，为了找到中间结点，本身就要线性遍历。

一种改进是保存指向中间结点的引用，并允许向左右两个方向移动：

还可以继续为每个左右部分保存中点引用：

把结构纵向展开，就得到一棵树：

该结构称为二叉树，因为每个分支点最多分成两个方向。

树的性质¶

树由以下部分构成：

结点；
连接结点的边；
任意两个结点之间只有一条简单路径。

在有根树中，我们指定一个没有父结点的根。没有子结点的结点称为叶子。

下面都是合法的树：

练习 10.2.1。 给出一个不是树的结构。提示：可以让它出现环，或让两个结点之间存在多条路径。

在一般树的约束上继续增加条件，就得到更具体的类型：

二叉树：每个结点有 0、1 或 2 个子结点；
二叉搜索树（BST）：对每个结点 X：
左子树中的每个键都小于 X.key；
右子树中的每个键都大于 X.key。

这个 BST 性质非常重要，后续会反复使用。

一个简化的 BST 结点类：

private class BST<Key> {
    private Key key;
    private BST<Key> left;
    private BST<Key> right;

    public BST(Key key, BST<Key> left, BST<Key> right) {
        this.key = key;
        this.left = left;
        this.right = right;
    }

    public BST(Key key) {
        this.key = key;
    }
}

二叉搜索树操作¶

查找¶

BST 性质让查找过程类似二分查找：

从根开始比较目标 X；
若 X 小于当前键，进入左子树；
若 X 大于当前键，进入右子树；
若相等，找到目标；若走到 null，说明不存在。

练习 10.2.2。 实现：

static BST find(BST T, Key key)

一种递归写法：

static BST find(BST T, Key sk) {
    if (T == null) {
        return null;
    }
    if (sk.equals(T.key)) {
        return T;
    } else if (sk.compareTo(T.key) < 0) {
        return find(T.left, sk);
    } else {
        return find(T.right, sk);
    }
}

若树比较平衡，高度为 Θ(log N)，查找也只需对数时间。

插入¶

新键总是被插入到叶子位置。

先按查找路径向下走：

若已经存在，通常不做任何事；
若走到 null，就在该位置创建新结点，从而保持 BST 性质。

static BST insert(BST T, Key ik) {
    if (T == null) {
        return new BST(ik);
    }
    if (ik.compareTo(T.key) < 0) {
        T.left = insert(T.left, ik);
    } else if (ik.compareTo(T.key) > 0) {
        T.right = insert(T.right, ik);
    }
    return T;
}

练习 10.2.3。 想出不同插入顺序，使同一批键形成高度不同的树。极端情况下：

合理顺序可以形成近似平衡树，高度 Θ(log N)；
按严格升序或降序插入可能形成链，高度 Θ(N)。

删除¶

删除后必须重建连接，并保持 BST 性质。分三种情况。

没有子结点¶

目标是叶子。把父结点中指向它的引用设为 null，之后垃圾回收器会回收该结点。

只有一个子结点¶

让父结点直接指向目标的唯一子结点。由于 BST 性质对子树递归成立，这不会破坏顺序。

有两个子结点¶

不能随便选择一个子结点替换，否则可能破坏 BST 性质。替代结点必须：

大于左子树中的所有键；
小于右子树中的所有键。

满足条件的典型选择：

左子树中最右侧、也就是最大的结点；
右子树中最左侧、也就是最小的结点。

用选中的前驱或后继替换目标，再删除它原来的结点。该方法称为 Hibbard 删除。

用 BST 实现 Set 与 Map¶

BST 可以实现 Set ADT。数组集合的 contains 最坏需要扫描全部元素，是 Θ(N)；平衡 BST 能利用有序性质，把查找降到 Θ(log N)。

也可以让每个 BST 结点保存 (key, value)，从而实现 Map。树结构的位置由键决定，值作为对应数据一同保存。

总结¶

ADT 由操作定义，而不是由实现定义；
常见 ADT 包括并查集、映射、集合与列表；
Java 提供 Map、Set、List 接口及多种实现；
集合或映射可以用数组实现，最坏操作 Θ(N)；
平衡 BST 的查找和插入为 Θ(log N)；
BST 查找与插入较直接；删除更复杂，常用 Hibbard 删除。

后续练习：

第 10 章 抽象数据类型与树¶