Dynamic Weighted Data Structures.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1982
- Accession Number
- ADA122046
Entities
People
- Samuel Watkins Bent
Organizations
- Stanford University