| Categories and Subject Descriptors (2008) | |||||||||||||||
Abstract | |||||||||||||||
| The abstract data type one-sided flexible array, also called randomaccess list, supports look-up and update of elements and can grow and shrink at one end. We describe a purely functional implementation based on weight-balanced multiway trees that is both simple and versatile. A novel feature of the representation is that the running time of the operations can be tailored to one’s needs—even dynamically at array-creation time. In particular, one can trade the running time of look-up operations for the running time of update operations. For instance, if the multiway trees have a fixed degree, the operations take Θ(log n) time, where n is the size of the flexible array. If the degree doubles levelwise, look-up speeds up to Θ ( √ logn) while update slows down to Θ(2 √ logn). We show that different tree shapes can be conveniently modelled after mixedradix number systems. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||