Accession Number : ADA122046
Title : Dynamic Weighted Data Structures.
Descriptive Note : Doctoral thesis,
Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Bent,Samuel Watkins
Report Date : Jun 1982
Pagination or Media Count : 84
Abstract : This thesis discusses implementations of an abstract data structure called a 'dynamic dictionary'. Such a data structure stores a collection of items, each of which is equipped with a 'key' and a 'weight'. Among the operations we might wish to perform on such a collection are: (1) accessing an item, given its key; (2) inserting a new item; (3) deleting an item; (4) joining two collections into one; (5) splitting a collection into two; and (6) changing the weight of an item. Operations (b)-(f) provide the dynamic nature of the data structure. In addition, we want the implementation to respect the weights, so that accessing a heavy item is quicker than accessing a light one. In an optimal binary tree, the path length to an item of weight w in a collection of total weight, W is proportional to log(W/w). By relaxing the optimality constraint and considering different kinds of trees, it is possible to retain this logarithmic access time (with a larger constant factor), and simultaneously achieve similar logarithmic times for the dynamic operations. Two new data structures are proposed, 'biased 2-3 trees' and 'biased weight-balanced trees.' They achieve the logarithmic time bounds provided the cost is amortized over a sequence of operations. These data structures have applications to the network flow problem and to the design of self-organizing data structures.
Descriptors : *DATA MANAGEMENT , *INFORMATION SYSTEMS , *WEIGHTING FUNCTIONS , *DATA STORAGE SYSTEMS , *INDEXES , DATA BASES , THESES , DATA ACQUISITION , ACCESS TIME , LOGARITHM FUNCTIONS , DICTIONARIES , NETWORK FLOWS
Subject Categories : Information Science
Statistics and Probability
Distribution Statement : APPROVED FOR PUBLIC RELEASE