A value-bearing perfect binary tree has size , and the next size is . Suppose two size- trees have at least one smaller tree before them. The portion represented by these trees and that nonempty preceding portion has at least elements. The greedy choice would have used a larger perfect binary tree instead, contradicting the specified representation. Three size- trees are likewise impossible, since . Therefore the only possible repeated size is a pair at the beginning. This is the representation invariant of a skew-binary random-access list.
A Haskell representation is:Every tree stores a value at its root, including internal nodes. Interpret the forest by root-left-right preorder traversal, concatenating the results in forest order. Valid values have correct cached sizes, perfect binary trees, nondecreasing sizes and only the permitted initial duplicate. The raw constructors can express invalid representations, so the operations below assume valid values and should form the public interface. Sizes are assumed to fit in
import Prelude hiding (null, head, tail)
data RTree a = Leaf a | Node a (RTree a) (RTree a)
newtype List a = List [(Int, RTree a)]Int; the stated time complexities use constant-time size arithmetic.The empty skew-binary random-access list contains no trees:Both construction of
nil :: List a
nil = List []
null :: List a -> Bool
null (List []) = True
null _ = Falsenil and testing null take constant time.Only the first two trees need inspection:When the first sizes agree, place
cons :: a -> List a -> List a
cons x (List ((w,t):(v,u):ts))
| w == v = List ((2*w+1, Node x t u):ts)
cons x (List ts) = List ((1, Leaf x):ts)x above those two perfect binary trees. Its preorder traversal is x followed by the old two traversals. No further size- tree can occur, so all remaining sizes are at least ; equality creates at most the allowed initial duplicate. When the first sizes differ, adjoining a singleton is valid, including the case that the old first tree is also a singleton. These are exactly the two possible greedy representations after increasing the length by one. Each case creates a bounded number of constructors and inspects no tree interior, giving worst-case time complexity. Existing trees are shared.Repeated constant time insertion constructs the representation:The right fold preserves order because
fromList :: [a] -> List a
fromList = foldr cons nilcons prepends its argument. On a finite length- list, there are calls of cons; completely constructing the result takes time and constructors. This claim concerns finite inputs, not productivity of conversion from an infinite lazy list.The first tree's root is the first element. Deleting that root either discards a singleton or exposes two equal-sized child trees:For a node of size , both children have size . Their order agrees with the old preorder traversal, and they become the sole permitted initial duplicate. The rest of the forest was no smaller than the old root tree. Thus both operations preserve the representation invariant and take worst-case time on a nonempty skew-binary random-access list.
head :: List a -> a
head (List ((_,Leaf x):_)) = x
head (List ((_,Node x _ _):_)) = x
head (List []) = error "head: empty list"
tail :: List a -> List a
tail (List ((_,Leaf _):ts)) = List ts
tail (List ((w,Node _ l r):ts)) =
let h = w `div` 2 in List ((h,l):(h,r):ts)
tail (List []) = error "tail: empty list"Repeated root removal gives the conventional list:The representation interpretation satisfies
toList :: List a -> [a]
toList rs
| null rs = []
| otherwise = head rs : toList (tail rs)toList (cons x rs) = x : toList rs; alternatively, structural induction on the number of stored elements proves that each step emits exactly the next preorder traversal value. The output has cons cells, and each step takes constant time, so fully consuming it costs time. No repeated list concatenation is needed.Skip whole trees using their cached sizes, then descend through one tree:After skipping a size- tree, the desired index decreases by . Inside a node, position zero is the root, positions belong to the left child and the following positions to the right child. This proves correctness by structural induction on the search.
index :: List a -> Int -> a
index (List ts) i
| i < 0 = error "index: negative index"
| otherwise = seek ts i
where
seek [] _ = error "index: out of bounds"
seek ((w,t):us) j
| j < w = at w t j
| otherwise = seek us (j-w)
at _ (Leaf x) 0 = x
at w (Node x l r) j
| j == 0 = x
| j <= h = at h l (j-1)
| otherwise = at h r (j-1-h)
where h = w `div` 2
at _ _ _ = error "index: invalid representation"There are at most forest entries by the supplied bound, and each tree has logarithmic height. Consequently a valid query takes time, with logarithmic worst cases. On a conventional linked list,
xs !! i follows links and costs , hence in the worst case. The first element remains a constant time query in either representation. Articles by others on the same topic
There are currently no matching articles.