A (free) tree T is A simple graph such that for every pair of vertices v and w there is a unique path from v to w Rooted tree
A rooted tree is a tree
where one of its vertices is designated the root Level of a vertex and tree height Let T be a rooted tree: The level l(v) of a vertex v is the length of the simple path from v to the root of the tree The height h of a rooted tree T is the maximum of all level numbers of its vertices: h = max { l(v) } v V(T)
Example: the tree on the right has height 3 Organizational charts Huffman codes
On the left tree the word rate is encoded
001 000 011 100 On the right tree, the same word rate is encoded 11 000 001 10 7.2 Terminology
An internal vertex is a vertex that has at least one child A terminal vertex is a vertex that has no children The tree in the example has 4 internal vertices and 4 terminal vertices Subtrees
A subtree of a tree T is a tree T' such that
V(T') V(T) and E(T') E(T) Characterization of trees
Theorem 7.2.3 If T is a graph with n vertices, the following are equivalent: a) T is a tree b) T is connected and acyclic (“acyclic” = having no cycles) c) T is connected and has n-1 edges d) T is acyclic and has n-1 edges 7.3 Spanning trees
Given a graph G, a tree T is a
spanning tree of G if: T is a subgraph of G and T contains all the vertices of G Spanning tree search
Breadth-first search method
Depth-first search method (backtracking) 7.4 Minimal spanning trees
Given a weighted graph G, a
minimum spanning tree is a spanning tree of G that has minimum “weight” 1. Prim’s algorithm
Step 0: Pick any vertex as a Step 3: Repeat Step
starting vertex (call it a). T = 2, choosing the {a}. edge of smallest Step 1: Find the edge with weight that does not smallest weight incident to a. form a cycle until all Add it to T Also include in T vertices are in T. The the next vertex and call it b. resulting subgraph T Step 2: Find the edge of is a minimum smallest weight incident to spanning tree. either a or b. Include in T that edge and the next incident vertex. Call that vertex c.
2. Kruskal’s algorithm Step 1: Find the edge in Step 3: Repeat Step 2 the graph with smallest until you reach out to every weight (if there is more vertex of the graph. The than one, pick one at chosen edges form the random). Mark it with any given color, say red. desired minimum spanning tree. Step 2: Find the next edge in the graph with smallest weight that doesn't close a cycle. Color that edge and the next incident vertex. 7.5 Binary trees
A binary tree is a tree
where each vertex has zero, one or two children Full binary tree
A full binary tree is a
binary tree in which each vertex has two or no children. Full binary tree
Theorem 7.5.4: If T is a full
binary tree with k internal vertices, then T has k + 1 terminal vertices and the total number of vertices is 2k + 1. Example: there are k = 4 internal vertices (a, b, c and f) and 5 terminal vertices (d, e, g, h and i) for a total of 9 vertices. Height and terminal vertices
Theorem 7.5.6: If a binary tree of height h has t terminal vertices, then lg t < h, where lg is logarithm base 2. Equivalently, t < 2h. Example, h = 4 and t = 7. Then: t = 7 < 16 = 24 = 2h A case of equality
If all t terminal vertices of a
full binary tree T have the same level h = height of T, then t = 2h. Example: The height is h = 3, and the number of terminal vertices is t = 8 t = 8 = 23 = 2h Alphabetical order
Alphabetical or lexicographic order is the
order of the dictionary: a) start with an ordered set of symbols X = {a,b,c, …}. X can be infinite or finite. b) Let = x1x2…xm and = y1y2…yn be strings over X. Then define < if x1 < y1 or if xj= yj for all j, 1 < j < k, for some k such that 1 < k < min{m,n} and xj+1 < yj+1 or if m < n and xj = yj for all j, 1 < j < m Example of alphabetical order Let X = set of letters of the alphabet ordered according to precedence, i.e. a < b < c <… < x < y < z Let = arboreal and = arbiter. In this case, x1 = y1 = a, x2 = y2 = r x3 = y3 = b. So, we go the fourth letter: x4 = o and y4 = i. Since i < o we have that < . Binary search trees
Data are associated to Example
each vertex : "Computers are an important Order data technological tool" alphabetically, so that for each vertex v, data to the left of v are less than data in v and data to the right of v are greater than data in v 7.6 Tree Traversals
1: Pre-order traversal
2: In-order traversal More on tree traversals
3: Post-order traversal
4: Reverse post-order traversal Arithmetic expressions Standard: infix form (A+B) C – D/ E Fully parenthesized form (in -order & parenthesis): (((A + B) C) – (D / E)) Postfix form (reverse Polish notation): A B + C D E / - Prefix form (Polish notation): - + A B C / D E 7.7 Decision trees
A decision tree is a binary tree containing an
algorithm to decide which course of action to take. 7.8 Isomorphism of trees
Given two trees T1 and T2
T1 is isomorphic to T2 if we can find a one-to-one and onto function f :T1 → T2 that preserves the adjacency relation i.e. if v, w V(T1) and e = (v, w) is an edge in T1, then e’ = (f(v), f(w)) is an edge in T2. Isomorphism of rooted trees
Let T1 and T2 be rooted trees with roots r1 and
r2, respectively. T1 and T2 are isomorphic as rooted trees if there is a one-to-one function f: V(T1) V(T2) such that vertices v and w are adjacent in T1 if and only if f(v) and f(w) are adjacent in T2 f(r1) = r2 Example: T1 and T2 are isomorphic as rooted trees Isomorphism of binary trees
Let T1 and T2 be binary trees with roots r1 and
r2, respectively. T1 and T2 are isomorphic as binary trees if a) T1 and T2 are isomorphic as rooted trees through an isomorphism f, and b) v is a left (right) child in T1 if and only if f(v) is a left (right) child in T2 Note: This condition is more restrictive that isomorphism only as rooted trees. Left children must be mapped onto left children and right children must be mapped onto right children. Binary tree isomorphism
Example: the following two trees are
isomorphic as rooted trees, but not isomorphic as binary trees Summary of tree isomorphism There are 3 kinds of tree isomorphism Isomorphism of trees Isomorphism of rooted trees (root goes to root) Isomorphism of binary trees (left children go to left children, right children go to right children) Non-isomorphism of trees
Many times it may be easier to determine
when two trees are not isomorphic rather than to show their isomorphism. A tree isomorphism must respect certain properties, such as the number of vertices the number of edges the degrees of corresponding vertices roots must go to roots position of children, etc. Non-isomorphism of rooted trees
Theorem 7.8.7: There are four non-isomorphic
rooted trees with four vertices. The root is the top vertex in each tree. The degrees of the vertices appear in parenthesis Non-isomorphic binary trees
Theorem 7.8.12: There are C(2n,n) / (n+1) non-isomorphic binary trees with n vertices, n > 0, where C(2n,n) / (n+1) are the Catalan numbers Cn Catalan numbers (1)
1. Eugene Charles Catalan
1. Belgian mathematician, 1814-1894 2. Catalan numbers can be computed using this formula: 3. Cn = C(2n,n) / (n+1) for n > 0 The first few Catalan numbers are: 1. n =0 1 2 3 4 5 6 7 8 9 10 2. Cn = 1 1 2 5 14 42 132 429 1430 4862 16796 Applications of Catalan numbers
The number of ways in which a polygon with n+2
sides can be cut into n triangles The number of ways in which parentheses can be placed in a sequence of numbers, to be multiplied two at a time The number of rooted trivalent trees with n+1 vertices The number of paths of length 2n through an n by n grid that do not rise above the main diagonal The number of nonisomorphic binary trees with n vertices Isomorphism of binary trees
There is an algorithm to test whether two binary
trees are isomorphic or not. If the number of vertices in the two trees is n, and if the number of comparisons needed is an, it can be shown that an < 3n + 2. Theorem 7.8.14: The worst case of this algorithm is (n). 7.9 Game trees
Trees can be used to analyze all possible
move sequences in a game: Vertices are positions: a square represents one player and a circle represents another player An edge represents a move A path represents a sequence of moves
