Bootstrapping One-sided Flexible Arrays

Ralf Hinze
Rheinische Friedrich-Wilhelms-Universität Bonn

The abstract data type one-sided flexible array, also called random-access list, supports look-up and update of elements and can grow and shrink at one end. We describe an 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 run-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 O(log n) amortized time, where `n' is the size of the flexible array. However, if the degree doubles levelwise, look-up speeds up to O(sqrt (log n)) while update slows down to O(2^sqrt(log n)). The different tree shapes can be conveniently modelled after mixed-radix number systems.