利用欧拉回路计算每个结点的深度.doc

欧拉回路技术在本节中，我们将介绍欧拉回路技术，并说明如何运用这一技术在n个结点的二叉树中计算出每个结点的深度。在这个O(lgn)时间的EREW算法中，关键的一步就是并行前缀计算。为了在PRAM中存储二叉树，我们采用了简单的二叉树表示法。每个结点i有三个域parenti,lefti,righti，分别指向结点i的父母、左子女和右子女。假定每个结点用一个非负整数来表示。我们为每个结点联接三个而不是一个处理器，其原因我们在下面将会明白。称这三个处理器为结点的A，B和C处理器，我们可以很容易地在结点与其三个处理器之司找出对应关系。例如，结点i可以与处理器3i，3i+1和3i+2相联接。在串行RAM上，计算包含n个结点的树中每个结点的深度所需运行时间为O(n)。采用一种简单的并行算法来计算结点深度时，算法可以从树的根结点开始把一种“波”向下传输。这种波同时到达深度相同的所有结点，因此通过对波载计数器增值，我们就能计算出每个结点的深度。这种并行算法对完全二叉树很适用，这是因为其运行时间与树的高度成正此。而树的高度最大为n-1，这时算法的运行时间为O(n)，这并不优于串行算法。但是，如果我们运用欧拉回路技术，不论树的高度是多少，都能够在EREW PRAM上用O(lgn)的运行时间计算出结点的深度。一个图的欧拉回路是通过图的每条边一次一个回路，当然，在此过程中它可以多次访问一个结点。根据图论算法可知，一个有向连通图具有欧拉回路当且仅当对所有结点v，v的出度等于v的入度。因为无向图每条无向边(u，v)对应于相应的有向图中的两条边(u，v)和(v，u)，因此任何无向连通图改成的有向图均包含欧拉回路，这对无向树也自然成立。(a)(b)图4 运用欧拉回路技术来计算每个结点在二叉树中的深度为了计算二叉树T中结点的深度，首先在改写的有向树T中形成一个欧拉回路。该回路对应于树的遍历过程，如图4(a)所示，它可以用一个连接树中所有结点的链表来表示。其结构如下： 如果结点的左子女存在，则结点的A处理器指向其左子女的A处理器，否则就指向自身的B处理器。 如果结点存在右子女，则结点的B处理器指向其右子女的A处理器，否则就指向其自身的C处理器。 如果一个结点是其父母结点的左子女，则结点的C处理器指向其父母的B处理器，如果该结点是其父母结点的右子女，则结点的C处理器指向其父母的C处理器。根结点的C处理器指向NIL。 因此，根据欧拉回路形成的链表的表头是根结点的A处理器，表尾是根节点的C处理器。如果已知构成原始树的指针，则我们可以在O(1)的时间内构造出欧拉回路。在我们获得表示T的欧拉回路的链表后，我们在每个A处理器中放入值1，在每个B处理器中放入值0，在每个C处理器中放入值-1，如图4(a)所示。然后如第1.2节中那样，我们运用满足结合律的普通加法来执行并行前缀计算。图4(b)说明了并行前缀计算的结果。我们说，在执行完并行前缀计算过程后，每个结点的深度值在结点的C处理器中。为什么呢？我们按以下要求把数放入A，B和C三个处理器中：访问子树的最后结果是把运行和加上0。每个结点i的A处理器对其左子女树的运行和加1，这表明i的左子女的深度比i的深度大1。B处理器对运行和没有影响，这是因为i的左子女的深度与其右子女的深度相等。C处理器使运行和减1，以便对i的父母结点来说，对以i为根结点的子树进行访问后运行和不会改变。我们可以在O(1)的时间内计算出表示欧拉回路的列表。列表中包含3n个对象，所以执行并行前缀计算过程仅需O(lg