LinuxQuestions.org
Register a domain and help support LQ
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 08-04-2006, 09:04 AM   #1
spx2
Member
 
Registered: Dec 2005
Distribution: debian
Posts: 160

Rep: Reputation: 30
flexible tree library


i would like to ask if for C(not c++) there are
written any free libraries(opensource) for creating
trees with variable number of child nodes(siblings) on
each father node.
and the nodes could have a linked list as a
member.

also if you don't know such a library please let
me know where am i most likely to find a library
like this.

i would write one from zero but...i would be wasting
time.
 
Old 08-05-2006, 07:48 AM   #2
dmail
Member
 
Registered: Oct 2005
Posts: 970

Rep: Reputation: Disabled
Does a B tree fit your requirements?
http://www.fearme.com/misc/alg/node23.html
 
Old 08-07-2006, 02:58 AM   #3
spx2
Member
 
Registered: Dec 2005
Distribution: debian
Posts: 160

Original Poster
Rep: Reputation: 30
i just need a variable number of children on each node.
b-trees not fit my needs.
 
Old 08-07-2006, 08:40 AM   #4
dmail
Member
 
Registered: Oct 2005
Posts: 970

Rep: Reputation: Disabled
Quote:
Originally Posted by spx2
i just need a variable number of children on each node.
b-trees not fit my needs.
Why not?
Quote:
In computer science, B-trees are tree data structures that are most commonly found in databases and filesystems. B-trees keep data sorted and allow amortized logarithmic time insertions and deletions.

The idea behind B-trees is that internal nodes can have a variable number of child nodes within some pre-defined range.
http://en.wikipedia.org/wiki/B-tree

Last edited by dmail; 08-07-2006 at 08:41 AM.
 
Old 08-09-2006, 02:40 AM   #5
worzel68
Member
 
Registered: May 2006
Location: Sydney
Distribution: FC5, FC3, AIX, System V,
Posts: 50

Rep: Reputation: 15
Lots of people confuse B-Trees with Binary trees. Blame the name of the BTree!!
 
Old 08-10-2006, 07:04 AM   #6
spx2
Member
 
Registered: Dec 2005
Distribution: debian
Posts: 160

Original Poster
Rep: Reputation: 30
if i have time i will look on those trees
but in the meantime i am doing trees with linked
lists to have multiple children
 
Old 08-10-2006, 01:51 PM   #7
sundialsvcs
Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 5,377

Rep: Reputation: 1108Reputation: 1108Reputation: 1108Reputation: 1108Reputation: 1108Reputation: 1108Reputation: 1108Reputation: 1108Reputation: 1108
You might need a combination of data structures. For example, you might need a Tree where one elment of each Leaf consists of a List. The constructor and destructor of the Leaf object could certainly manage an attached List.

Now, having said that ... always begin by very carefully describing to yourself: "what, not how you need to do."

In other words, without right-away committing to the notion that what you need is "a tree," look at just what you need to be able to put into this structure and what kinds of queries you need to make of it, what kinds of changes you need to make to it, and any sequence-order requirements.
 
Old 08-10-2006, 09:13 PM   #8
95se
Member
 
Registered: Apr 2002
Location: Windsor, ON, CA
Distribution: Ubuntu
Posts: 740

Rep: Reputation: 32
B-trees probably won't suit your needs. I believed they are optimized for storage on-disk, not in memory.

Here is a simple red-black tree implementation I created (to be versatile): http://www.tomswitzer.com/files/rbtr...6-08-10.tar.gz

I tried to be versatile, so you can change the compare function to use w/ the value (the 2nd parameter passed in tree_insert). I also let you associate every value entered into the tree w/ some data, so it can be used as an associative array or something similar. Also, you can use some linked list implementation, for example, as the data, and have something else as the value. Here is a very simple example,

Code:
#include <stdio.h>
#include <string.h>
#include "tree.h"

int main() {
  int i;
  tree_t t = tree_create();

  tree_set_compare_function(t, (int (*)(void *, void *))strcmp);

  tree_insert(t, "hello", "there");
  tree_insert(t, "bye", "you are");

  printf("%s %s\n", tree_search(t, "hello"), tree_search(t, "bye"));

  for(i=0; i < tree_size(t); i++) {
    printf("%s ", tree_item(t, i));
  }
  putchar('\n');

  tree_destroy(t);
}
The 2 files your interested in are tree.c and tree.h. tree_test.c you can ignore. Just copy tree.c and tree.h over to whatever project you want to use them in, and compile them as part of your source.

You can also search by index (position) using tree_item so you can iterate over all the elements in a tree.
ALL operations are done in O(log n), including tree_item and tree_size. If you want more info, check out tree.c, it has much more detailed explainations of each function in tree.h than tree.h itself.
 
Old 08-11-2006, 04:18 AM   #9
Flesym
Member
 
Registered: Aug 2005
Location: Germany
Distribution: Ubuntu, Debian
Posts: 189

Rep: Reputation: 31
Here is al library for directed graphs. And because a tree is a subset of these graphs (well actually it is undirected, but you can simply work around this restriction)it may fit you needs. But I must confess, that I never used it myself.

EDIT:
Oh, I just read, that this library also supports undirected graphs, and with this you can model your tree without any "workaround."

Last edited by Flesym; 08-11-2006 at 04:26 AM.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

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 Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
anyone know linux like ipcop, but more flexible? xcore_on Linux - Newbie 4 05-13-2006 10:49 AM
Do I need something more flexible than Firestarter? rickh Linux - Security 3 01-05-2006 09:57 AM
most flexible distro puishor Linux - General 2 06-26-2005 04:45 AM
the bible = the tree of the knowledge of good and evil () Jesus = the tree of life Michael111 General 2 04-14-2004 04:28 PM
need a P-Tree (Patricia Tree) library manaskb Programming 1 11-02-2002 06:15 PM


All times are GMT -5. The time now is 10:53 AM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration