Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Binary search trees (AVL trees)

Reply
Thread Tools

Binary search trees (AVL trees)

 
 
Dennis \(Icarus\)
Guest
Posts: n/a
 
      01-04-2010
"jacob navia" <(E-Mail Removed)> wrote in message
news:hhsd9d$q5c$(E-Mail Removed)...
> Nick Keighley a écrit :
>> On 3 Jan, 20:09, jacob navia <(E-Mail Removed)> wrote:
>>> 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

 
Reply With Quote
 
 
 
 
Stefan Ram
Guest
Posts: n/a
 
      01-04-2010
Richard Heathfield <(E-Mail Removed)> writes:
>>Anything you can do in C you can do in C++.

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

 
Reply With Quote
 
 
 
 
Ben Bacarisse
Guest
Posts: n/a
 
      01-04-2010
jacob navia <(E-Mail Removed)> writes:

> James Dow Allen a écrit :
>> On Jan 4, 2:43 am, jacob navia <(E-Mail Removed)> wrote:
>>> I implemented over the holidays the AVL trees in a small module of
>>> around 600 lines. Obviously the bare minimum: insert/delete and
>>> find. There is an equal method to compare two trees.

>>
>> Will you allow the caller to traverse through a subtree,
>> coroutine style? (I mentioned "traverser structures" in a
>> recent thread, though with little or no response.)

>
> 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>
--
Ben.
 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      01-04-2010
Richard Heathfield a écrit :
> Nick Keighley wrote:
>
> <snip>
>
>> Anything you can do in C you can do in C++.

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


 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      01-04-2010
Ben Bacarisse a écrit :
> jacob navia <(E-Mail Removed)> writes:
>
>> James Dow Allen a écrit :
>>> On Jan 4, 2:43 am, jacob navia <(E-Mail Removed)> wrote:
>>>> I implemented over the holidays the AVL trees in a small module of
>>>> around 600 lines. Obviously the bare minimum: insert/delete and
>>>> find. There is an equal method to compare two trees.
>>> Will you allow the caller to traverse through a subtree,
>>> coroutine style? (I mentioned "traverser structures" in a
>>> recent thread, though with little or no response.)

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


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.
 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      01-04-2010
jacob navia <(E-Mail Removed)> writes:

> Ben Bacarisse a écrit :
>> jacob navia <(E-Mail Removed)> writes:
>>
>>> James Dow Allen a écrit :
>>>> On Jan 4, 2:43 am, jacob navia <(E-Mail Removed)> wrote:
>>>>> I implemented over the holidays the AVL trees in a small module of
>>>>> around 600 lines. Obviously the bare minimum: insert/delete and
>>>>> find. There is an equal method to compare two trees.
>>>> Will you allow the caller to traverse through a subtree,
>>>> coroutine style? (I mentioned "traverser structures" in a
>>>> recent thread, though with little or no response.)
>>> 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.

>
> 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/lib...raversers.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.

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


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.

--
Ben.
 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      01-04-2010
Richard Heathfield a écrit :
>>
>> Well, it is like his chapter on AVL trees.

>
> 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...)
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      01-04-2010
jacob navia <(E-Mail Removed)> writes:
> Richard Heathfield a écrit :
>>>
>>> Well, it is like his chapter on AVL trees.

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

[...]

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

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
Dann Corbit
Guest
Posts: n/a
 
      01-04-2010
In article <(E-Mail Removed)>, (E-Mail Removed) says...
>
> jacob navia <(E-Mail Removed)> writes:
> [...]
> > 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).
 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      01-04-2010
Richard Heathfield a écrit :
>>
>> (I have to admit it is failry long to read from start to end, quite a
>> lot of stuff...)

>
> 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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Binary tree search vs Binary search Bogdan C Programming 22 10-21-2010 09:46 PM
Re: Binary search trees or hash tables? BGB / cr88192 C Programming 5 01-07-2010 12:01 AM
Re: Binary search trees or hash tables? Dann Corbit C Programming 0 01-06-2010 04:16 AM
binary search trees j_depp_99@yahoo.com C++ 2 03-05-2008 02:11 PM
Help : Merging Binary Search Trees ptrSriram C Programming 3 12-12-2005 04:37 AM



Advertisments