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