"David L. Nicol" <[EMAIL PROTECTED]> writes:
[...]
> Hashes also waste a lot of space. Something balanced might use less
> space than a hash. Depends on the data, of course.
I don't think most (sorted) balanced tree implementations do this, due
to the memory waste. Exactly balanced trees are not exactly popular.
Approximately balanced trees (AVL trees, 2-3 trees leer at me from dim
memory of Data Structures class) have slightly different heights at
different leaves. That's a problem: if you have to add just one leaf
at a new level below an n-element complete tree, you'll be adding an
average of n/2 elements, depending on precise location
The advantage of having everything in one array is of course that you
eliminate 2 or 3 pointers per element. The problem is you still need
to get a pretty densely-packed tree for this to pay off, if you're
going to be wasting a lot more than 33% of your allocated space.
It gets worse, though. You're no longer dealing in pointers. All the
rebalancing algorithms reassign pointers to move entire subtrees.
That moves k elements in time O(1). With an array, everything must
move, so you'll be paying time O(k) to move k elements each time.
(Array-based heaps have neither of these problems).
--
Ariel Scolnicov |"GCAAGAATTGAACTGTAG" | [EMAIL PROTECTED]
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
