【6.2】树的链式存储结构

一、“子结点表”表示方法

list of children，就是图的邻接表。

二、静态“左孩子/右兄弟”表示法

在数组中存储的“子结点表”

三、动态表示法

每个结点分配可变的存储空间

• 子结点数目发生变化，需要重新分配存储空间

四、动态“左孩子/右兄弟”表示法

• 左孩子在树中是结点的最左子结点，右子结点是结点原来的右侧兄弟结点
• 根的右链就是森林中每棵树的根结点

动态二叉链表树的关键实现细节：

寻找当前结点的父结点：

删除以root为代表的森林的所有结点：

删除以subroot为根的子树：

思考:下面的算法是否能遍历森林?

思考:灵活应用遍历框架

思考:删除以subroot为根的子树

• 请注意待删除的子树是否为空、subroot有 无父指针等情况的判断。
• 考虑删除以后各项相关链接的修改顺序。

五、父指针表示法及其在并查集中的应用

5.1 父指针表示法

• 只需要知道父结点的应用
• 只需要保存一个指向其父结点的指针域，称为 父指针 (parent pointer)表示法
• 用数组存储树结点，同时在每个结点中附设一个指针指示其父结点的位置

5.2 父指针表示法:算法

查询结点的根:

• 从一个结点出发找出一条向上延伸到达根的祖先路径
• O(k)，k为树高

判断两个结点是否在同一棵树:

• 两个结点根结点相同，它们一定在同一棵树中
• 如果其根结点不同，那么两个结点就不在同一棵树中

5.3 并查集

并查集 是一种特殊的集合，由一些不相 交子集构成，合并查集的基本操作是:

• Find: 查询结点所在集合
• Union: 归并两个集合

并查集是重要的抽象数据类型 – 应用于求解等价类等等问题

5.4 等价关系

一个具有 n 个元素的集合 S，另有一个定义在集合 S 上 的 r 个关系的关系集合 R。x，y，z表示集合中的元素

若关系 R 是一个 等价关系，当且仅当如下条件为真时 成立:

• (a)对于所有的 x，有 (x，x)∈R(即关系是自反的)
• (b)当且仅当 (x，y)∈R 时 (y，x)∈R(即关系是对称的)
• (c)若 (x，y)∈R 且 (y，z)∈R，则有 (x，z)∈R(即关系是传递的)

如果(x，y)∈R，则元素x和y是等价的

5.5 等价类(equivalence classes)

等价类是指相互等价的元素所组成的最大集合。 所谓最大，就是指不存在类以外的元素，与类内 部的元素等价

由x∈S生成的一个R等价类

• R = {y| y∈S ∧ xRy}
• R将S划分成为r个不相交的划分S1，S2，…Sr，这些 集合的并为S

用树来表示等价类的并查：

• 用一棵树代表一个集合
• 集合用父结点代替
• 若两个结点在同一棵树中，则它们处于同一个集合
• 树的实现
• 存储在静态指针数组中
• 结点中仅需保存父指针信息

5.5 UNION/FIND算法示例(1)

5.5 UNION/FIND算法示例(2)

路径压缩：

• 查找X
• 设X最终到达根R
• 顺着由X到R的路径把每个结点的父指针域均设置为直接指向R
• 产生极浅树

5.5 UNION/FIND算法示例(3)

路径压缩

路径压缩使Find开销接近于常数:

• 权重 + 路径压缩
• 对n个结点进行n次Find操作的开销为O(nα(n))，约 为Θ(nlog*n)
• α(n)是单变量Ackermann函数的逆，它是一个增长速度比logn慢得 多但又不是常数的函数
• log*n 是在 n = logn ≤ 1 之前要进行的对 n 取对数操作的次数
• log*65536 = 4(4次log操作)
• Find至多需要一系列n个Find操作的开销非常接 近于Θ(n)
• 在实际应用中，α(n)往往小于4

思考

• 可否使用动态指针方式实现父指针表示 法?
• 查阅各种并查集权重和路径压缩优化方 法，并讨论各种方法的异同和优劣

。。

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