Sv: PFile dir structures (was: Misc)

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

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

Well, that's the cool thing about templates: they not only sometimes make
things ALOT easier, but they will requently speed up your code too. This
usually comes at the cost of larger size of the finished product, though.

>>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)
>
That's what I understand as "full".

>"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).
>
That sounds like something that migth be usefull with AVL trees. My
knowledge is limited with AVL trees, though, so I may be talking nonsense :)

>I had these terms in the back of my mind and thus was a bit confused ;)
>
Ah, ok. Some of my statements must've seem a bit weird to you... :)

Quoting from the book "Data structures and other objects using C++":

[QUOTE]
Full Binary Trees
In a full binary tree, every leaf has the same depth, and every non-leaf has
two children.

Complete Binary Trees
Suppose you take a full binary tree and start adding entries at a new depth
from left to right. All the new leaves have the same depth - one more than
when we started - and we always add leftmost nodes first. [SNIP] In order to
be a complete tree, every level except the deepest must contain as many
nodes as possible; and at the deepest level, all nodes are as far left as
possible.
[UNQUOTE]