On Fri, 12 Apr 1996, Wout Mertens wrote:
> And another thing, someone mentioned splay trees? Something like that it
> was a binary tree, but when you found a room, it was moved upwards in
> the tree? But how do you find it back later?
With the splay tree, the found node is moved to the head of the tree, and
the old head is reconnected to the new head and things are rearranged.
I'm not exactly fluent with the mechanics of it, just that it exists, and
is faster for often-used nodes (think of it like a disk cache, frequently
accessed files are put in the cache while less often used files have to be
read straight from the disk. This is NOT how a splay tree works, but the
effects are similar).
A 'splay' function does all the rearranging of nodes. As far as using
splay trees, it's exactly like a normal binary tree (left node, right node,
and parent node (which I think is required for splay trees)).
As for finding the node after it moves up, think of the rearranging as
changing the order you added the nodes to the tree. For example, you
originally had a tree like this:
F
/ \
D G
\
E
You find 'E', and the tree gets rearranged to:
E
/ \
D F
\
G
One of the problems with splay trees is their worst-case lookup time. I
don't remember the 'O' stuff for it, but basically is the same as a linked-list.
HOWEVER, splay trees balance themselves out as they're accessed, so the
worst-case lookup is rarely done.
Like I said before, I'm no expert on these things. I've just poked around
with them a bit.
This is probably getting off-topic, so I'll add that hash tables, or more
properly arrays of lists (or trees) are probably best for room lookups.
- Mark
markd@eskimo.com (finger markd@eskimo.com for my PGP signature)
http://www.eskimo.com/~markd U.S.A. Home of the Alternate Reality page
This archive was generated by hypermail 2b30 : 12/18/00 PST