Binary search trees (AVL trees)

[Dennis \(Icarus\)]

Nick Keighley a écrit :

jacob navia a écrit :

After posting [about an implementaion of a tree], I have just discovered
that I can do > the transition
between the smallish 65535 limited trees to the 32 bit ones
AUTOMATICALLY!

Since I keep the count of the elements in the tree header, when I arrive
at inserting the 65537th element I have just to change the POINTER of
the vtable to point to the vtable of the 32 bit version, reallocate the
nodes in 32 bits and go on!

This is completely impossible to do in C++ since an object can't change
dynamically its class at runtime.

nonsense. Anything you can do in C you can do in C++.

No. In C++ you can't manipulate the vtable for an object...
It is the compiler that manages it. You can't even access it.

You can't change
types dynamically in either C or C++.

True. But in C you canchange the vtable for an object,
what you can't do in C++.

<snip>
So it does look like you're talking about virtual method table.
Cool.

Since C doesn't have virtual methods it's difficult to manipulate it.

If you're implementing your own vtable, this can be done in C++ as well.

Dennis

 

[Stefan Ram]

Try this in C++ and see how far you get:

»Do« means »process behavior«, not »source code«.

#include <stdlib.h>
int main(void) (...)

#include <cstdlib>
int main(){ return EXIT_FAILURE; }

 

[Ben Bacarisse]

James Dow Allen a écrit :

For all containers we have the "Apply" function:
bool (*Apply)(<container ptr> ST,int (*Applyfn)(const void
*data,void *arg),void *arg);

In the "arg" function you pass an argument to the applied function.
You can then, pass a structure pointer or whatever is needed.

I don't think this is as flexible than traverser structures. Does
your function allow one to "bail out" early for example?

<snip>

 

[jacob navia]

Richard Heathfield a écrit :

Nick Keighley wrote:



Try this in C++ and see how far you get:

#include <stdlib.h>
int main(void)
{
int delete = EXIT_FAILURE;
return delete;
}



<snip>

This is the only contribution of heathfield to this thread.

Well, it is like his chapter on AVL trees. Nothing very substantive
to say the least. No discussion about advantages, disadvantages.
He wastes 32 bits in storing the 2 bits of per node info, no discussion about
possible optimizations...

The data items are all integers, obviating the complications associated
with anything remotely useful since the primitive C comparison operations
work on integers... No passing of a comparison routine, etc etc.

Just a bunch of code, with some elementary explanations.

Nothing blatantly wrong either, like in the above "contribution".
Of course the code above is not wrong, and even it is correct.

He just fails to grasp (or is unable to propose) anything useful, like the
code in his book.


He *could* make a contribution but chooses to argue endlessly with
spinoza111, apparently his best friend

 

[jacob navia]

Ben Bacarisse a écrit :

I don't think this is as flexible than traverser structures.

Mmmm I thought "travcerser structures" were a context passed between different calls to the
user callback function, and maybe I am wrong. Can you please explain more or point me to a reference?

Thanks

Does
your function allow one to "bail out" early for example?

Can be easily added by using a special return value
as a "break iteration" command, for instance if you
return a value lower than zero...

I will add it this evening.

 

[Ben Bacarisse]

Ben Bacarisse a écrit :

Mmmm I thought "travcerser structures" were a context passed between
different calls to the user callback function, and maybe I am
wrong. Can you please explain more or point me to a reference?

http://www.stanford.edu/~blp/avl/libavl.html/Traversers.html

The idea of some kind of "thing" that points into the tree and can be
moved in one or other direction is not uncommon, but Ben Pfaff's
implementation is one of the most flexible that I've seen.

Presumably C++'s iterators do something very similar internally.

Can be easily added by using a special return value
as a "break iteration" command, for instance if you
return a value lower than zero...

I will add it this evening.

That will interfere with the current return value of course. You've
not said what it is for, so maybe there is little damage.

C does not have a notation for a function value, so interfaces that use
a function pointer are always rather clumsy. I think including some
sort of iterator would help.

 

[jacob navia]

Richard Heathfield a écrit :

I haven't written a chapter on AVL trees.

<snip>

Strange strange. I have an old book called "C unleashed" from a certain
Richard Heathfield.

Page 479 and following there is a chapter on "AVL trees".

You forgot that?

Or you did not read the book?

(I have to admit it is failry long to read from start to end, quite a
lot of stuff...)

 

[Keith Thompson]

Richard Heathfield a écrit :

Strange strange. I have an old book called "C unleashed" from a
certain Richard Heathfield.

Page 479 and following there is a chapter on "AVL trees".

[...]

Richard Heathfield is not the only author of that book. Have you
considered the possibility that someone else wrote that chapter?

 

