树结构在程序设计中的运用讲解.ppt

树结构在程序设计中的运用 复旦大学附中 周文超 树结构在程序设计中的运用 引言 一．并查集 二．线段树 三．树状数组 小结 引言 近年来，由于各种竞赛纷纷采用free-pascal，因此对于算法来说，空间效率上的要求降低了，而对时间效率却提出了更高的要求。这使得选手不仅要娴熟地掌握常规算法，而且要大胆创新，构造更高效的算法来解决问题。 在以往的程序设计中，链式结构采用得较多。的确链式结构有编程复杂度低、简单易懂等优点，但有一个致命的弱点：相邻的两个元素间的联系并不明显。而树结构却能很好的做到这一点。 返回 并查集 竞赛中会经常遇到这样的题目：给出各个元素之间的联系，要求将这些元素分成几个集合，每个集合中的元素直接或间接有联系。在这类问题中主要涉及的是对集合的合并和查找，因此将这种集合称为并查集。 链结构的并查集 树结构的并查集 链结构的并查集 链表被普通用来计算并查集：表中的每个元素设两个指针：一个指向同一集合中的下一个元素；另一个指向表首元素。采用链式存储结构，在进行集合的查找时的算法复杂度仅为O（1）；但合并集合时的算法复杂度却达到了O（n）。如果我们希望两种基本操作的时间效率都比较高的话，链式存储方式就“力不从心”了。 返回 树结构的并查集 采用树结构支持并查集的计算能够满足我们的要求。并查集与一般的树结构不同，每个顶点纪录的不是它的子结点，而是将它的父结点记录下来。下面我介绍一下树结构的并查集的两种运算方式 ⑴直接在树中查询 ⑵边查询边“路径压缩” 直接在树中查询 集合的合并算法很简单，只要将两棵树的根结点相连即可，这步操作只要O（1）时间复杂度。所以算法的时间效率取决于集合查找的快慢。而集合的查找效率与树的深度呈线性关系。因此直接查询所需要的时间复杂度平均为O（logN）。但在最坏情况下，树退化成为一条链，使得每一次查询的算法复杂度为O（N）。 边查询边“路径压缩” 其实，我们还能将集合查找的算法复杂度进一步降低：采用“路径压缩”算法。它的想法很简单：在集合的查找过程中顺便将树的深度降低。采用路径压缩后，每一次查询所用的时间复杂度为增长极为缓慢的ackerman函数的反函数——α（x）。对于可以想象到的n，α（n）都是在5之内的。 线段树 处理涉及到图形的面积、周长等问题的时候，并不需要依赖很深的数学知识，但要提高处理此类问题的效率却又十分困难。这就需要从根本上改变算法的基础——数据结构。这里要说的就是一种特殊的数据结构——线段树。 先看一道较基础的题目：给出区间上的n条线段，判断这些线段覆盖到的区间大小。通过这题我们来逐步认识线段树。 线段树的定义 在线段树中加入和删除线段 计算测度和连续线段数 返回 线段树的定义 线段树是一棵二叉树，将一个区间划分为一个个[i，i+1]的单元区间，每个单元区间对应线段树中的一个叶子结点。每个结点用一个变量count来记录覆盖该结点的线段条数。 在线段树中插入和删除线段 在线段树中插入和删除线段的方法类似，都采用递归逐层向两个子结点扫描，直到线段能够盖满结点表示的整个区间为止。 计算测度和连续线段数 结点的测度m指的是结点所表示区间中线段覆盖过的长度。 计算测度和连续线段数 连续线段数line指的是区间中互不相交的线段条数。 计算测度和连续线段数 line可以根据lbd，rbd定义如下： 1 (count 0) 0 (count=0 且结点为叶结点) Line= lch^.Line + rch^.Line - 1 (count=0 且结点为内部结点， lch^．rbd、rch^．lbd都为1) lch^.Line + rch^.Line (count=0且结点为内部结点， lch^．rbd,rch^．Lbd不同时为1) 树状数组 IOI2001中的MOBILE难倒了很多选手。虽然该题的题意十分简单：在一个矩阵中，通过更新元素值修改矩阵状态，并计算某子矩阵的数字和，但难点在于数据的规模极大。下面，我来介绍一种新的数据结构—树状数组。 1、建立树状数组C 2、更新元素值 3、子序列求和 建立树状数组C 先将问题简化，考察一维子序列求和的算法。设该序列为a[1]，a[2]……a[n] 算法1：直接在原序列中计算。显然更新元素值的时间复杂度为O(1)；在最坏情况下，子序列求和的时间复杂度为Ｏ(n)。 算法三：增加数组C，其中C[i]=a[i-2k+1]+……+a[i]