Tree structure - AbsoluteAstronomy.com

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)

and telecommunications.)

For a formal definition see set theory

Tree (set theory)

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
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
Business: pyramid selling scheme
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...
Sports: business chess
Business chess
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

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



        encyclopedia

          /      \

      science  culture

                /   \

              art  craft

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

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