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

*To*: <dean>, <markm>*Subject*: Region splay*From*: Ravi Pandya <ravi>*Date*: Thu, 1 Feb 90 11:11:34 PST*Cc*: <xtech>

I ran into a bug in the splay algorithm last night. Because the grouping was hidden inside the rotate operations, I thought the problem was more fundamental than it was, so I rewrote the splay algorithm to maintain grouping between splays of the left and right ends of a region. In designing the algorithm, I had made the simplifying assumption that we had fully ordered spaces, and that the tree was kept in ordered form (left < right). It turns out that the algorithm doesn't require full ordering if proper grouping is built into the rotate operations. My algorithm is much simpler than the old algorithm, mostly because the (later unnecessary) ordering assumption caused me to take a different perspective on the problem. >From this perspective, it looked like it ought to be possible to do a Status: RO region splay algorithm, and I couldn't fall asleep last night until I'd worked out the details. A simple extension of the new algorithm gives a region splay with the following properties: - isolates the region in its own subtree and brings it to the top - groups the tree according to the kind of regions it gets as requests (hence does not require any external grouping heuristic) - does extra search only if the requests (hence grouping) don't correspond well to the simple regions in the space - works fine in the presence of overlapping subtree regions, but it may do some extra searching The algorithm is: SplayEntLoaf >> {IntegerVar} splay: region {Region} "Ensure that each of my children is either all in or all out of the region. Return 0, 1, or 2 according to the number of my children that are in the region. If 1, then the left child is in the region, and the right child outside." Inner loaf: "optimization: use external regions to avoid splaying children if possible" left := myLeftOCrum splay: left transformed region. right := myRightOCrum splay: right transformed region. Rearrange the subtree according to the following table: left right rearrange subtree from -> to return ------ ------ -------------------------------------- ------ 0 0 no change 0 0 1 (A (B* C)) -> (B* (A C)) 1 0 2 (A B*) -> (B* A) 1 1 0 ((A* B) C) -> (A* (B C)) 1 1 1 ((A* B) (C* D)) -> ((A* C*) (B D)) 1 1 2 ((A* B) C*) -> ((A* C*) B) 1 2 0 no change 1 2 1 (A* (B* C)) -> ((A* B*) C) 1 2 2 no change 2 * indicates a subtree that is all in the region, as opposed to one that is all outside the region (one or the other is guaranteed, because the children have already been splayed) Virtual and partial loaves need to replace themselves with an actual subtree in which the leaves are all in or all out of the region, and return the result from splaying it. Enforcing that left is inside and right is outside rather than vice versa is not necessary, but it simplifies the book-keeping, which is complicated enough already. It's sufficiently complicated that I don't see any need to implement the algorithm right away, but it's nice to know it'll be there when we need it. --ravi P.S. Dean: the algorithm you posted will work fine for the multi-dimensional case, but not for a region splay of, say, every fifth element, where the grouping algorithm has no way to know how to keep things in the region together across distinction splays. For arbitrary regions, you really need to do the splay all at once.

- Prev by Date:
**Amusing anecdote** - Next by Date:
**Region splay** - Previous by thread:
**Amusing anecdote** - Next by thread:
**Region splay** - Index(es):