On Thu, Sep 06, 2001 at 05:57:05AM -0500, David L. Nicol wrote:
> I have just been hipped to the elegant method of storing binary
> trees in arrays, which I never knew before. Here is the kernel
> of it:
>
> The root of the tree is always at position 0
>
> The parent of any node $N is at position int($N >> 1)
>
> The children of any node are at ($N << 1) and (($N << 1) +1)
>
> ( aka $N*2 and $N*2+1 )
I've played with that. The problem is it's really expensive to
move/delete nodes. Consider what happens if you delete the root node,
N/2 nodes have to move. Deletion/moving becomes an O(N) operation
instead of O(1).
Since keeping a tree balanced involves moving nodes, inserting is now
O(N) as well.
It's a nice, efficient representation if you have a static tree that's
not going to change much.
> Are there any CPAN modules that use this technique to create
> hash-like containers in the form of trees of [$key,$value] objects?
You can look at my really, really old
http://www.cpan.org/modules/by-module/Tree/Tree.tar.gz
It uses the traditional node/pointer structure. The interesting
algorithm in there is the splay tree, which tries to readjust itself
based on usage to put the most often used nodes at the top.
PS That thing is REALLY old and fairly embarassing.
--
Michael G. Schwern <[EMAIL PROTECTED]> http://www.pobox.com/~schwern/
Perl6 Quality Assurance <[EMAIL PROTECTED]> Kwalitee Is Job One
...and I pull out the Magnum from under the desk where I keep it in case
someone laughs at a joke that's so dry it's got a built in
water-fountain, and blow the lot of them away as a community Service.
-- BOFH
