Tree structure
Encyclopedia
A tree structure is a way of representing the hierarchical
Hierarchy
A hierarchy is an arrangement of items in which the items are represented as being "above," "below," or "at the same level as" one another...

nature of a structure
Structure
Structure is a fundamental, tangible or intangible notion referring to the recognition, observation, nature, and permanence of patterns and relationships of entities. This notion may itself be an object, such as a built structure, or an attribute, such as the structure of society...

in a graphical form. It is named a "tree structure" because the classic representation resembles a tree
Tree
A tree is a perennial woody plant. It is most often defined as a woody plant that has many secondary branches supported clear of the ground on a single main stem or trunk with clear apical dominance. A minimum height specification at maturity is cited by some authors, varying from 3 m to...

, 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.

A tree structure is conceptual, and appears in several forms. For a discussion of tree structures in specific fields, see Tree (data structure)
Tree (data structure)
In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.Mathematically, it is an ordered directed tree, more specifically an arborescence: an acyclic connected graph where each node has zero or more children nodes and at...

for computer science: insofar as it relates to graph theory, see tree (graph theory)
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...

, or also tree (set theory)
Tree (set theory)
In set theory, a tree is a partially ordered set In set theory, a tree is a partially ordered set (poset) In set theory, a tree is a partially ordered set (poset) (T, In set theory, a tree is a partially ordered set (poset) (T, ...

. Other related pages are listed below.

## Nomenclature and properties

Every finite tree structure has a member that has no superior
Superior (hierarchy)
In a hierarchy or tree structure of any kind, a superior is an individual or position at a higher level in the hierarchy than another , and thus closer to the apex. It is often used in business terminology to refer to people who are supervisors and in the military to people who are higher in the...

. 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 "node
Node (computer science)
A node is a record consisting of one or more fields that are links to other nodes, and a data field. The link and data fields are often implemented by pointers or references although it is also quite common for the data to be embedded directly in the node. Nodes are used to build linked, often...

s".
Nodes without children are called leaf nodes, "end-nodes", or "leaves".

The names of relationships between nodes are modeled after family relations. 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's "parent" is a node one step higher in the hierarchy (i.e. closer to the root node) and lying on the same branch.
• "Sibling" ("brother" or "sister") nodes share the same parent node.
• A node's "uncles" are siblings of that node's parent.
• 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", which is their parent and thus one of their ancestors. Also, "encyclopedia", being the root of the tree, is the ancestor of "science", "culture", "art" and "craft". Finally, "science", "art" and "craft", being leaves, are ancestors of no other node.

Tree structures are used to depict all kinds of taxonomic
Taxonomy
Taxonomy is the science of identifying and naming species, and arranging them into a classification. The field of taxonomy, sometimes referred to as "biological taxonomy", revolves around the description and use of taxonomic units, known as taxa...

knowledge, such as family tree
Family tree
A family tree, or pedigree chart, is a chart representing family relationships in a conventional tree structure. The more detailed family trees used in medicine, genealogy, and social work are known as genograms.-Family tree representations:...

s, the biological evolutionary tree, the evolutionary tree of a language family, the grammatical structure of a language (a key example being S → NP VP, meaning a sentence is a noun phrase and a verb phrase, with each in turn having other components which have other components), the way web pages are logically ordered in a web site, mathematical trees of integer sets
Tree of primitive Pythagorean triples
In mathematics, a Pythagorean triple is a set of three positive integers a, b, and c having the property that they can be respectively the two legs and the hypotenuse of a right triangle, thus satisfying the equation a^2+b^2=c^2; the triple is said to be primitive if and only if a, b, and c share...

, et cetera.

In a tree structure there is one and only one path
Path (graph theory)
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...

from any point to any other point.

Tree structures are used extensively in computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

(see Tree (data structure)
Tree (data structure)
In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.Mathematically, it is an ordered directed tree, more specifically an arborescence: an acyclic connected graph where each node has zero or more children nodes and at...

and telecommunications.)

For a formal definition see set theory
Tree (set theory)
In set theory, a tree is a partially ordered set In set theory, a tree is a partially ordered set (poset) In set theory, a tree is a partially ordered set (poset) (T, In set theory, a tree is a partially ordered set (poset) (T, ...

.

## Examples of tree structures

• Internet:
• usenet hierarchy
• Document Object Model
Document Object Model
The Document Object Model is a cross-platform and language-independent convention for representing and interacting with objects in HTML, XHTML and XML documents. Aspects of the DOM may be addressed and manipulated within the syntax of the programming language in use...

's logical structure, Yahoo!
Yahoo!
Yahoo! Inc. is an American multinational internet corporation headquartered in Sunnyvale, California, United States. The company is perhaps best known for its web portal, search engine , Yahoo! Directory, Yahoo! Mail, Yahoo! News, Yahoo! Groups, Yahoo! Answers, advertising, online mapping ,...

subject index, Open Directory Project
Open Directory Project
The Open Directory Project , also known as Dmoz , is a multilingual open content directory of World Wide Web links. It is owned by Netscape but it is constructed and maintained by a community of volunteer editors.ODP uses a hierarchical ontology scheme for organizing site listings...

• Information management: Dewey Decimal System, PSH
Polythematic Structured Subject Heading System is a bilingual Czech-English controlled vocabulary of subject headings developed and maintained by the National Technical Library in Prague...

• Management: hierarchical organization
Organization
An organization is a social group which distributes tasks for a collective goal. The word itself is derived from the Greek word organon, itself derived from the better-known word ergon - as we know `organ` - and it means a compartment for a particular job.There are a variety of legal types of...

al structures
• Computer Science:
• binary search tree
Binary search tree
In computer science, a binary search tree , which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structurewhich has the following properties:...

• Red-Black Tree
Red-black tree
A red–black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer and named "symmetric binary B-tree," but acquired its modern name in a paper in 1978 by...

• AVL tree
AVL tree
In computer science, an AVL tree is a self-balancing binary search tree, and it was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. Lookup, insertion, and deletion all take O time in both the average and worst...

• Biology: evolutionary tree
• Project management: work breakdown structure
Work breakdown structure
A work breakdown structure , in project management and systems engineering, is a deliverable oriented decomposition of a project into smaller components. It defines and groups a project's discrete work elements in a way that helps organize and define the total work scope of the project.A work...

• Linguistics (syntax): Phrase structure trees
Phrase structure rules
Phrase-structure rules are a way to describe a given language's syntax. They are used to break down a natural language sentence into its constituent parts namely phrasal categories and lexical categories...

Business chess is a variant of chess played in teams. It was invented in 1992 by Dr. Grachya Ovakimyan of Moscow with the aim of making chess more entertaining and spectacular....

, playoffs brackets
Bracket (tournament)
A bracket is a tree diagram that represents the series of games played during a tournament, named as such because it appears to be a large number of interconnected brackets....

• Mathematics: Von Neumann universe
Von Neumann universe
In set theory and related branches of mathematics, the von Neumann universe, or von Neumann hierarchy of sets, denoted V, is the class of hereditary well-founded sets...

## 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, that connect nodes together with line segments:
```
encyclopedia
/      \
science  culture
/   \
art  craft
```

### Nested sets

Nested sets
Nested set model
The nested set model is a particular technique for representing nested sets in relational databases.The term was apparently introduced by Joe Celko; others describe the same technique without naming it or using different terms...

that use enclosure/containment to show parenthood, examples include TreeMaps
Treemapping
In information visualization and computing, treemapping is a method for displaying hierarchical data by using nested rectangles.- Main idea :...

and fractal maps:
```
+------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 view
Tree view
A tree view or an outline view is a graphical user interface element that presents a hierarchical view of information. Each item can have a number of subitems...

s":
```
encyclopedia
science
culture
art
craft
```

### Nested parentheses

A correspondence to nested parentheses was first noticed by Sir Arthur Cayley
Arthur Cayley
Arthur Cayley F.R.S. was a British mathematician. He helped found the modern British school of pure mathematics....

.

```
(science,(art,craft)culture)encyclopedia
```

or:
```
encyclopedia(culture(art,craft),science)
```

Also, trees can be represented radially
A radial tree, or "radial map", is a method of displaying a tree structure in a way that expands outwards, radially. It is one of many ways to visually display a tree., with examples extending back to the early 20th century...

.

Kinds of trees:
• B-tree
B-tree
In computer science, a B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children...

• Dancing trees
• Decision tree
Decision tree
A decision tree is a decision support tool that uses a tree-like graph or model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm. Decision trees are commonly used in operations research, specifically...

• Left child-right sibling binary tree
Left child-right sibling binary tree
In computer science, a left child-right sibling binary tree is a binary tree representation of a k-ary tree. The process of converting from a k-ary tree to an LC-RS binary tree is not reversible in general without additional information....

• Tree (data structure)
Tree (data structure)
In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.Mathematically, it is an ordered directed tree, more specifically an arborescence: an acyclic connected graph where each node has zero or more children nodes and at...

• Tree (graph theory)
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...

• Tree (set theory)
Tree (set theory)
In set theory, a tree is a partially ordered set In set theory, a tree is a partially ordered set (poset) In set theory, a tree is a partially ordered set (poset) (T, In set theory, a tree is a partially ordered set (poset) (T, ...

Related articles:
• Data drilling
Data drilling
Data drilling refers to any of various operations and transformations on tabular, relational, and multidimensional data...

• Hierarchical model
Hierarchical model
A hierarchical database model is a data model in which the data is organized into a tree-like structure. The structure allows representing information using parent/child relationships: each parent can have many children, but each child has only one parent...

: clustering
Hierarchical clustering
In statistics, hierarchical clustering is a method of cluster analysis which seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into two types:...

and query
Hierarchical query
A hierarchical query is a type of SQL query that handles hierarchical model data.Standard SQL specifies hierarchical queries by way of recursive common table expressions...

• Tree testing (information architecture)

Identification of some of the basic styles of tree structures can be found in:
• Jacques Bertin
Jacques Bertin
Jacques Bertin was a French cartographer and theorist, known from his book Semiologie Graphique , edited in 1967...

, Sémiologie graphique, 1967, Éditions Gauthier-Villars, Paris (2nd edition 1973, English translation 1983);
• Donald E. Knuth, The Art of Computer Programming
The Art of Computer Programming
The Art of Computer Programming is a comprehensive monograph written by Donald Knuth that covers many kinds of programming algorithms and their analysis....

, Volume I: Fundamental Algorithms, 1968, Addison-Wesley, pp. 309–310;
• Brian Johnson and Ben Shneiderman
Ben Shneiderman
Ben Shneiderman is an American computer scientist, and professor for Computer Science at the Human-Computer Interaction Laboratory at the University of Maryland, College Park...

, Tree-maps: A space-filling approach to the visualization of hierarchical information structures, in Proceedings of IEEE Visualization (VIS), 1991, pp. 284–291;