One day I will get the hang of 'reply to'.
-------- Original Message --------
Subject: Re: [techtalk] DESIGN: N-ary trees
Date: Thu, 22 Mar 2001 20:38:31 -0600
From: coder <[EMAIL PROTECTED]>
[EMAIL PROTECTED] wrote:
>
> Has anyone come up with a useful design of an N-ary tree (I'm
> thinking of a 4-ary tree) where you can lift a whole branch of
> the tree and move it elsewhere?
>
> Dancer and I were arguing 4-ary trees (for use in cartesian spaces
> in computer games), and I argued it as not being practically feasible,
> and him as wanting to have one...
>
Ok, I have two random tangents, the first is about N-ary trees, the
second about your 4-ary trees to be used with cartesian points.
I am not an expert in algorithm analysis, but here are a few things of
relevance which may be interesting (this is a geek list ;)
The various flavors of b-trees are N ary trees, in that they contain
large branching factors (greater than 2). These are very usefull within
file systems as they provide fast lookup but also use disk space in an
efficent manner. For example, ResierFS uses B*trees. B+trees are also
common.
Note that the degree of a btree determines how many leaves and elements
per node it contains. A tree with degree of 2 is the simplest btree and
is called a '2-3-4' tree, and can have as many keys per node. (So, this
might be an example of your 4-ary tree, and they are used in practice).
The difference between B-trees, B+trees, B*trees, etc is in how the keys
are stored in each node. I don't recall offhand what this difference is
:/
Now, the big thing to note here is that all of these trees the keys are
ordered by a single comparison. If you are trying to order cartesian
spaces there are two values to take into account. The X axis location
and the Y axis location. This makes things a bit more difficult.
The only thing I can think of to handle this would be a dual tree, one
for each axis. But this (and any other data structure except for a
special hash) will not be a single relocation if you change both the X
and Y values of a given node.
If you change only one value for a given node, say move it along the X
axis, then you simply need to remove it and then reinsert in the proper
place in the X tree. Change both values, and you now have two removes
and inserts.
You probably want to locate a given node quickly, so this adds a hash
table to the mess.
So, you would end up with something akin to the following (pardon my
ascii art)
y
|
| d
| b
|a c
-------- x
X tree: (Nx Node X)
-------
Nc
/ \
Nb Nd
/
Na
Y tree:
-------
Nb
/ \
Na Nd
/
Nc
Node Index:
-----------
(hash)
'a' -> Na
'b' -> Nb
'c' -> etc.
This way to locate a given named node, such as 'a', you use the hash
table. To find other nodes close to 'a' along the X axis you can
traverse the X tree. To find other nodes close to 'a' along the Y axis
you can traverse the Y tree.
If you have other operations which need to be fast, then you may have to
use an alternate data structure all together.
_______________________________________________
techtalk mailing list
[EMAIL PROTECTED]
http://www.linux.org.uk/mailman/listinfo/techtalk
