0

I have a database of nodes. Each node can have exactly one parent, but any number of children. Some nodes may be stored with no parent, but at run time, I can create a default "root" node to be the parent of these.

First off, what is this data structure called? I think it's just a "tree," but I want to make sure I'm using the correct terminology.

Another issue I'm running into is finding an efficient way to create the tree. The nodes can be retrieved from the database in any order, so when I add a node to the tree, its parent may not be in the tree yet. This means that when I add a node, I have to check whether any existing nodes have parents and then add the parent in the appropriate spot.

I've searched a lot online, but most talk about trees just refers to "binary trees," and even then I can't even find any good examples of constructing the tree in code -- it's usually working with an existing tree.

Are there any examples of efficient ways to build this tree (whatever it may be called)? Language doesn't matter, but I'll be using php.

2 Answers 2

2

With the caveat that each node has exactly one parent except for the root node, calling this a tree is fine.

With respect to building the tree, one way is to do the following:

  1. keep some kind of associative lookup of existing nodes indexed by their unique ID (I don't know PHP, but I'm thinking some kind of dictionary or hash)
  2. keep a similar lookup of orphan nodes, indexed by parent ID
  3. when you create a node:
    1. see if it's parent is in the existing set
      • if it is, attach the child to the parent
      • if not, insert the new node in the orphan set
    2. then see if any orphans are waiting for it (nodes in the orphan set indexed with the new node's ID)
      • if there are, attach them and remove them from the orphan set
    3. finally, add the new node to the existing set
  4. at the end, anything still in the orphan set is either a problem, or should be attached to your root node.

Assuming, of course, you have some unique ID to identify parent/child relationships.

Oh, and I seem to have used the word set to mean some kind of associative container - note that it can't be unique or 3.2 will have problems with multiple orphans of the same node.

3
  • Thanks, this is actually what I planned to do.. I just didn't want it to be inefficient. I guess the associative lookups on orphan/existing parents would be really fast, but since this is a tree it seems like it would make more sense not to have sets with all nodes, but to traverse the tree to find the parent node.. I'm probably just thinking about this too hard. Jan 27, 2012 at 16:11
  • It shouldn't be unusually slow, but do clarify if you have some specific non-functional requirements. If it is actually a search tree, you might be able to avoid building the existing lookup, but you're probably replacing a probably constant-time hash lookup with a log-time tree lookup. Besides which, the route from root to your new parent may be unclear if it's in an orphaned subtree.
    – Useless
    Jan 27, 2012 at 16:18
  • Your name belies your usefulness .. The tree organization is somewhat arbitrary based on the unique IDs -- I guess I'll just stick with an associative array. Jan 27, 2012 at 16:24
1

Your definition is insufficient for a tree. Simply enforcing that each node has exactly one parent is in fact far from a tree, because it already guarantees your structure will be cyclic.

A tree is a directed graph without cycles, in which any two vertices are connected by exactly one (simple) path. If you leave out the simple path requirement you end up with a more general structure, called the directed acyclic graph. If you further allow cycles, you get a directed graph, which is pretty much what you have given your simple description.

Independent of whether the definition of your data nodes you gave is exact or not, you may do best by assuming a directed (acyclic) graph for your construction process. In a graph, standalone nodes that are not (yet) connected are a normal case that won't give you any trouble. So you can read out the database in any order you want to and construct your datastructure from that.

Edit: I already assumed that your structure is acyclic. But do note that any tree is also a special case of a graph, so the above all holds. Do read up on graph datastructures, as they allow you to construct trees in an incremental fashion, without requiring proper roots and children all the time. You only have to guarantee, that the final graph will indeed be a tree structure (which mainly depends on your database content).

1
  • I left out an important point then: cycles are not possible with this structure either. A node cannot be the parent of a higher level node. Jan 27, 2012 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.