Biomedical Engineering Reference
In-Depth Information
0
0
3
1
N
up-sweep
4
3
4
1
N
Figure 4.5:
Example of the up-sweep for re-sorting a tree.
It is important that any operation on the tree ensures that after the op-
eration, the tree preserves its property that any parent node has a smaller
value of
φ
than either of its children. Occasionally, an operation on a par-
ticular node may mean that it is no longer correctly placed. This requires
the tree to be re-sorted to accommodate this modified node. Either an up-
sweep or a down-sweep process is required to restore the tree structure.
Suppose there is a single misplaced node,
N
. First, compare
N
with its
parent. If
N
is smaller than its parent, than an up-sweep is required. Other-
wise,
N
is compared with its children, and if
N
is larger than either child,
a down-sweep is used.
In the up-sweep, since
N
is smaller than its parent,
N
and its parent
are exchanged. This process continues, with
N
comparing with its parent,
until the parent is smaller or
N
has reached the top of the tree; see Fig. 4.5
for an illustration.
In the down-sweep, the node
N
is compared against its children. If
N
is smaller than either child, it is exchanged with the smaller of its two
children. Like the up-sweep, this process is repeated until
N
is smaller
than both of its children, or reaches the end of the tree. The down-sweep
is illustrated in Fig. 4.6.
0
0
3
1
down-sweep
N
4
4
1
2
2
5
5
3
N
45
45
Figure 4.6:
Example of the down-sweep for re-sorting a tree.
