AVL-trees, hmm...

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

>> 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?
>
>Ever tried recursion? Then the array is hidden as the call-stack itself
>and is IMHO efficient.
>

That way is not effecient. Each invocation of the function has to be loaded
to the call-stack (right?). More importantly, it requires that its all done
at once; it can't be strected out over a period of time. Then there's not
much point of the iterator being external... (an Apply() method with a
callback function argument, perhaps a template, would be much more sensible
for what you are suggesting)

I've figured out a way to do it. Basically, the trick is that the fact that
the iterator follows a very strict set of rules that only allows it to be at
one position in the tree after having iterated over a specific number of
nodes. So, when at a position, and trying to find out wheter to go ro the
right, left or parent of the node at that position, it can figure out, by
the fact that it IS at that position, where it should go next. I haven't
actually implemented it, but it should work.

>Do you know AVL-Trees? Don't they fit better to your problem then array
>based binary trees?
>

My knowledge of the more advanced data structures is limited to B-trees,
binary search trees, heaps and hash tables. Of course I know of all the less
advanced datastructures like stacks, ques and linked lists.

Unfortunately, I do not know what an AVL-tree is. Perhaps you could direct
me to a webpage on it? I have been unable to find anything on datastructures
on the web.

If AVL trees have a better access time than balanced binary search trees,
then that sounds interesting.

I don't see how it would be possible to narrow down the search by more than
50% in one operation, as is done by the binary search trees. The only thing
that I can think of that would do something like that is to place the
entries that are accessed more frequently higher in the tree. But that would
destroy the structure of the tree, making finding anything in the tree
impossible. I'm sure there are workarounds for this, but it doesn't sound
like a very good technique. Of course, hash-tables can potentially be better
than 50% per operation, but to do that, you need to be sure of keeping the
load factor of the table low, thereby wasting alot of memory.

Can AVL-tree narrow down searches faster than by a factor of 50% per
operation? How easy are they to serialise (dump to storage) ? Are they
better at adding/removing than binary search trees?

>Sorry about these maybe ignorant questions but i don't know your
>knowledge about efficient datastructures...
>
I don't see anything ignorant in them. The truth is that my knowledge of
data-structures is quite limited. Too limited. You wouldn't happen to know
of any good websites on the subject?