= Skew-binary random-access list
Represent a finite <list> by a <forest> of value-bearing <perfect binary trees> of sizes $1,3,7,\ldots$, in nondecreasing order, using the greedy largest sizes and allowing a repeated size only in the first two positions. Concatenated <preorder traversals> recover the <list>. Cached tree sizes guide indexing.
Front insertion merges the first two equal-size trees beneath a new root, or adds a singleton if they differ. Removing the first root either discards a singleton or splits its two children into the initial equal-size pair. Both operations inspect and allocate only a bounded number of constructors, taking worst-case <constant time> and sharing the remaining representation. A positional query skips whole cached tree sizes and then descends through one tree, taking $O(\log(n+1))$ time. Conversion in either direction takes <linear time> on finite input.
The duplicate-size restriction follows directly from greediness. If two size-$w$ trees had any preceding nonempty portion, there would be at least $2w+1$ elements available, enough for the next larger <perfect binary tree>. Three equal-size trees would likewise suffice for that larger tree. Both contradict the greedy representation.
Back to article page
