Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > simple BST implementation

Reply
Thread Tools

simple BST implementation

 
 
Mark
Guest
Posts: n/a
 
      10-23-2009
Thank you for commentaries. Hope my late response will be noticed. I have a
few more queries.

Seebs wrote:
[skip]
> I'd probably do these two differently.
>
> tree_node *tree_addnode(struct tree_node *root, void *data, int
> (*cmp_fn))...
>
> But even this is error-prone. In this case, I think it makes more
> sense to distinguish betwen the tree and its nodes.
>
> So I recommend:
>
> struct tree {
> int (*cmp_fn)(const void *d1, const void *d2);
> struct tree_node *root;
> }


Richard Heathfield wrote:
> I would take a pointer to a tree structure (which manages the root and
> any housekeeping information needed by the tree), the data, the size,
> and an optional void * for side-channel information. (Consequently, I
> would add an extra void * to the comparison function.)


So as I see it, both Seebs and Richard recommend to represent the
abstraction of the BST in two structures - one for the tree's node and the
other one is for the tree itself. What is the profit of doing this? When is
it good to exploit such method and for what data structures?

PS. Now I remember I have seen such technique somewhere in a circular list
implementation.

--
Mark

 
Reply With Quote
 
 
 
 
Seebs
Guest
Posts: n/a
 
      10-23-2009
On 2009-10-23, Mark <(E-Mail Removed)> wrote:
> So as I see it, both Seebs and Richard recommend to represent the
> abstraction of the BST in two structures - one for the tree's node and the
> other one is for the tree itself. What is the profit of doing this? When is
> it good to exploit such method and for what data structures?


I usually do something like that when I feel that the container is somehow
genuinely distinct from its "top" member. The tree seems to be the right
place to, for instance, stash a comparator function -- since presumably you
always want the same one for the tree (and some trees need a comparator to
decide where a new item goes). It is not obvious to me that individual
nodes are, in real use cases, likely to make sense to treat the same way
you treat the tree as a whole.

By contrast, I wouldn't usually do this for a singly-linked or doubly-linked
list...

> PS. Now I remember I have seen such technique somewhere in a circular list
> implementation.


That can make sense too.

So why for a doubly-linked list, but not a circular list? Because for a
doubly-linked list, you can always find the ends by iterating, but there
isn't necessarily an end for a circular list.

-s
--
Copyright 2009, all wrongs reversed. Peter Seebach / http://www.velocityreviews.com/forums/(E-Mail Removed)
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
 
Reply With Quote
 
 
 
 
user923005
Guest
Posts: n/a
 
      10-23-2009
On Oct 22, 8:22*pm, Seebs <(E-Mail Removed)> wrote:
> On 2009-10-23, Mark <(E-Mail Removed)> wrote:
>
> > So as I see it, both Seebs and Richard recommend to represent the
> > abstraction of the BST in two structures - one for the tree's node and the
> > other one is for the tree itself. What is the profit of doing this? When is
> > it good to exploit such method and for what data structures?

>
> I usually do something like that when I feel that the container is somehow
> genuinely distinct from its "top" member. *The tree seems to be the right
> place to, for instance, stash a comparator function -- since presumably you
> always want the same one for the tree (and some trees need a comparator to
> decide where a new item goes). *It is not obvious to me that individual
> nodes are, in real use cases, likely to make sense to treat the same way
> you treat the tree as a whole.
>
> By contrast, I wouldn't usually do this for a singly-linked or doubly-linked
> list...
>
> > PS. Now I remember I have seen such technique somewhere in a circular list
> > implementation.

>
> That can make sense too.
>
> So why for a doubly-linked list, but not a circular list? *Because for a
> doubly-linked list, you can always find the ends by iterating, but there
> isn't necessarily an end for a circular list.


Plus, the end of a ring buffer often rolls forward. So even after you
found a start or an end, chances are it has moved shortly thereafter.
Plus, ring buffers are either empty, partly full, or full. The
elements of the ring buffer have no idea which state the ring buffer
as a whole is in.
A ring buffer needs a secondary observer thing that understands the
ring state.
 
Reply With Quote
 
user923005
Guest
Posts: n/a
 
      10-23-2009
On Oct 23, 12:32*am, Richard Heathfield <(E-Mail Removed)> wrote:
> In
> <(E-Mail Removed)>,
>
> user923005 wrote:
>
> <snip>
>
> > Plus, ring buffers are either empty, partly full, or full.

>
> Not necessarily! *They can be dynamic, expanding as demand
> requires. (Mine tend to do that.)
>
> <snip>


Do you mean to tell me that your ring buffers are neither empty, full,
nor partly full?

