【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(即关系是对称的)
  • ©若 (x,y)∈R 且 (y,z)∈R,则有 (x,z)∈R(即关系是传递的)

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

5.5 等价类(equivalence classes)

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

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

  • [x]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

思考

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

。。

参考资料

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

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学