Sv: Sv: Misc

["Bjarke Hammersholt Roune" <asmild@post6.tele.dk>]

>>I've already implemented a complete hashed binary search tree based on an
>>array. If you want to do it again, that's fine, it just seems a bit weird
to
>>do things like that.
>
>I never said I wanted to do it again (you refer to hashing, right?). I just
>said we should use that technique.
>
I don't mean just hashing. I've implemented the full code of a complete
hashed binary search tree based on an array, aswell as a non-hashed version
and a top-hashed one (see other email). Templates coupled with derivation
make it possible to have these 3 versions without writing the same code
twice.

the trick is that the entry-class exposed in the interface is not
nessecarily the same entry-class that is used internally by the tree, and
both of these are templatised. So the internal entry-class can use hashing
or not, without changing the exposed class, and without changing the code of
the basic tree. Don't worry, though, this represents no effeciency problem,
I've made sure of that.

>>Btw, you don't need to convert uncomplete balanced trees to complete
trees,
>>since all the trees you are going to be building will be already
complete...
>
>Yup, but they will not be "optimal". For example if you take that array
>layout (pos (left son) = pos (this)*2 , pos (right son) = pos (this)*2+1)
>this array is a perfectly valid balanced tree:
>
>| 5 | 3 | 8 | 2 | 4 | 6 | 10 | 1 | - | - | - | - | 7 | 9 |
>
It wouldn't be a complete tree, though. I'm not sure you know what it means
for a tree to be complete. It means that it stored in suchs a way as to be
what you call "optimal". Some call it left'ish trees. Like heaps.
Implementing things like you suggest here would be somewhat simpler, but, as
you correctly observe, *extremely* wastefull.

The tree I've implemented is kept constantly complete, meaning that it is
complete at all times, including when adding or removing entries. This also
means that if you set the capacityGrowth (how much it grows at memory
underflow) of the tree to 1, the underlying array will be at all times
exactly as large as is needed, but no larger.

Currently, the way excess memory is handeld is by having a method of the
tree ShrinkToSize(ppSizeT extraCapacity = 0) that will shrink the size of
the underlying array to exactly what is needed, plus space for an additional
extraCapacity entries.