数据结构chapter树与二叉树等价问题.ppt

森林法改进2的算法分析 操作　 Find Union 时间效率 O(log2+m/nn) O(1) 操作执行次数 m n-1 　将所有元素合并到一个集合：O(n+mlog2+m/nn) Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 森林法改进1+改进2的算法分析 操作　 Find Union 时间效率 O(l) O(1) 操作执行次数 m n-1 　将所有元素合并到一个集合：O(m+n) Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 作业11 算法设计题 1、实现FindPathCompress（）函数功能，该函数在查找的同时实现路径压缩，将深层结点移近根结点。 2、实现UnionRank（）函数功能，该函数实现按秩进行合并的算法，其中的查找操作调用第一步的函数。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 离散数学 等价关系 　　设mathR/math是集合mathA/math上的一个二元关系，若mathR/math满足： 　　自反性：math\forall x \in A,~~(x, x) \in R/math 　　对称性：math\forall x, y \in A,~~(x, y) \in R ~~ \implies ~~(y, x) \in R/math 　　传递性：math\forall x, y, z \in A, Luruiqi((x, y) \in R \wedge (y, z) \in R)~~\implies~~(x, z) \in R/math 　　则称mathR/math是定义在mathA/math上的一个等价关系。设R是一个等价关系，若x,y∈R，则称x等价于y，记作x~y。 　　例如，设mathA = \{1, 2, \ldots, 8\}/math，定义mathA/math上的关系mathR/math如下： 　　math 　　R = \{ (x, y) | x, y \in A \wedge x \equiv y (\mod~3) \} 　　/math 　　其中mathx \equiv y (\mod~3)/math 叫做 mathx/math 与 mathy/math 模 3 同余，即 mathx/math 除以 3 的余数与mathy/math 除以 3 的余数相等。不难验证 mathR/math 为 mathA/math 上的等价关系。 　　设f是从A到B的一个函数，定义A上的关系R：aRb,当且仅当f(a)=f(b),R是A上的等价关系。 集合中的数据元素除了“同属于一个集合的关系”之外别无其它关系 集合的实现方法有位向量表示法、有序表表示法、树型结构表示法等。 * 离散数学 等价关系 　　设mathR/math是集合mathA/math上的一个二元关系，若mathR/math满足： 　　自反性：math\forall x \in A,~~(x, x) \in R/math 　　对称性：math\forall x, y \in A,~~(x, y) \in R ~~ \implies ~~(y, x) \in R/math 　　传递性：math\forall x, y, z \in A, Luruiqi((x, y) \in R \wedge (y, z) \in R)~~\implies~~(x, z) \in R/math 　　则称mathR/math是定义在mathA/math上的一个等价关系。设R是一个等价关系，若x,y∈R，则称x等价于y，记作x~y。 　　例如，设mathA = \{1, 2, \ldots, 8\}/math，定义mathA/math上的关系mathR/math如下： 　　math 　　R = \{ (x, y) | x, y \in A \wedge x \equiv y (\mod~3) \} 　　/math 　　其中mathx \equiv y (\mod~3)/math 叫做 mathx/math 与 mathy/math 模 3 同余，即 math