Data Structure dilemma

[mshr25]

Hello,all!
I work on a kind of algorithm where the speed and memory consumption are critical. I understand that these are tradeofs but I want to try to reach an optimal solution.
Now I'll try describe the problem: I have a tree where every node have a variable number of children (maximum . The number of elements can reach many millions. In the algoritm I need to pass through all when for every node I pass through all his children one after another.
I want to ask your advice about the implementation. I have some possibilites and want to choose the optimal. So, the possibilities are:

1) To build it in a tree manner. I define a structure that is similar to a linked list, but the field 'next' will be dynamically allocated to contain the actual number of children. This seems to me the most straightforward implementation,
however it begins to be a bit complicated to allocate the memory everytime and to free all of it at the end. This way also forces me to work in the recursive way and I don't know how efficient it is.

2) To build one single linked list when I arrange the elements in a such way that for a node m at level n the children will be after the children of a node at place m-1. For every node I add a link to his first child and save the number of his children.
In this way, given a node I can pass through all his children at O(N) time.This also forces me to work on the algorithm in the recursion.

3) To work like in step "2" but instead of a linked list to add elements to the array using realloc function. However I don't if this way is fast and efficient. Also if I have to pass through all the nodes one after another, does the array have the advantage over a linked list in the access speed?

4) To work like in "2" and after it to create an array and transfer the elements from the linked list to the array.

Basically,the main advantage of the array is that it has an access of O(1) to every element and I can implement an algorithm in a non recursive way.
Therefore the main question is: for a recursive solution which is better 2 or 1, and for non recursive 3 or 4?

Thanks alot!
mshr25

[weaknessforcats]

I'm not sure of your requirement here:
1) a node can have many children
Ergo: a child can have children
Erfo: a chile is a node
Ergo: use a tree

Do I have that right?

I think you want to avoid a linked list due to the long processing times for millions of nodes.

Are you working in C++??

Ifso, try a map<> if keys are unique or multimap<> if keys are duplicated. These STL containers are maximized for speed so you won't be able to write a faster container.

map<> and multimap<> use a red/black tree which, as you know, is a binary representation of a 2-3-4-tree.

[mshr25]

Thanks for trying to answer!
First of all I work in C and I'm not familiar with C++. I did some google searching and found that my data structure is called octal tree or octree. Every node can have up to 8 children but usually it will have less (in the program I find how many exactly are for every node).There is a root node and also there are root nodes that represent the elements on the last level of division.
I try to avoid linked list because it takes more memory than array. However adding nodes to an array with realloc seems not a good idea (or maybe I wrong).
I'm also not sure whether running through an array cell after cell is faster than running through a linked list link after link-what do you say? I must say that I pass through the structure once and do not have to implement searching and deleting.

There is another method:For every node I check how many nodes it has and allocate an array of pointers to nodes accordingly. This seems to me a bit complicated. In all the implementations I saw on the net there always 8 different pointers while some of them points to data and some of them contain NULL. But it also seems to me a waste of memory.

mshr25

[JosAH]

I have been using the following structure for my good ol' minimal cost network
flow algorithm for a long time; it works fine for a general tree and it's simple:

typedef struct node {
   struct node* child; /* pointer to leftmost child */
   struct node* parent; /* pointer to parent */
   struct node* sibbling; /* pointer to next sibbling */
   data_t data;
} node_t;
 

There's just one pointer to the children which are linked together by the sibling
pointer (a linked list). The pointer to the parent makes it possible to easily crawl
back up the tree. Inserting a new leftmost child is easy. Deletion of a child takes
a linear traversal through the sibling list. But most important (to me) is/was that
all the nodes have the same size.

kind regards,

Jos

[weaknessforcats]

have been using the following structure for my good ol' minimal cost network
flow algorithm for a long time; it works fine for a general tree and it's simple:


Code: ( c )
typedef struct node {
struct node* child; /* pointer to leftmost child */
struct node* parent; /* pointer to parent */
struct node* sibbling; /* pointer to next sibbling */
data_t data;
} node_t;


There's just one pointer to the children which are linked together by the sibling
pointer (a linked list). The pointer to the parent makes it possible to easily crawl
back up the tree. Inserting a new leftmost child is easy. Deletion of a child takes
a linear traversal through the sibling list. But most important (to me) is/was that
all the nodes have the same size.

This looks exactly like the node used by map<> and multimap<>.

Arfe you sure these won't work??