Information Technology Reference
In-Depth Information
worse than the timeslot array both in the consumption of time and storage space. Olov
et al. propose a binary search tree, but the experimental results also show the perfor-
mance of this data structure is worse than the segment tree [10]. QingXiong et al. pro-
posea data structure based on the single linked list and the experimental results show
that the storage consumption of the single linked list is far less than that in the timeslot
array[9]. If the amount of requests is not large, the time consumption of the single
linked list will be better [11-13]. The single linked list is optimized and improved to
increase the processing and search speed with slightly higher cost of storage space
[14-17].
In summary, the timeslot array has certain advantages in performance as a classical
data structure whereas the performance of non-slotted data structures (the bandwidth
tree, the binary search tree) is not satisfactory [18-22]. The description, processing and
store performance of several data structures will be analyzed and compared with the
timeslot array by experiments later.
4
Resource Clue Tree
4.1
Introduction
A resource clue tree is a data structure combining the binary search tree and the linked
list, in which the list pointers ( tag ) link the nodes in sequence. In this way, it can
combine the fast search speed of the binary search tree with the efficient traversal of
the linked list to avoid recursion and improve the performance. A simple resource
clue tree is shown as figure 3.
In Figure 3, the solid line pointers represent for the pointers of the tree (left and
right) and the dashed pointers for the pointers of the list ( tag ). The pointer root and
start stand for the root of the tree and the head node of the list, respectively. The node
is defined as follows:
struct node
{
intbw; //the value of resources(bandwidth)
intts; //start time
struct node* tag;
struct node* left;
struct node* right;
};
The tree is built according to the values of the key word ts . Any node p stores the
value of bw during a period of time ( p . ts , p -> tag . ts ). During this period, bw is a con-
stant and the values of the adjacent nodes are different. The start time of the next node
in list order ( p -> tag ) represents for the end time of p in order to save storage space.
The value of bw in the last node is 0 and identifying the end time of the previous node.
Search WWH ::




Custom Search