Now that's an interesting data structure.
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      10-23-2009
user923005 <(E-Mail Removed)> writes:
> On Oct 23, 12:32*am, Richard Heathfield <(E-Mail Removed)> wrote:
>> In
>> <(E-Mail Removed)>,
>>
>> user923005 wrote:
>>
>> <snip>
>>
>> > Plus, ring buffers are either empty, partly full, or full.

>>
>> Not necessarily! *They can be dynamic, expanding as demand
>> requires. (Mine tend to do that.)
>>
>> <snip>

>
> Do you mean to tell me that your ring buffers are neither empty, full,
> nor partly full?
>
> Now that's an interesting data structure.


If it can expand as demand requires, it needn't ever be full.

--
Keith Thompson (The_Other_Keith) (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
 
James Kuyper
Guest
Posts: n/a
 
      10-23-2009
Keith Thompson wrote:
> user923005 <(E-Mail Removed)> writes:
>> On Oct 23, 12:32 am, Richard Heathfield <(E-Mail Removed)> wrote:
>>> In
>>> <(E-Mail Removed)>,
>>>
>>> user923005 wrote:

....
>>>> Plus, ring buffers are either empty, partly full, or full.
>>> Not necessarily! They can be dynamic, expanding as demand
>>> requires. (Mine tend to do that.)
>>>
>>> <snip>

>> Do you mean to tell me that your ring buffers are neither empty, full,
>> nor partly full?
>>
>> Now that's an interesting data structure.

>
> If it can expand as demand requires, it needn't ever be full.


In that case, it should be either empty or partly full. To claim the
existence of a situation where none of three options listed of
user923005 apply you'll have to explain a lot more than just that.
 
Reply With Quote
 
user923005
Guest
Posts: n/a
 
      10-23-2009
On Oct 23, 7:31*am, Keith Thompson <(E-Mail Removed)> wrote:
> user923005 <(E-Mail Removed)> writes:
> > On Oct 23, 12:32*am, Richard Heathfield <(E-Mail Removed)> wrote:
> >> In
> >> <(E-Mail Removed)>,

>
> >> user923005 wrote:

>
> >> <snip>

>
> >> > Plus, ring buffers are either empty, partly full, or full.

>
> >> Not necessarily! *They can be dynamic, expanding as demand
> >> requires. (Mine tend to do that.)

>
> >> <snip>

>
> > Do you mean to tell me that your ring buffers are neither empty, full,
> > nor partly full?

>
> > Now that's an interesting data structure.

>
> If it can expand as demand requires, it needn't ever be full.


In that case, I want one. My data structures always fill up.

I do think I will give expandable ring buffers a bit more thought.

I have lots of ring buffers in my code base, but they tend to be fixed
size (determined by some parameter).

A little thought about ring buffers that size themselves might result
in better code.
 
Reply With Quote
 
user923005
Guest
Posts: n/a
 
      10-24-2009
On Oct 23, 9:16*pm, Richard Heathfield <(E-Mail Removed)> wrote:
> In <(E-Mail Removed)>,
>
> user923005 wrote:
>
> <snip>
>
> > A little thought about ring buffers that size themselves might
> > result in better code.

>
> Don't you read the books you help write?


It's not the reading part that stumbles me. It's the thinking.

My data structures have to run by themselves in a darkened room, with
evil men throwing their worst at them (I write database software). So
I should expect the worst possible inputs to arrive billions at a
time. What will my data structure do? I need to consider that the
same evil perpetrators will be pounding the stuffings out of other
data structures on 100 other threads and I am simply not allowed to
run out of resources or fail to bring the calculation to completion in
a timely manner.

So (for me at least) these things are never as simple as they might
seem on the surface.
 
Reply With Quote
 
David Thompson
Guest
Posts: n/a
 
      11-02-2009
On Tue, 20 Oct 2009 00:02:14 -0700 (PDT), Nick Keighley
<(E-Mail Removed)> wrote:

> On 20 Oct, 06:16, Richard Heathfield <(E-Mail Removed)> wrote:
> > In <(E-Mail Removed)>, Seebs wrote:
> > > On 2009-10-20, Mark <(E-Mail Removed)> wrote:

>
> > >> /* error codes */
> > >> enum {
> > >> * * T_ESUCCESS,

> >
> > > No.

> >
> > > "EFOO" is widely recognized as indicating an *error*.

>
> it's not uncommon (nor very wrong) to lump "success" in with the
> "error" codes.


Especially with value 0, as here. Although I would write explicitly
the formally-redundant = 0 .

 
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
LL TO BST puzzlecracker C++ 2 01-19-2005 11:10 PM
Applications of stacks/queues/trees/heap/BST Ice C++ 4 12-19-2004 06:04 PM
BST: remove less than Ridimz C++ 8 10-07-2003 01:40 AM
BST Rupert harrison C++ 2 09-15-2003 08:38 AM
BST & recursion Andrew Edwards C++ 12 08-04-2003 10:54 AM



Advertisments