Memory overhead for trees?
phr-n2002b at NOSPAMnightsong.com
Fri Aug 16 01:48:53 CEST 2002
pinard at iro.umontreal.ca (François Pinard) writes:
> I'm toying with the idea of converting an existing LISP system into Python.
> The system uses a lot of real trees, I mean, more deep than wide on average.
> Trees are traversed and explored a great deal, but modified relatively less
> often. I'm seeking a representation which, while being reasonably efficient
> -- yet no miracles are expected here! -- is not too voracious on memory.
If it's a binary tree that's reasonably balanced, the usual
representation is a linear array like in the heapsort algorithm.
a is the root; and for any node a[i], the node's children are
a[2*i+1] and a[2*i+2].
More information about the Python-list