Information Technology Reference
In-Depth Information
5
Resource Binary Tree
5.1
Introduction
The definition of the resource binary tree is similar to that of the resource clue tree. In
a resource binary tree, each node stores the allocated values of
bw
within a time pe-
riod (
l
,
r
). There is only a root node root (0, 0, +∞,
NULL
,
NULL)
in the initial tree.
The definition of a tree node is shown as follows:
structtreenode
{
intbw; // the value of resources(bandwidth)
int l; //start time
int r; //end time
structtreenode* left;
structtreenode* right;
};
In the implementation process of the resource binary tree, the left pointer of a
node(
left
) points to its first child and the right pointer(
right)
points to its next brother.
When reservation requests arrive, the valid node meeting the conditions splits into
new valid nodes and the original node will be invalid.
There are two types of nodes in the resource binary tree—valid nodes and invalid
nodes. When
p->left==NULL
, p is a valid node, or else, it is an invalid node and has no
relation with the value of
p->right
. Only the useful information of reservation stored in
valid nodes is useful while invalid nodes only have the function of index and judgment.
5.2
Algorithms of Request Processing
Fig. 6.
Three methods of splitting
