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