Datastructures

[Bloodstein]

Hi,

I need a datastructure to store data that has a structure similar to a tree. The tree can have multiple children (not constrained to 2). Each child can have only one parent.

I'm thinking at the moment of implementing a Graph data structure (which is really an expanded tree). However, i dun need the complexity associated with one child being able to belong to two parents.

The data structure has to be extremely efficient in sorting data "horizontally" (ie. across parents) as opposed to vertically. Searching is also an important feature so that has to be pretty efficient as well. Efficiency for adding and removing data is more relaxed.

So, any suggestions on an appropriate data structure is welcome. I would be implementing the data structure in VB. Also, I'd really hate to go out an code the whole data structure, so any help on places where i can find VB implementation of those data structures (or any other language that is easy to port to VB) would be really really really appreciated. Even better, any reference to existing data structure in VB that handles my situation would be appreciated (I'm thinking 'bout the TreeNode that TreeView control uses....but, wat do u guys think?)

Thanks

 

[Grimfort]

If you have a class, that has a collection (or listarray) inside. You can create methods that add, select, and delete children (objects) that are stored in this array.

Basically, you just have one class, that holds a reference to its owner (of the same type of class), and a list of its children (same type of class). The top class has no owner.

 

[Bloodstein]

That would work. But efficiency is also a rather important factor. Would that really be efficient?

 

[Grimfort]

Its exactly how the nodes and listviewitems work (well as close as you can be from my knowledge).
Make sure you use ListArray or extend of BaseCollection.
The Collection object, gets slow after around 200k items added to it.

For a general reference to speed, I have around 8 sets of these structures, filled with about 10-15k objects, which are accessed fairly often. I havent seen any big issues with speed, just my overhead of calling back to VB6 stuff .