home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / tree_col.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  2.8 KB  |  75 lines
  1. {\magonebf 3.11 Dynamic collections of trees  (tree\_collection) }
  2.  
  3. An instance $D$ of the data type $tree\_collection$ is a collection of 
  4. vertex disjoint rooted trees, each of whose vertices has a real-valued 
  5. cost and contains an information of type $I$, called the information type of
  6. $D$.
  7.  
  8. \bigskip
  9. {\bf 1. Declaration of a dynamic tree collection type}
  10.  
  11.  
  12. \decl tree\_collection I
  13.  
  14. introduces a new data type with name \name\ consisting of all dynamic
  15. tree collections with information type $I$.
  16.  
  17.  
  18.  
  19. \bigskip
  20. {\bf 2. Creation of a tree\_collection }
  21.  
  22. \create D {}
  23.  
  24. creates an instance \var\ of type \name, initialized with the empty collection.
  25.  
  26.  
  27.  
  28. \bigskip
  29. {\bf 3. \operations}
  30.  
  31. \medskip
  32. \+\cleartabs & \hskip 2truecm & \hskip 5truecm &\cr
  33. \+\op d\_vertex   maketree {I\ x}  
  34.                              {Adds a new tree to $D$ containing a single }
  35. \+\nop                       {vertex $v$ with cost zero and information $x$,}
  36. \+\nop                       {and returns $v$.} 
  37. \smallskip 
  38. \+\op I           inf {d\_vertex\ v} 
  39.                              {Returns the information of vertex $v$.}
  40. \smallskip
  41. \+\op d\_vertex   findroot {d\_vertex\ v} 
  42.                              {Returns the root of the tree containing $v$.}
  43. \smallskip
  44. \+\op d\_vertex   findcost {d\_vertex\ v,\ real\&\ x} {}
  45. \+\nop                       {Sets $x$ to the minimum cost of a vertex on the}
  46. \+\nop                       {tree path from $v$ to findroot($v$) and returns}
  47. \+\nop                       {the last vertex (closest to the root) on this }
  48. \+\nop                       {path of cost $x$.}
  49. \smallskip
  50. \+\op void        addcost {d\_vertex\ v,\ real\ x} {}
  51. \+\nop                       {Adds real number $x$ to the cost of every vertex}
  52. \+\nop                       {on the tree path from $v$ to findroot($v$)}.                                 
  53. \smallskip
  54. \+\op void        link {d\_vertex\ v,\ d\_vertex\ w} {}
  55. \+\nop                   {Combines the trees containing vertices $v$ and $w$}
  56. \+\nop                   {by adding the edge $(v,w)$. (We regard tree }
  57. \+\nop                   {edges as directed from child to parent.) }
  58. \+\nop                   {\precond $v$ and $w$ are in different trees }
  59. \+\nop                   {and $v$ is a root.}
  60. \smallskip
  61. \+\op void        cut {d\_vertex\ v}
  62.                             {Divides the tree containing vertex $v$ into}
  63. \+\nop                      {two trees by deleting the edge out of $v$.}
  64. \+\nop                      {\precond $v$ is not a tree root.}
  65.                                                                       
  66. \bigskip
  67. {\bf 4. Implementation}
  68.  
  69. Dynamic collections of trees are implemented by partitioning the trees
  70. into vertex disjoint paths and representing each path by a self-adjusting
  71. binary tree (see [T83]). All operations take amortized time $O(\log n)$
  72. where $n$ is the number of maketree operations.
  73.  
  74.  
  75.