Front page | perl.fwp |
Postings from September 2001
"David L. Nicol" <david@kasey.umkc.edu> writes:
> 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 )
This only works for complete binary trees, of course. You cannot
e.g. represent this tree (without wasting an exponential amount of
space, that it):
/\
/\
/\
/\
/\
/\
/\
/\
So it's mostly used for very specific trees. There's a standard way
to build a heap which works this way.
> Are there any CPAN modules that use this technique to create
> hash-like containers in the form of trees of [$key,$value] objects?
The Heap module might be implemented like this (there are also other
ways to do it!). Since Heaps are used in priority queues, you could
look for a module implementing those.
--
Ariel Scolnicov |"GCAAGAATTGAACTGTAG" | ariels@compugen.co.il
Compugen Ltd. | +++ THIS SPACE TO LET +++ \ We recycle all our Hz
72 Pinhas Rosen St. |Tel: +972-3-7658117 (Main office)`---------------------
Tel-Aviv 69512, ISRAEL |Fax: +972-3-7658555 http://3w.compugen.co.il/~ariels
Thread Previous
|
Thread Next