l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.1.0/docs/html/ext/pb_assoc/node_invariants.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
   2 <html>
   3         <head>
   4                 <title>Node Invariants</title>
   5                 <meta name="GENERATOR" content="Microsoft Visual Studio .NET 7.1">
   6                 <meta name="vs_targetSchema" content="http://schemas.microsoft.com/intellisense/ie5">
   7         </head>
   8 <body bgcolor = "white">
   9 <h1>Node Invariants</h1>
  10
  11 <p>
  12         Figure
  13 <a href = "#node_invariants">Some node invariants</a>
  14 shows some node invariants. A shows
  15 a tree whose each node contains, asides from an <tt>double</tt> key, the number
  16 of nodes at the subtree rooted at the node; B shows a tree whose each node
  17 contains, asides from a line-interval key, the maximal endpoint of the interval
  18 of any node in the subtree rooted at the node.
  19         The first tree allows querying efficiently what is the order statistic
  20 of any element; the second tree allows querying efficiently if any, or which,
  21 intervals overlap a given interval.
  22 </p>
  23
  24 <h6 align = "center">
  25 <a name = "node_invariants">
  26 <img src = "node_invariants.jpg" width = "50%" alt = "no image">
  27 </a>
  28 </h6>
  29 <h6 align = "center">
  30 Some node invariants.
  31 </h6>
  32
  33
  34 <p>
  35         Maintaining such trees is difficult, for two reasons:
  36 </p>
  37 <ol>
  38         <li> Various operations can invalidate node invariants.
  39 <i>E.g.</i>, Figure
  40 <a href = "#node_invariant_invalidations">Invalidation of node invariants</a>
  41 shows how a right rotation, performed on A, results in B, with nodes <i>x</i>
  42 and <i>y</i> having corrupted invariants (the greyed nodes in C);
  43 Figure
  44 <a href = "#node_invariant_invalidations">Invalidation of node invariants</a>
  45 shows how an insert, performed on D, results in E, with nodes <i>x</i>
  46 and <i>y</i> having corrupted invariants (the greyed nodes in F).
  47         It is not feasible to know outside the tree the effect of an operation on the
  48 nodes of the tree.
  49         </li>
  50         <li>
  51                 Even if node invariants are maintained, it is not possible to know
  52 in advance which search paths are required (<i>e.g.</i>, searching for all
  53 line intervals overlapping some interval might require several search paths).
  54         </li>
  55 </ol>
  56
  57
  58 <h6 align = "center">
  59 <a name = "node_invariant_invalidations">
  60 <img src = "node_invariant_invalidations.jpg" width = "80%" alt = "no image">
  61 </a>
  62 </h6>
  63 <h6 align = "center">
  64 Invalidation of node invariants.
  65 </h6>
  66
  67 <p>
  68         These problems are solved by a combination of two means:
  69 </p>
  70
  71 <ol>
  72         <li>
  73                 The tree-based containers are parameterized by a <tt>Node_Updator</tt>
  74 parameter. When a tree operation might invalidate some node invariant,
  75 a <tt>Node_Updator</tt> object is invoked to restore the invariant. This object is
  76 always invoked with three nodes: some node, say <i>x</i> in
  77 Figure
  78 <a href = "#restoring_node_invariants">Invalidation of node invariants</a>-A
  79 has an invalid invariant, but its children, <i>y</i> and <i>z</i> hav valid invariants.
  80 After the invocation, all three nodes have valid invariants, as
  81 in
  82 Figure
  83 <a href = "#restoring_node_invariants">Invalidation of node invariants</a>-B.
  84 It is well known that any <tt>insert</tt>, <tt>erase</tt>,
  85 <tt>split</tt> or <tt>join</tt>, can restore
  86 all node invariants by a small number of node invariant updates
  87 [<a href = "references.html#clrs2001">clrs2001</a>].
  88 For example, Figure
  89 <a href = "#update_seq_diagram">
  90 Insert update sequence diagram
  91 </a>
  92 shows an <tt>insert</tt> operation (point A); the tree performs some operations, and
  93 calls the update functor three times (points B, C, and D).
  94         </li>
  95         <li>
  96                 The tree based containers all define internally <tt>node_iterator</tt>
  97         and <tt>const_node_iterator</tt>, iterators which can be used to traverse
  98         from a node to any of its children or parent.
  99         </li>
 100 </ol>
 101
 102 <h6 align = "center">
 103 <a name = "restoring_node_invariants">
 104 <img src = "restoring_node_invariants.jpg" width = "80%" alt = "no image">
 105 </a>
 106 </h6>
 107 <h6 align = "center">
 108 Invalidation of node invariants.
 109 </h6>
 110
 111 <h6 align = "center">
 112 <a name = "update_seq_diagram">
 113 <img src = "update_seq_diagram.jpg" width = "50%" alt = "no image">
 114 </a>
 115 </h6>
 116 <h6 align = "center">
 117 Insert update sequence diagram.
 118 </h6>
 119
 120
 121 <p>
 122         In
 123 <a href = "concepts.html#concepts_null_policies">Null Policy Classes</a>
 124 a distinction was made between <i>redundant policies</i>
 125 and <i>null policies</i>.
 126 </p>
 127
 128 <p>
 129         Seemingly, in this case a redundant policy - a policy which doesn't
 130 affect nodes' contents would suffice in this case. This, however, would
 131 lead to performance loss.
 132 Figure
 133 <a href = "#rationale_null_node_updator">
 134 Rationale for null node-invariant functors
 135 </a>
 136 shows a typical case where invariants are restored (in this case, to the
 137 shaded node). In most cases, tree operations such as rotations affect only
 138 the lower levels of the tree. A null policy allows to know that there
 139 is no need to traverse the tree to the root.
 140 </p>
 141
 142 <h6 align = "center">
 143 <a name = "rationale_null_node_updator">
 144 <img src = "rationale_null_node_updator.jpg" width = "50%" alt = "no image">
 145 </a>
 146 </h6>
 147 <h6 align = "center">
 148 Rationale for null node-invariant functors.
 149 </h6>
 150
 151
 152 </body>
 153
 154 </html>