Tree - Revision history

Brian: +cat:trees

2011-12-12T03:22:56Z

+cat:trees

Brian at 16:22, 31 October 2011

2011-10-31T16:22:09Z

Brian: /* Anatomy */

2011-05-30T20:53:46Z

‎Anatomy

Brian: /* Binary trees */

2011-05-17T05:06:11Z

‎Binary trees

Brian: /* Characterization */

2011-04-06T03:51:54Z

‎Characterization

Brian at 18:20, 12 March 2011

2011-03-12T18:20:32Z

Brian: /* Anatomy */ - oops

2011-03-12T08:09:40Z

‎Anatomy: - oops

Brian at 08:09, 12 March 2011

2011-03-12T08:09:13Z

Brian at 07:57, 12 March 2011

2011-03-12T07:57:26Z

Brian: /* Characterization */ - grammar

2011-03-12T07:55:52Z

‎Characterization: - grammar

← Older revision		Revision as of 03:22, 12 December 2011
Line 81:		Line 81:
	[[Category:Graph theory]]		[[Category:Graph theory]]
	[[Category:Pages needing diagrams]]		[[Category:Pages needing diagrams]]
		+	[[Category:Trees]]

@@ Line 72: / Line 72: @@
 * '''[[Lowest common ancestor]] (LCA) problem''': Given a pair of nodes in a tree, efficiently determine their lowest common ancestor, that is, the deepest node that is an ancestor of both given nodes. A variety of algorithms exist for this important problem.
 * It is easy to find the ''distance'' between any pair of nodes in a tree, weighted or unweighted, because there is only one path to consider, which may be found using depth-first search or breadth-first search.
-:* To find the ''diameter'' of a tree, pick any starting vertex <math>u</math>, find the vertex <math>v</math> furthest away from <math>u</math> using DFS or BFS (breaking ties arbitrarily), and then find the vertex <math>w</math> furthest away from <math>v</math>. The distance between <math>v</math> and <math>w</math> is the tree's diameter. ([[Tree/Diameter proof|proof]])
+:* To find the ''diameter'' of a tree, pick any starting vertex <math>u</math>, find the vertex <math>v</math> furthest away from <math>u</math> using DFS or BFS (breaking ties arbitrarily), and then find the vertex <math>w</math> furthest away from <math>v</math>. The distance between <math>v</math> and <math>w</math> is the tree's diameter.<ref name="diameter">Bang Ye Wu and Kun&ndash;Mao Chao. ''A note on Eccentricities, diameters, and radii''. Retrieved from http://www.csie.ntu.edu.tw/~kmchao/tree07spr/diameter.pdf</ref>
 :* In the ''dynamic distance query'' problem, we wish to be able to efficiently determine the distances between pairs of nodes in a tree, but we also want to be able to change the weights of edges. This problem is solved using the [[heavy-light decomposition]].
 * The ''maximum matching problem'', ''minimum vertex cover problem'', ''minimum edge cover problem'', and ''maximum independent set problem'' all admit simple [[dynamic programming]] solutions when the graph involved is a tree.
 [[Category:Graph theory]]
 [[Category:Pages needing diagrams]]

