Tree structure

Encyclopedia

A

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.

A tree structure is conceptual, and appears in several forms. For a discussion of tree structures in specific fields, see Tree (data structure)

for computer science: insofar as it relates to graph theory, see tree (graph theory)

, or also tree (set theory)

. Other related pages are listed below.

. 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

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.

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

knowledge, such as family tree

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

, 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

(

and telecommunications.)

For a formal definition see set theory

.

Almost always, these boil down to variations, or combinations,

of a few basic styles:

that use enclosure/containment to show parenthood, examples include TreeMaps

and fractal maps:

s":

.

or:

Also, trees can be represented radially

.

Related articles:

**tree structure**is a way of representing the hierarchicalHierarchy

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 superiorSuperior (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 ModelDocument Object ModelThe 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 ProjectOpen Directory ProjectThe 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, PSHPolythematic Structured Subject Heading SystemPolythematic 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 organizationOrganizationAn 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 treeBinary search treeIn 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 TreeRed-black treeA 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 treeAVL treeIn 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...

- binary search tree
- Biology: evolutionary tree
- Business: pyramid selling scheme
- Project management: work breakdown structureWork breakdown structureA 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 treesPhrase structure rulesPhrase-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...
- Sports: business chessBusiness chessBusiness 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 bracketsBracket (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 universeVon Neumann universeIn 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

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

encyclopedia

/ \

science culture

/ \

art craft

### Nested sets

Nested setsNested 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 viewTree 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 CayleyArthur 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

Radial tree

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

.

## See also

Kinds of trees:- B-treeB-treeIn 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 treeDecision treeA 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 treeLeft child-right sibling binary treeIn 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 drillingData drillingData drilling refers to any of various operations and transformations on tabular, relational, and multidimensional data...
- Hierarchical modelHierarchical modelA 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...

: clusteringHierarchical clusteringIn 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 queryHierarchical queryA 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)

### Further reading

Identification of some of the basic styles of tree structures can be found in:- Jacques BertinJacques BertinJacques 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*, Volume I: Fundamental Algorithms, 1968, Addison-Wesley, pp. 309–310;The Art of Computer ProgrammingThe Art of Computer Programming is a comprehensive monograph written by Donald Knuth that covers many kinds of programming algorithms and their analysis.... - Brian Johnson and Ben ShneidermanBen ShneidermanBen 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; - Peter EadesPeter EadesPeter D. Eades is an Australian computer scientist, a professor in the School of Information Technologies at the University of Sydney, known for his expertise in graph drawing....

, 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 CommunicationSociety for Technical CommunicationThe Society for Technical Communication is a professional society for the advancement of the theory and practice of technical communication.-Overview:...
- Wikipedia tree hierarchy of categories and pages under Computing