⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 chapter1_3.htm

📁 介绍高级数据结构和算法的讲义
💻 HTM
字号:
🔍 
<html>
<!-- #BeginTemplate "/Templates/article_template.dwt" --> 
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="keywords" content="algorithm, data structure, contest, programming, 算法, 数据结构, 程序设计, 竞赛">
<meta name="description" content="discussing the algorithm and data structure of computer programming, as well as all kinds of programming contest.">
<meta name="description" content="讨论程序设计的算法与数据结构，各类程序设计竞赛试题解析和参赛经验介绍。">
<!-- #BeginEditable "doctitle" --> 
<title>算法与数据结构 -- 欧拉回路技术</title>
<!-- #EndEditable --> 
<script id="header" language="JavaScript" src="../../lib/header.js"></script>
<!-- #BeginEditable "javascript" --> 
<script language="JavaScript">
previous = "chapter1_2.htm";
next = "chapter2.htm";
contents="";
topic="并行算法——指针转移";
</script>
<!-- #EndEditable --> 
</head>
<body bgcolor="#FFFFFF">
<div id="content"> <!-- #BeginEditable "MainContent" --> 
  <h3>1.3 欧拉回路技术</h3>
  <p>在本节中，我们将介绍欧拉回路技术，并说明如何运用这一技术在n个结点的二叉树中计算出每个结点的深度。在这个O(lgn)时间的EREW算法中，关键的一步就是并行前缀计算。</p>
  <p>为了在PRAM中存储二叉树，我们采用了简单的二叉树表示法。每个结点i有三个域parent[i],left[i],right[i]，分别指向结点i的父母、左子女和右子女。假定每个结点用一个非负整数来表示。我们为每个结点联接三个而不是一个处理器，其原因我们在下面将会明白。称这三个处理器为结点的A，B和C处理器，我们可以很容易地在结点与其三个处理器之司找出对应关系。例如，结点i可以与处理器3i，3i+1和3i+2相联接。</p>
  <p>在串行RAM上，计算包含n个结点的树中每个结点的深度所需运行时间为O(n)。采用一种简单的并行算法来计算结点深度时，算法可以从树的根结点开始把一种“波”向下传输。这种波同时到达深度相同的所有结点，因此通过对波载计数器增值，我们就能计算出每个结点的深度。这种并行算法对完全二叉树很适用，这是因为其运行时间与树的高度成正此。而树的高度最大为n-1，这时算法的运行时间为O(n)，这并不优于串行算法。但是，如果我们运用欧拉回路技术，不论树的高度是多少，都能够在EREW 
    PRAM上用O(lgn)的运行时间计算出结点的深度。</p>
  <p>一个图的欧拉回路是通过图的每条边一次一个回路，当然，在此过程中它可以多次访问一个结点。根据图论算法可知，一个有向连通图具有欧拉回路当且仅当对所有结点v，v的出度等于v的入度。因为无向图每条无向边(u，v)对应于相应的有向图中的两条边(u，v)和(v，u)，因此任何无向连通图改成的有向图均包含欧拉回路，这对无向树也自然成立。</p>
  <p align="center"><img border="0" src="images/fig4a.gif" width="504" height="386"></p>
  <p align="center">(a)</p>
  <p align="center"><img border="0" src="images/fig4b.gif" width="504" height="386"></p>
  <p align="center">(b)<br>
  </p>
  <p align="center">图4 运用欧拉回路技术来计算每个结点在二叉树中的深度</p>
  <p>为了计算二叉树T中结点的深度，首先在改写的有向树T中形成一个欧拉回路。该回路对应于树的遍历过程，如图4(a)所示，它可以用一个连接树中所有结点的链表来表示。其结构如下：</p>
  <ul>
    <li>如果结点的左子女存在，则结点的A处理器指向其左子女的A处理器，否则就指向自身的B处理器。</li>
    <li>如果结点存在右子女，则结点的B处理器指向其右子女的A处理器，否则就指向其自身的C处理器。</li>
    <li>如果一个结点是其父母结点的左子女，则结点的C处理器指向其父母的B处理器，如果该结点是其父母结点的右子女，则结点的C处理器指向其父母的C处理器。根结点的C处理器指向NIL。</li>
  </ul>
  <p>因此，根据欧拉回路形成的链表的表头是根结点的A处理器，表尾是根节点的C处理器。如果已知构成原始树的指针，则我们可以在O(1)的时间内构造出欧拉回路。</p>
  <p>在我们获得表示T的欧拉回路的链表后，我们在每个A处理器中放入值1，在每个B处理器中放入值0，在每个C处理器中放入值-1，如图4(a)所示。然后如第1.2节中那样，我们运用满足结合律的普通加法来执行并行前缀计算。图4(b)说明了并行前缀计算的结果。</p>
  <p>我们说，在执行完并行前缀计算过程后，每个结点的深度值在结点的C处理器中。为什么呢？我们按以下要求把数放入A，B和C三个处理器中：访问子树的最后结果是把运行和加上0。每个结点i的A处理器对其左子女树的运行和加1，这表明i的左子女的深度比i的深度大1。B处理器对运行和没有影响，这是因为i的左子女的深度与其右子女的深度相等。C处理器使运行和减1，以便对i的父母结点来说，对以i为根结点的子树进行访问后运行和不会改变。</p>
  <p>我们可以在O(1)的时间内计算出表示欧拉回路的列表。列表中包含3n个对象，所以执行并行前缀计算过程仅需O(lgn)的运行时间。因此，计算所有结点深度所花费的全部运行时间为O(lgn)。又因为算法执行中不需要对有存储器执行并发存取操作，所以该算法是一个EREW算法。</p>
  <!-- #EndEditable --> </div>
<script src='../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate -->
</html>

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -