[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]

high-arity splay trees?

While thinking about the new region splay algorithm, I noticed that it
can generalize to high-arity trees (presumably so can other splay
algorithms, but the particular phrasing of the algorithm made it more
observable).  Right now it returns the number of children that are
completely contained within a region.  If there are more than two
children, this number can simply be larger.  We'd want a special case
to represent all children (with 0 for no children).  I believe the
extension is straightforward.  

The rotate operations would need to be more clever to keep the arity
up, and the optimizations I suggested in a previous message would be
more difficult.  I wonder what the performance tradeoffs look like....