[Haskell-cafe] Red-Blue Stack
tom.davie at gmail.com
Sat Sep 27 09:44:18 EDT 2008
> Thomas Davie wrote:
>> In this interprettation, here's what I think is an O(1)
>> rbPop :: Colour -> RBStack a -> RBStack a
>> rbPop c Empty = error "Empty Stack, can't pop"
>> rbPop c (More c' v asCs nextNonC)
>> | c == c' = asCs
>> | otherwise = rbPop c nextNonC
> Your pop doesn't seem to be in O(1) since you have to walk through
> the nextNonC stack if the colours don't match.
Yep, this is still O(1) though, as you can guarentee that nextNonC
will start with something of the correct colour. Thus the worst case
here is that we walk once to the nextNonC element, and then do a
different O(1) operation.
More information about the Haskell-Cafe