@@ Line 15: / Line 15: @@
 Some trees are '''rooted''', that is, they have one particular vertex designated the '''root'''. Others are '''unrooted''', perhaps because no significance can be attached to singling out one vertex to be a root. Here are examples, that serve to introduce and explain terminology:
 * In an organic tree, there are several points at which the trunk and its branches divide. Let these, along with the ground, and the endpoints of the smallest branches, be vertices, with the vertex at the ground being labelled the root, for obvious reasons, and let the trunk and branches be the edges. The significance of the rooting is that the trunk and all its branches are considered to emanate from the root (which makes sense given how trees actually grow). The vertices corresponding to the endpoints of the smallest branches, which always have degree one, are called '''leaves''', in strict analogy. The distance from the root node to any other node is sometimes called that node's '''height''', again in strict analogy, but, due to the practice in computer science of drawing trees upside-down, it is more commonly called the '''depth'''. The maximum height of any node in the tree is known as the tree's height.
-* The ''family tree'' consisting of all descendants of an individual: This, too, is named for its resemblance to an organic tree, and it is no surprise that it can be placed into analogy with a graph-theoretic tree as well. Let each person in the family tree be a vertex and let there be an edge between two vertices if one of the corresponding individuals is a child of the other. Label the vertex corresponding to the aforementioned individual as the root vertex. Then, all adjacent vertices represent that individual's child, and, in strict analogy, these nodes are said to be '''children''' of the root node. In general, in a rooted tree, if two nodes are adjacent, the one further away from the root is considered to be a child of the one closer, and the one closer is called the '''parent''' of the one further away. (A node will always have exactly one parent, unless it is the root.) Furthermore, given some node <math>u</math>, the node itself, its children, its children's children, and so on, are called the node's '''descendants'''; the term ''strict descendant'' is sometimes taken to mean the same but excluding <math>u</math> itself. Likewise, <math>u</math>, <math>u</math>'s parent, <math>u</math>'s parent's parent, and so on, are called '''ancestors''' (with the term ''strict ancestor'' being defined analogously). The root is ancestral to all nodes.
+* The ''family tree'' consisting of all descendants of an individual: This, too, is named for its resemblance to an organic tree, and it is no surprise that it can be placed into analogy with a graph-theoretic tree as well. Let each person in the family tree be a vertex and let there be an edge between two vertices if one of the corresponding individuals is a child of the other. Label the vertex corresponding to the aforementioned individual as the root vertex. Then, all adjacent vertices represent that individual's child, and, in strict analogy, these nodes are said to be '''children''' of the root node. In general, in a rooted tree, if two nodes are adjacent, the one further away from the root is considered to be a child of the one closer, and the one closer is called the '''parent''' of the one further away. (A node will always have exactly one parent, unless it is the root.) Furthermore, given some node <math>u</math>, the node itself, its children, its children's children, and so on, are called the node's '''descendants'''; the term ''proper descendant'' is sometimes taken to mean the same but excluding <math>u</math> itself. Likewise, <math>u</math>, <math>u</math>'s parent, <math>u</math>'s parent's parent, and so on, are called '''ancestors''' (with the term ''proper ancestor'' being defined analogously). The root is ancestral to all nodes.
 * In the ''tree of life'', each vertex represents a species and edges represent evolution of one species into another. The root of this tree is some universal common ancestor of life on Earth, and the leaves of this tree are either extant species or species that have gone extinct without radiating or transitioning to a newer species.
 * A corporate hierarchy can theoretically be represented by a rooted tree, where each employee is a vertex and a vertex's children are those vertices corresponding to the employees managed by subordinates, and the vertex corresponding to the CEO (or equivalent) is the root of the tree. Hierarchies in general are easily representable by trees.

@@ Line 29: / Line 29: @@
 Tree '''traversal''' is the act of visiting every vertex of a tree. Traversing a tree produces an ordering of the tree's vertices. If a tree has <math>N</math> nodes, then there are <math>N!</math> different orderings, but two are particularly important: '''preorder''' and '''postorder'''. In a preorder traversal, we perform a [[depth-first search]] starting from the tree's root, and a node is considered to be visited as soon as it is first pushed onto the stack. A postorder traversal is similar, but now a node is considered to be visited only after all its children have been visited. (Leaf nodes are still considered visited as soon as they are pushed on the stack, as they have no children.) In some trees, an order is already imposed on the children of any given vertex; that is, a node with multiple children has a well-defined first child, second child, and so on. In these case, preorder and postorder traversals always visit a node's children in order, and are unique for a given rooted tree.
-==Binary trees==
+==Binary and ''k''-ary trees==
 A '''binary tree''' is a rooted tree in which every vertex has at most two children, called ''left'' and ''right''. The subtree rooted at a node's left child is called the ''left subtree'', with ''right subtree'' defined analogously. Binary trees are of special interest because of their ability to organize data, as in [[binary search tree]]s and [[binary heap]]s.
@@ Line 43: / Line 43: @@
 A binary tree is said to be '''complete''' when levels 0 through <math>h-1</math> are completely filled, and all nodes on level <math>h</math> are as far to the left as possible. A complete binary tree will always have the minimum height possible. A binary tree is said to be '''balanced''' when all external nodes have similar height; if the heights of any two external nodes differ by at most one, it is said to be '''perfectly balanced'''. Balanced trees are useful for searching efficiently.
 ===Inorder traversal===

@@ Line 2: / Line 2: @@
 ==Characterization==
-For a simple graph, any two of these three statements, taken together, imply the third:
+For a simple graph, any two of these three statements, taken together, imply the third ([[Tree/Proof of properties of trees|proof]]):
 * The graph is connected.
 * The graph is acyclic.

@@ Line 6: / Line 6: @@
 * The graph is acyclic.
 * The number of vertices in the graph is exactly one more than the number of edges.
-This implies that when two of these conditions are known to hold, the graph is definitely a tree, and that all trees satisfy all three conditions (with the exception of the empty tree, that contains no nodes at all.)
+This implies that when two of these conditions are known to hold, the graph is definitely a tree, and that all trees satisfy all three conditions (with the exception of the empty tree, which contains no nodes at all, and is sometimes considered not to be a valid tree anyway).
 Additionally, the statement that there is exactly one path between any pair of vertices is also equivalent to the statement that the graph is a tree.
 ==Anatomy==
@@ Line 23: / Line 25: @@
 Any connected subgraph of a tree is itself a tree and is called a '''subtree''' of that tree, but in a rooted tree, the term is usually used in a restricted sense to denote a node <math>u</math> plus all of its descendants; this is referred to as ''the subtree rooted at <math>u</math>''. (The subtree rooted at the root is the tree itself.) We shall use the term in this restricted sense throughout this article. A subtree can correspond to, in the examples above, everything emanating from a specific branch of an organic tree, or all the descendants of one particular individual, or a clade (monophyletic taxon), or all the employees subject to a particular employee's authority.
 [[Category:Graph theory]]
 [[Category:Pages needing diagrams]]

@@ Line 18: / Line 18: @@
 * When a pair of parallel, closely spaced wooden boards with some nails hammered into them is immersed in a solution of water, soap, and glycerin, and then removed, a soap film will be formed that connects all the nails together without forming any cycles [http://cgg-journal.com/2001-2/01/CFIG14.gif]. This gives what is called a ''Steiner tree''. Again, this is an unrooted tree, as it makes no sense to label any particular vertex the root.
 The distinction between rooted and unrooted trees is somewhat artificial; we can always convert a rooted tree to an unrooted tree by forgetting which node is the root, and we may sometimes wish, in algorithms, to regard an unrooted tree as rooted by arbitrarily choosing a root.
 [[Category:Graph theory]]
 [[Category:Pages needing diagrams]]