flexible tree library

spx2 · 08-04-2006, 09:04 AM

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.

dmail · 08-05-2006, 07:48 AM

Does a B tree fit your requirements?
http://www.fearme.com/misc/alg/node23.html

spx2 · 08-07-2006, 02:58 AM

i just need a variable number of children on each node.
b-trees not fit my needs.

dmail · 08-07-2006, 08:40 AM

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

worzel68 · 08-09-2006, 02:40 AM

Lots of people confuse B-Trees with Binary trees. Blame the name of the BTree!!

spx2 · 08-10-2006, 07:04 AM

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

sundialsvcs · 08-10-2006, 01:51 PM

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.

95se · 08-10-2006, 09:13 PM

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.

Flesym · 08-11-2006, 04:18 AM

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