Sv: Sv: Sv: Strangest thing happened; ...

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

>I'm mainly interested in how you just store a static complete tree. No
>adding/removing, just read accesses.
>
Oh, that's quite easy. Well, ok, I didn't figure it out by myself, so that's
easy for me to say... :)

As you probably have figured out, nodes are kept track of by their offset
into the array. Offset 0 is the root, and offset size-1 is the last node in
the tree.

for every offset i, (i * 2) + 1 is the offset of i's left child.
for every offset i, (i * 2) + 2 is the offset of i's right child.
for every offset i, (i - 1) / 2 is the offset of i's parent, except for
offset 0.

Trying to obtain a non-existant left or right child will yield a value that
is greater than the size of the tree.

I've made adding work now. Removing should be quite easy to implement now.

Adding to a complete binay search tree is, it turns out, quite alot slower
than adding to a non-complete one. In complete trees, every entry has one,
and only one, correct location. Changing a node at the higest position (ie,
the root) when adding can make it nessecary to move every node in a straight
line (well, not literally straight, but conseptually) from the root to the
leftmost leaf descendant of the root. If something like that happends, that
changes the root of n subtrees of the tree where n is the number of nodes
from the root to its leftmost leaf descendant. If we're really unlucky, then
the same thing happends to every one of these subtrees, and to all of their
subtrees on the right/left side (depends on wheter the leftmost unused
location in the array was on the right or left side of the root), and so on.

[self-pity mode on]
Now, in the block of text above, there are some errors. Try if you can find
it ;)  That's what its like debugging the implementation for a complete
binary search tree...
[self-pity mode off]

The performance shouldn't matter too much, though, atlesat not if we can
avoid any merging/unmerging of the trees when loading paks. When we're
writing them, then it'll either be format 1 paks, which are to be kept
small, or format 0 ones, which its ok for to take a little while to write,
as usually that will only happen when the developer is creating the release
version of the paks, and then it really doens't matter.

It took my computer something like 1-2½ second to add 500 entries one at a
time to an empty tree, as percieved by me. This was a debug version with no
optimizations, though. I'll get around to profile it tomorrow and get a
little more precise time on a release build. The current implementation is
not very optimized, so performance should get alot better.

I haven't checked it (and I'm not going to!), but I think the worst-case
performance for adding to and removing from this kind of tree is actually
O(n) rather than O(log n). Don't know about average-case. Best case is
definately O(log n). I think :)

Performance for finding entries in this kind of tree, of course, is the same
as an ordinary binary search tree that is balanced: O(log n)

There're some things that's really nagging me:

how the "¤#%!& do you specify member functions as template parameters to a
template?

This doesn't work:

template<class ENTRY_TYPE, class KEY_TYPE, KEY_TYPE
(someClass::*KEY_METHOD)()>
class ppBinarySearchTree;

Well, ok, it kinda works because it doesn't generate any errors or warnings,
but then if you do this:

ppBinarySearchTree<TestEntry, int, TestEntry::GetKey> tree;

the compiler generates an error saying "const parameter expected". No amount
of playing around with const will get you anywhere. Why on earth isn't
TestEntry::GetKey const? I mean, you can't assign to it, because then you
get an ambiguity error, which is even more confusing. Assigning
TestEntry::GetKey to a function pointer works fine, though.

You might ask if it's really nessecary to do it like this (with the
templates). It's well worth it, as it makes it extremely easy to add hashing
capability to a derivation with only a couple of lines of code. I'll come up
with some default values so you won't have to specify all those parameters
every time you want to use suchs a tree (could we add a non-virtual inline
do-nothing member to ppBase named GetKey() and anohter one named GetHash()
for this porpuse?).

I was wondering if there aren't any good free open-source container class
libraries that will do these kinds of classes?

Does anybody know how to implement effecient external pre-order, in-order
and post-order iterators to binary trees without creating an array to keep
track of what has already been iterated over?

Does anybody know how to compute the level of a node based on its offset
into an array representing a binary tree without using base 2 logarithms or
stepping through the levels, searching for it? If not, does anybody how to
compute base 2 logarithms in C++? How expensive is this operation?