Re: Sv: Misc

[Christian Reiniger <warewolf@mayn.de>]

Bjarke Hammersholt Roune wrote:

>> 2.) PFile
>> I now implemented the core PakFile writing stuff using normal search
>> trees, not the complete stuff, because I (grr) left my algorithms book
>> at home and thus dont know the algo for converting a generic (balanced)
>> tree to a minimal complete one (taking up as little space as possible).
>> Well, later we can add this.
>> Bjarke, you convinced me concerning added hashing. I also think 4byte
>> keys are the way to go.
>>
>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.

>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 |

where the "-" things are empty fields. The tree has 10 element while the
array has to have at least 14 fields to be able to completely store the
tree. Now imagine a tree with thousands of elements. That way up to 50% of
the array space can be wasted. That's too much. The problem is to brin the
tree into a form where you can shrink the array to the *exact* size of the
tree. In our example that would be:

| 7 | 4 | 9 | 2 | 5 | 8 | 10 | 1 | 3 |


	Christian
--

Drive A: not responding...Formatting C: instead