Information Technology Reference
In-Depth Information
It is easy to update the values of
bw
and
tag
. But the pointers of the tree are more
complicated to handle and they can be divided into two cases: (1)
p
is the precursor
node of
p2
and when
p-> right == NULL
, it is indicated that
p
is the parent node of
p2
and
p2
is the right child of
p
; (2) when
p->right
!=
NULL
,
p2
is the leftmost node
of a subtree whose root is
p->right
.
4.3
Performance
There are still several performance issues in the resource clue tree. Firstly, there will be
more and more nodes over time and all nodes will expire. If the current time now is big
than the end time of a node, it will be meaningless. The expired nodes still occupy the
storage space and result in the waste of storage resources. We define the pruning func-
tion to solve this problem. The main idea for that algorithm is to find all of the expired
nodes periodically and remove them from the tree in order to eliminate redundancy and
save storage. The process of the pruning algorithm is shown in figure 5.
Fig. 4.
The algorithmic process to insert
the end time node
Fig. 5.
The process of the pruning algorithm
Frequent usage of the pruning function will degrade the overall performance of the
data structure because the function itself will also consume resources. Therefore, pe-
riodical pruning is reasonable. Experimental results show that the effect of the prun-
ing function is obvious. Each pruning can remove 10% to 20% of the nodes to make
the total number of nodes maintain a relatively stable level.
