[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

PFile dir structures (was: Misc)

Bjarke Hammersholt Roune wrote:

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

Can you send me the code? Although I'm not so interested in the complete
tree thing (see my other mail) that template/derivation efficiency sounds
interesting. Especially because I used templates only a few times up to now.

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

I guess theres some terminology confusion here, because we used different
words in Uni:

"vollstaending" (= "complete") means that each inner node has exactly two
sons (note: I didn't remember this correctly - neither of our trees is
neccesarily complete in this sense)

"voll" (= "full") means that all nodes on all levels except the two lowest
levels have exactly two sons (that neither describes a balanced tree as
used in PFile nor a complete tree as you see it).

I had these terms in the back of my mind and thus was a bit confused ;)


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