Are trees organised by a "firstchild, nextsibling" structure? If not, why not?

Question

Usually, tree data structures are organised in a way that each node contains pointers to all its children.

       +-----------------------------------------+
       |        root                             | 
       | child1            child2         child3 |
       +--+------------------+----------------+--+
          |                  |                |
+---------------+    +---------------+    +---------------+
|    node1      |    |     node2     |    |     node3     |
| child1 child2 |    | child1 child2 |    | child1 child2 |
+--+---------+--+    +--+---------+--+    +--+---------+--+
   |         |          |         |          |         |

This seems natural, but it comes with some problems. For example, when the number of child nodes varies, you need something like an array or list to manage the childs.

By using only (first)child and (next)sibling pointers instead, we get something that looks like that:

       +-------------------+
       |        root       |
       | child    sibling  +--->NULL
       +--+----------------+
          |             
+----------------+    +----------------+    +----------------+
|    node1       |    |     node2      |    |     node3      |
| child  sibling +--->| child  sibling +--->| child  sibling +--->NULL
+--+-------------+    +--+-------------+    +--+-------------+
   |                     |                     |

Oviously, this kind of structure can represent trees just as well, but it also offers some advantages. Most important is that we don't have to worry about the number of child nodes any more. When used for a parse tree, it offers a natural representation for a term like "a+b+c+d+e" without becoming a deep tree.

Do collection libraries offer tree structures like that? Do parsers use such a structure? If not, what are the reasons?

Answer 1

Trees, like lists, are "abstract data types" which can be implemented in different ways. Each way has it's advantages and disadvantages.

In the first example, the main advantage of this structure is that you can access any child in O(1). The disadvantage is that appending a child might sometimes be a little more expensive when the array has to be expanded. This cost is relatively small though. It is also one of the simplest implementation.

In the second example, the main advantage is that you always append a child in O(1). The main disadvantage is that random access to a child costs O(n). Also, it may be less interesting for huge trees for two reasons: it has a memory overhead of one object header and two pointers per node, and the nodes are randomly spread over memory which may cause a lot of swapping between the CPU cache and the memory when the tree is traversed, making this implementation less appealing for them. This is not a problem for normal trees and applications though.

One last interesting possibility which was not mentioned is to store the whole tree in a single array. This leads to more complex code, but is sometimes a very advantageous implementation in specific cases, especially for huge fixed trees, since you can spare the cost of the object header and allocate contiguous memory.

Answer 2

Almost every project that has some editable model or document will have a hierarchical structure to it. It can come in handy to implement the 'hierarchical node' as a base-class for different entities. Often the linked-list (child sibling, 2nd model) is the natural way many class libraries grow, however the children may be of diverse types, and probably an "object model" is not what we consider when talking about trees in general.

My favorite implementation of a tree(node) of your first model is a one-liner (in C#):

public class node : List<node> { /* props go here */ }

Inherit from a generic List of your own type (or inherit from any other generic collection-of-your-own-type). Walking is possible in one direction: form the root downward (items do not know their parents).

Parent only tree's

Another model you did not mention is the one where every child has a reference to it's parent:

               null
                 |
       +---------+---------------------------------+
       |       parent                              |
       | root                                      |
       +-------------------------------------------+
          |                   |                |
+---------+------+    +-------+--------+    +--+-------------+
|     parent     |    |     parent     |    |     parent     |
|     node 1     |    |     node 2     |    |     node 3     |
+----------------+    +----------------+    +----------------+

Walking this tree is only possible the other way round, normally all these nodes will be stored in a collection (array, hashtable, dictionary etc..) and a node will be located by searching the collection on criteria other than the hierarchical position in the tree which would typically not be of primary importance.

These parent-only tree's are usually seen in database applications. It's quite easy to find the children of a node with "SELECT * WHERE ParentId=x" statements. However we seldom find these transformed into tree-node class objects as such. In statefull (desktop) applications they may be wrapped into existing tree-node controls. In stateless (web)applications even that may be unlikely. I've seen ORM-mapping class-generator tools throw stack overflow errors when generating classes for tables that have a relation with themselves (chuckle), so maybe these tree's are not that common after all.

bidirectional navigable trees

In most practical cases however, it's convenient to have the best of both worlds. Nodes that have a list of children and in addition know their parent: bidirectional navigable trees.

                          null
                            |
       +--------------------+--------------------+
       |                  parent                 |
       |        root                             | 
       | child1            child2         child3 |
       +--+------------------+----------------+--+
          |                  |                |
+---------+-----+    +-------+-------+    +---+-----------+
|      parent   |    |     parent    |    |  parent       |
|    node1      |    |     node2     |    |     node3     |
| child1 child2 |    | child1 child2 |    | child1 child2 |
+--+---------+--+    +--+---------+--+    +--+---------+--+
   |         |          |         |          |         |

This brings along many more aspects to consider:

• Where to implement the linking and unlinking of parent's?
  • let the bussiness logic take care, and leave the aspect out of the node (they will forget!)
  • nodes have methods for creating children (does not allow re-ordering) (Microsofts choice in their System.Xml.XmlDocument DOM implementation, which almost drove me crazy when I first encountered it)
  • Nodes take a parent in their constructor (does not allow re-ordering)
  • in all add(), insert() and remove() methods and their overloads of the nodes (usually my choice)
• Persistance
  • How to walk the tree when persisting (leave out parent-links for example)
  • How to rebuild the two-way linking after de-serializing (setting all the parents again as a post-deserialization action)
• Notifications
  • Static mechanisms (IsDirty flag), handle recursively in properties?
  • Events, bubble up through parents, down through children, or both ways (consider the windows message pump for example).

Now to answer the question, bidirectional navigable trees tend to be (in my career and field so far) the most widely used. Examples are Microsofts implementation of System.Windows.Forms.Control, or the System.Web.UI.Control in the .Net framework, but also every DOM (Document Object Model) implementation will have nodes that know their parent as well as an enumeration of their children. The reason: ease of use over ease of implementation. Also, these are usually base classes for more specific classes (XmlNode may be the base of Tag, Attribute and Text classes) and these base classes are natural places to put generic serialization and event-handling architectures.

Tree's lay at the heart of many architectures, and being able to navigate freely means being able to implement solutions faster.

Answer 3

I don't know of any container library that directly supports your second case, but most container libraries can easily support that scenario. For example, in C++ you could have:

class Node;  // forward reference to satisfy the compiler
typedef std::list<Node*> NodeList;
class Node : public NodeList { /* . . . */ };  // a node is also a list

Node* n = new Node;
n->push_back(new Node);
Node* tree = new Node;
tree->push_back(new Node);
tree->push_back(n);

Parsers probably use a structure similar to this, because it efficiently supports nodes with variable numbers of items and children. I don't know for certain because I usually don't read their source code.

Answer 4

One of the cases when having the array of children is preferable is when you need random access to the children. And this usually is when the children is sorted. For example, the file-like hierarchy tree can use this for faster path search. Or DOM tag tree when index access is very natural

Another example is when having the "pointers" to all children allows more convenient usage. For instance both types you described can be used when implementing tree relations with relational database. But the former (master-detail from parent to children in this case) will allow querying with general SQL for useful data, while the latter will limit you significantly.