Tree structure

It has been suggested that Tree (data structure) be merged into this article or section. (Discuss)

A tree structure showing the possible hierarchical organization of an encyclopedia.

The original Encyclopédie actually used a tree diagram to show which way its subjects were ordered.

A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. It is named a "tree structure" because the classic representation resembles a tree, even though the chart is generally upside down compared to an actual tree, with the "root" at the top and the "leaves" at the bottom.

In graph theory, a tree is a connected acyclic graph (or sometimes, a connected directed acyclic graph in which every vertex has indegree 0 or 1). An acyclic graph which is not necessarily connected is sometimes called a forest (because it consists of trees).

Nomenclature and properties

Every finite tree structure has a member that has no superior. This member is called the "root" or root node. It can be thought of as the starting node. The converse is not true: infinite tree structures may or may not have a root node.

The lines connecting elements are called "branches", the elements themselves are called "nodes". Nodes without children are called "end-nodes" or "leaves".

The names of relationships between nodes are modeled after family relations. In computer science, traditionally only names for male family members had been used. In linguistics, the names of female family members are used. It is said that this was an express countermovement to the traditional naming convention, started by the female students of linguist Noam Chomsky.^{[citation needed]} However, nowadays, in computer science at least, the gender-neutral names "parent" and "child" have largely displaced the older "father" and "son" terminology, although the term "uncle" is still used for other nodes at the same level as the parent.

• A node is a "parent" of another node if it is one step higher in the hierarchy and closer to the root node.
• "Sibling" ("brother" or "sister") nodes share the same parent node.
• A node that is connected to all lower-level nodes is called an "ancestor".

In the example, "encyclopedia" is the parent of "science" and "culture", its children. "Art" and "craft" are siblings, and children of "culture".

Tree structures are used to depict all kinds of taxonomic knowledge, such as family trees, the evolutionary tree, the grammatical structure of a language (the famous example being S → NP VP, meaning a sentence is a noun phrase and a verb phrase), the way web pages are logically ordered in a web site, et cetera.

In a tree structure there is one and only one path from any point to any other point.

Tree structures are used extensively in computer science (see Tree (data structure) and telecommunications.)

Examples of tree structures

• Internet: usenet hierarchy, Document Object Model's logical structure^[1], Yahoo! subject index, Open Directory Project
• Information management: Dewey Decimal System
• Management: hierarchical organizational structures
• Computer Science: binary search tree Red-Black Tree AVL tree
• Biology: evolutionary tree
• Business: pyramid selling scheme
• Project management: work breakdown structure
• Linguistics (syntax): Phrase structure trees

Representing trees

There are many ways of visually representing tree structures. Almost always, these boil down to variations, or combinations, of a few basic styles:

Classical node-link diagrams

Classical node-link diagrams, that connect nodes together with line segments:

        encyclopedia
          /      \
      science  culture
                /   \
              art  craft

Nested sets

Nested sets that use enclosure/containment to show parenthood (for an interesting variation on this, see Treemaps):

      +------encyclopedia------+
      |          +--culture--+ |
      | science  |art   craft| |
      |          +-----------+ |
      +------------------------+

Layered "icicle" diagrams

Layered "icicle" diagrams that use alignment/adjacency:

      +-------------------+
      |   encyclopedia    |
      +---------+---------+
      | science | culture |
      +---------+---+-----+
                |art|craft|
                +---+-----+

Outlines and tree views

Lists or diagrams that use indentation, sometimes called "outlines" or "tree views":

      encyclopedia
         science
         culture
            art
            craft

Nested parentheses

Nested parentheses, a correspondence first noticed by Sir Arthur Cayley

(science,(art,craft)culture)encyclopedia

or:

encyclopedia(culture(art,craft),science)

See also

Kinds of trees

• B-tree
• Dancing trees
• Left child-right sibling binary tree
• Tree (data structure)
• Tree (graph theory)
• Tree (set theory)

Related articles

• Data drilling
• Hierarchical model: clustering and query
• Tree testing (information architecture)

Further reading

Identification of some of the basic styles of tree structures can be found in:

• Jacques Bertin, Sémiologie graphique, 1967, Éditions Gauthier-Villars, Paris (2nd edition 1973, English translation 1983);
• Donald E. Knuth, The Art of Computer Programming, Volume I: Fundamental Algorithms, 1968, Addison-Wesley, pp. 309-310;
• Brian Johnson and Ben Shneiderman, Tree-maps: A space-filling approach to the visualization of hierarchical information structures, in Proceedings of IEEE Visualization (VIS), 1991, pp. 284-291;
• Peter Eades, Tao Lin, and Xuemin Lin, Two Tree Drawing Conventions, International Journal of Computational Geometry and Applications, 1993, volume 3, number 2, pp. 133-153.

External links

• Visualization of phylogenetic trees on the T-REX server
• Using a tree structure to design a business process - from the Society for Technical Communication
• Wikipedia tree hierarchy of categories and pages under Computing

References