Information Technology Reference
In-Depth Information
Fig. 3.
An example of the resource clue tree
4.2
Algorithms of Request Processing
The Algorithm to Insert the Start Time Node.
The insertion of the start time node
p1
is similar to that of a binary search tree but it
has a higher efficiency for search. During the insertion process it needs to handle the
tag
and start pointer.The algorithm is as follows:
Inserts(p, req)
Input:
p
;
req
Explain:
pre
is the precursor of
p
if p == NULL //not exist
/*create new node 'p'*/
if pre != NULL
/*handle the pointers */
else
p->tag = start;
start = pre = p;
end if
else if req.ts == p->ts
pre = p;
end if
else if req.ts< p->ts
p->left = insertts(p->left, req);
else
pre = p;
p->right = insertts(p->right, req);
end if
end if
return p;
The Algorithm to Insert the End Time Node.
The insertion of the end node
p2
makes use of the high traversal efficiency of the
linked list. It traverses in the list order from
p1
to
p2
and deals with the values of
bw
.
This process needs to correctly handle the pointers. The algorithm is shown in figure 4.