FACTOID # 6: Michigan is ranked 22nd in land area, but since 41.27% of the state is composed of water, it jumps to 11th place in total area.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Tree structure

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. A hierarchy (in Greek hieros, sacred, and arkho, rule) is a system of ranking and organizing things or people. ... The structure of a thing is how the parts of it relate to each other, how it is put together. This contrast with process, which is how the thing works; but process requires a viable structure. ... The coniferous Coast Redwood, the tallest tree species on earth A tree can be defined as a large, perennial, woody plant. ...


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 is a set of trees). A diagram of a graph with 6 vertices and 7 edges. ... A tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ... In mathematics and computer science, graph theory studies the properties of graphs. ... A simple directed acyclic graph In mathematics, a directed acyclic graph, also called a dag or DAG, is a directed graph with no directed cycles; that is, for any vertex v, there is no directed path starting and ending on v. ... In the mathematical field of graph theory the degree or valency of a vertex v is the number of edges incident to v (with loops being counted twice). ... A tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ...


Every finite tree structure has a member that has no superior. This member is called the "root" or root node. The converse is not true: infinite tree structures need not have a root node. In mathematics, a set is called finite if and only if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ... In a hierarchical tree structure of any kind, a superior is higher in the hierarchy and thus closer to the apex than the subordinate ones. ... A root node is a specially chosen node in a tree data structure at which all operations on the tree begin. ...

Binary tree structure illustration
Illustration: A tree structure showing the possible hierarchical organization of an encyclopedia. This specific example happens to be a complete binary tree, which means all nodes have exactly zero or two child nodes. An Example of a tree in the meaning of a hierarchical (data) structure, in this specific case a binary tree. ... In computer science, a binary tree is an ordered tree data structure in which each node has at most two children. ...

The lines connecting elements are called "branches," the elements themselves are called "nodes." Nodes without children are called "end-nodes" or "leaves." The term node can refer to: Node, a spatial locus along a standing wave where the wave has minimal amplitude. ...


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. However, nowadays, in computer science at least, the gender-neutral names "parent" and "child" have largely displaced the older "father" and "son" terminology. Professor Avram Noam Chomsky, Ph. ...


The starting node is often called the "root."

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

Illustration: The original Encyclopédie actually used a tree diagram to show which way its subjects were ordered, though not a binary tree.
Illustration: The original Encyclopédie actually used a tree diagram to show which way its subjects were ordered, though not a binary tree.

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. Download high resolution version (1071x1407, 313 KB)Info: Figurative System of organisation of human knowledge from the Encyclopédie. ... Download high resolution version (1071x1407, 313 KB)Info: Figurative System of organisation of human knowledge from the Encyclopédie. ... Fig. ... Taxonomy (from Greek ταξινομία (taxinomia) from the words taxis = order and nomos = law) may refer to either the classification of things, or the principles underlying the classification. ... The evolutionary tree of living things is currently supposed to run something along the lines of that listed below. ...


Trees have a number of interesting properties:

  • The root node, i.e., the base node, is an ancestor of all the other nodes.
  • 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. In mathematics, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the successor vertex. ... Wikibooks Wikiversity has more about this subject: School of Computer Science Open Directory Project: Computer Science Downloadable Science and Computer Science books Collection of Computer Science Bibliographies Belief that title science in computer science is inappropriate nacho Categories: Computer science ... Telecommunication is the extension of communication over a distance. ...


Examples of tree structures

A newsgroup is a repository, usually within the Usenet system, for messages posted from many users at different locations. ... The Open Directory Project (ODP), also known as DMoz (for Directory. ... The Dewey Decimal Classification (DDC, also called the Dewey Decimal System) is a system of library classification developed by Melvil Dewey (1851–1931) in 1876, and since greatly modified and expanded in the course of the twenty-two major revisions which have occurred up until 2004. ... An organization (U.S. spelling) or organisation (U.K. spelling) is a formal group of people with one or more shared goals. ... In computer science, a binary search tree (BST) is a binary tree where every node has a value, every nodes left subtree contains only values less than or equal to the nodes value, and every nodes right subtree contains only values that are greater than or equal. ... The evolutionary tree of living things is currently supposed to run something along the lines of that listed below. ... Image File history File links File history Legend: (cur) = this is the current file, (del) = delete this old version, (rev) = revert to this old version. ... Image File history File links File history Legend: (cur) = this is the current file, (del) = delete this old version, (rev) = revert to this old version. ... For the ecclesiastical use of this term, see primate (religion) Families 13, See classification A primate is any member of the biological order Primates, the group that contains all lemurs, monkeys, and apes, including humans. ... A pyramid scheme is a business model that involves the exchange of money primarily for enrolling other people into the scheme, usually without any product or service being delivered. ... In project management, a work breakdown structure (WBS) is an exhaustive, hierarchical (from general to specific) tree structure of deliverables and tasks that need to be performed to complete a project. ...

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":
 encyclopedia science culture art craft 

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.

Donald Knuth Donald Ervin Knuth (born January 10, 1938) is a renowned computer scientist and Professor Emeritus at Stanford University. ... Cover of books The Art of Computer Programming is a comprehensive monograph written by Donald Knuth which covers many kinds of programming algorithms and their analysis. ... Ben Shneiderman (born August 21, 1947) is a American computer scientist. ... The Institute of Electrical and Electronics Engineers or IEEE (pronounced as eye-triple-ee) is an international non-profit, professional organization incorporated in the State of New York, United States. ...

Related terms


  Results from FactBites:
 
Tree structure - Wikipedia, the free encyclopedia (598 words)
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).
Tree data structure - Wikipedia, the free encyclopedia (458 words)
In computer science, a tree is a widely-used computer data structure that emulates a tree structure with a set of linked nodes.
In graph theory, a tree is a connected acyclic graph.
There are many different ways to represent trees; common representations represent the nodes as records allocated on the heap with pointers to their children, their parents, or both, or as items in an array, with relationships between them determined by their positions in the array (e.g., binary heap).
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m