(Tree|Nested Set|Hierarchy) Data Structure

About

A tree is a node that may have children. Tree's are inherently recursive by definition as each child of a node is a Tree itself, with or without children nodes.

A tree is a special case of a graph structure as this is the only graph that have a hierarchical relationship.

It's an rooted acyclic undirected graph. Undirected because the relation between a parent and its child is symmetric.

Relationship rules:

• Each element (node) in a tree has exactly one parent, with the exception of the root node, which has none.
• Each element (node) in a tree has one or more child, with the exception of the leaf node, which has none.
• A tree is a hierarchy where node (items) are represented as being:
  • above, ancestor
  • below, descendant
  • or at the same level as one another. sibling

A tree is a data structures with no or slow random access. Tree structure scale well.

A set of tree is known as a forest.

Articles Related

• Relational Database: Dimensional Data Modeling - Hierarchy
• Object: Tree - Composite Type (Design Pattern)

• Tree - (Traversal|Search)
• Tree - Composite Type (Design Pattern)
• Tree - Visitor (Design Pattern)

• wiki/Nested set model
• wiki/Hierarchy