On Sat, May 08, 2004 at 03:18:46PM -0400, Dylan Thurston wrote:
On Sat, May 08, 2004 at 09:10:52PM +0200, Wolfgang Jeltsch wrote:
For what do we need a balanced tree? At least, O(1) concatenation and O(n) conversion to an ordinary list should also work with unbalanced trees.
You don't need a balanced tree, but the O(n) bound requires the invariant that no proper subtree is empty. Otherwise, a tree containing n elements can be of unbounded size, and take an unbounded time to convert to a list.
Yes, but DData.Seq is supposed to be a general-purpose library, and I, for one, want most operations (e.g., lookup) to be O(log n).
I suspect there is no satisfactory general-purpose sequence implementation (DData.Seq isn't trying to be one -- it does no balancing.) A balanced tree would make most things O(log n), but other implementations give you O(1) for various subsets of operations (and the smaller the subset, the smaller the constant factor, as a rule of thumb). It seems essential to offer a range of implementations.