[Dann Corbit]

My project will be open source with no copyright (no GPL either) so that
anyone can use it, and adapt it as he/she sees fit. Nothing is hidden,
but not all things are standardized. Actually, the objective is to
propose an interface standard, and propose a sample implementation.

[...]

In other words, you want it to be public domain.

My understanding is that, under most current copyright laws,
anything you create is automatically copyrighted by default.
To release it to the public domain, you have to say so explicitly.

See, for example, <http://www.sqlite.org/copyright.html>. I presume
they got it right. I am not a lawyer; please do not take my word
on anything I say on this topic without checking elsewhere.

A Berkeley style license also answers the goal pretty nearly, and adds
additional protections (against, for instance, hijacking the code).

 

[jacob navia]

Richard Heathfield a écrit :

And I only wrote about a quarter of it.

OK, but anyway, my critic stands.

There is nothing WRONG in that book, in the sense of writing something that
will not compile, or is an outright mistake. It is just the fact that each time
I try to find some useful information I am confronted to a program that does
the bare minimum.

The AVL is just an example. Others include the handling of bitstrings, that
I looked it up when I as doing bitstrings some months ago. A few macros, and that
was it. All the difficulties (and beauty) of the subject are ignored.

Maybe because the book tries to cover such an enormous amount of material
the treatment is superficial, and it can't really go in depth into any subject,
so when you look up somethingyou just get another disappointment.

Or it can be that I expect too much from an enciclopedic book like that.

In any case if you did not write that, I am sorry.

jacob

P.S. It would be better however, that you would discuss this kind
of problems here instead of your endless discussions with spinoza111
the clutter this newsgroup with just empty polemic.

 

[Ben Pfaff]

Be sure to check out Judy Arrays:

http://judy.sourceforge.net

I spent an hour or two a few months ago looking at judy trees.
They are a nice combination of data structures that, it seems to
me, would perform well in a variety of circumstances.

But the part that bugs me about them is the documentation, which
keeps telling you over and over again how clever the designers
were. If it doesn't state explicitly that you couldn't possibly
invent such a clever data structure yourself, it at least
strongly implies it. And the explanation goes on and on breaking
everything down into tiny details, as if the rest of us couldn't
possibly understand what's going on without it. It bugs the heck
out of me.

 

[Ian Collins]

P.S. It would be better however, that you would discuss this kind
of problems here instead of your endless discussions with spinoza111
the clutter this newsgroup with just empty polemic.

Well said!

 

[bartc]

jacob navia ha scritto:

Just that they can grow and shrink and also that they can hold values of
different types. For example I can do something like

stk_t mystack = NULL;

stkPushN(myStack,3);

Is stk_t some sort of pointer? If so, how can this work: stkPushN is just
given a NULL value, how does it know what to initialise?

stkPushS(myStack,"Hello!");
printf("%d ",stkTopN(myStack));
stkPop(myStack);
printf("%s ",stkTopS(myStack));

Who owns the string that's just been popped, the stack structure, or the
caller?

Does the stack stucture record the type (number, string, etc) it's given, or
is it up to the caller to keep track?

 

[Curtis Dyer]

I spent an hour or two a few months ago looking at judy trees.
They are a nice combination of data structures that, it seems to
me, would perform well in a variety of circumstances.

But the part that bugs me about them is the documentation, which
keeps telling you over and over again how clever the designers
were. If it doesn't state explicitly that you couldn't possibly
invent such a clever data structure yourself, it at least
strongly implies it.

Yes, I also picked up that tone. When I was skimming through
_Judy IV Shop Manual_, in Sec. 3, "Smarter Digital Trees," I came
across this passage:

And, believe it or not, even if you understood all of the
following, you probably still could not write the Judy code
correctly; it's very tricky.

It seems they just went beyond implying at this point.

And the explanation goes on and on breaking
everything down into tiny details, as if the rest of us couldn't
possibly understand what's going on without it. It bugs the
heck out of me.

Although I'm probably not yet knowledgeable enough to understand
their implementation, it still seems a bit condescending to me.

 

[Dann Corbit]

Yes, I also picked up that tone. When I was skimming through
_Judy IV Shop Manual_, in Sec. 3, "Smarter Digital Trees," I came
across this passage:

And, believe it or not, even if you understood all of the
following, you probably still could not write the Judy code
correctly; it's very tricky.

It seems they just went beyond implying at this point.


Although I'm probably not yet knowledgeable enough to understand
their implementation, it still seems a bit condescending to me.

Condescending tone or not, they're really interesting.
To me, they are just a simple extension of the digital tree idea.
It's obviously a good idea for some sets of data.