Tree structure
From Wikipedia, the free encyclopedia
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 graph looks a bit like a tree, even though the tree is generally shown upside down compared with a real tree; that is to say 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).
Contents |
[edit] 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.)
[edit] 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
[edit] 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 that use enclosure/containment to show parenthood (for an interesting variation on this, see Treemaps):
+------encyclopedia------+
| +--culture--+ |
| science |art craft| |
| +-----------+ |
+------------------------+
- Layered "icicle" diagrams that use alignment/adjacency:
+-------------------+
| encyclopedia |
+---------+---------+
| science | culture |
+---------+---+-----+
|art|craft|
+---+-----+
- Diagrams that use indentation, sometimes called "outlines" or "tree views":
encyclopedia
science
culture
art
craft
- Nested parentheses, a correspondence first noticed by Sir Arthur Cayley
(science,(art,craft)culture)encyclopedia
Identification of some of these basic styles 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.
[edit] See also
- Kinds of trees
- B-tree
- Dancing trees
- Tree (data structure)
- Tree (graph theory)
- Tree (set theory)
- Tree (descriptive set theory)
- Related articles
[edit] 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
[edit] References
- ^ "What is the Document Object Model?" (html). W3C Architecture domain. http://www.w3.org/TR/DOM-Level-2-Core/introduction.html. Retrieved on 2006-12-05.
