How to efficiently build a tree from a flat structure ?

Question

Hi,

I have a bunch of objects in a flat structure. These objects have an ID and a ParentID property so they can be arranged in trees. They are in no particular order. Each ParentID property does not necessarily matches with an ID in the structure. Therefore their could be several trees emerging from these objects.

How would you process these objects to create the resulting trees ?

I'm not so far from a solution but I'm sure it is far from optimal...

Thanks !

[EDIT] @OrbMan : I need to create these trees to then insert Data into a database, in proper order.

@JPunyon : There are no circular references. A Node is a RootNode when ParentID == null or when ParentID can't be found in the other objects

Answer 1

Store IDs of the objects in a hash table mapping to the specific object. Enumerate through all the objects and find their parent if it exists and update its parent pointer accordingly.

class MyObject
{ // The actual object
    public int ParentID { get; set; }
    public int ID { get; set; }
}

class Node
{
    public List<Node> Children = new List<Node>();
    public Node Parent { get; set; }
    public MyObject AssociatedObject { get; set; }
}

IEnumerable<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects)
{
    Dictionary<int, Node> lookup = new Dictionary<int, Node>();
    actualObjects.ForEach(x => lookup.Add(x.ID, new Node { AssociatedObject = x }));
    foreach (var item in lookup.Values) {
        Node proposedParent;
        if (lookup.TryGetValue(item.AssociatedObject.ParentID, out proposedParent)) {
            item.Parent = proposedParent;
            proposedParent.Children.Add(item);
        }
    }
    return lookup.Values.Where(x => x.Parent == null);
}

Answer 2

Vague as the question seems to me, I would probably create a map from the ID to the actual object. In pseudo-java (I didn't check whether it works/compiles), it might be something like:

Map<ID, FlatObject> flatObjectMap = new HashMap<ID, FlatObject>();

for (FlatObject object: flatStructure) {
    flatObjectMap.put(object.ID, object);
}

And to look up each parent:

private FlatObject getParent(FlatObject object) {
    getRealObject(object.ParentID);
}

private FlatObject getRealObject(ID objectID) {
    flatObjectMap.get(objectID);
}

By reusing getRealObject(ID) and doing a map from object to a collection of objects (or their IDs), you get a parent->children map too.

Answer 3

Are you stuck using only those attributes? If not, it might be nice to create an array of child nodes, where you can cycle through all these objects once to build such attributes. From there, select the node with children but no parents and iteratively build your tree from the top down.

Answer 4

Not sure what you're trying to accomplish? Usually you use a tree data structure for searching, sorting, etc. - but if you're going to place the data right into a database..??..I'm not sure what the reasoning is? Are you looking to create a tree interface? and then save to a database? With each node having a unique ID and a parent ID...you basically have a structure and the base structure could be handled through the object reference (depending on how you have that setup)

Answer 5

I can do this in 4 lines of code and O(n log n) time, assuming that Dictionary is something like a TreeMap.

dict := Dictionary new.
ary do: [:each | dict at: each id put: each].
ary do: [:each | (dict at: each parent) addChild: each].
root := dict at: nil.

EDIT: Ok, and now I read that some parentIDs are fake, so forget the above, and do this:

dict := Dictionary new.
dict at: nil put: OrderedCollection new.
ary do: [:each | dict at: each id put: each].
ary do: [:each | 
    (dict at: each parent ifAbsent: [dict at: nil]) 
          add: each].
roots := dict at: nil.

Answer 6

Most of the answers assume you are looking to do this outside of the database. If your trees are relatively static in nature and you just need to somehow map the trees into the database, you may want to consider using nested set representations on the database side. Check out books by Joe Celko (or here for an overview by Celko).

If tied to Oracle dbs anyway, check out their CONNECT BY for straight SQL approaches.

With either approach, you could completely skip mapping the trees before you load the data up in the database. Just thought I would offer this up as an alternative, it may be completely inappropriate for your specific needs. The whole "proper order" part of the original question somewhat implies you need the order to be "correct" in the db for some reason? This might push me towards handling the trees there as well.