Transcript Trees
Trees Lecture 54 Section 11.5 Fri, Apr 28, 2006 Trees A graph is circuit-free (or acyclic) if it has no nontrivial circuits. A tree is a connected circuit-free graph. Examples of Trees A directory structure on a hard drive is a tree structure. Binary search tree. Expression tree. Huffman tree for data compression. Parse tree in a compiler. Directory Trees My Documents My Music My Pictures My Homework Math 262 Coms 262 Binary Search Trees 50 30 10 75 40 85 Expression Trees * + 10 15 25 Huffman Trees Consider the message ATTACK AT DAWN Count the frequencies of the letters. A–4 T–3 C–1 D–1 K–1 N–1 W–1 Huffman Trees 12 7 4 A 5 3 T 3 2 2 1 W 1 1 C D 1 K 1 N Huffman Trees 0 0 A 1 1 0 0 T 0 C 1 D 1 1 0 1 W K N Huffman Trees Encoding scheme: A = 00 T = 01 C = 1000 D = 1001 K = 110 N = 111 W = 101 Huffman Trees Encoding of the message ATTACK AT DAWN: 0001010010001100001100100101111. A total of 31 bits. ASCII would require 96 bits (12 chars). Compression ratio = 31/96 < 1/3. Parse Trees Consider the program statement if (x > 0) y = 1 The statement includes the following “terminals.” Keyword if Parentheses ( and ) Relative operators > and = Variables x and y Numbers 0 and 1 Parse Trees Parsing the statement uses the following “grammar” rules. stmt if ( rel-expr ) stmt stmt expr ; expr var = expr expr num rel-expr expr rel-op expr rel-op > Parse Trees stmt if ( rel-expr expr rel-op expr var > num var 0 y x stmt ) expr ; = expr num 1 Tree Characteristics Theorem: A tree must have at least one vertex of degree 1. Proof: Suppose not. Then each edge has degree at least 2. Using the idea in the proof for Euler circuits, if we pursue a walk, we will hit a dead-end only at a previously visited vertex. Proof This contradicts the property that trees are circuit free. Therefore, there must exist a vertex of degree 1. Tree Characteristics Theorem: If a tree has n vertices, then it has exactly n – 1 edges. Proof by induction. Base case: n = 1. The tree has 1 vertex and 0 edges, so the statement is true when n = 1. Proof Inductive case: Suppose the statement is true when n = k for some integer k 1. Let T be a tree with k + 1 vertices. Let v be a vertex of T of degree 1. Create a new graph T by removing v and its one incident edge. Then T is a tree with k vertices. Proof By the induction hypothesis, T has k – 1 edges. Therefore, T has k edges. Therefore, the statement is true for all n 1. Tree Characteristics Theorem: Let G be a graph with n vertices. If G has any two of the following three properties, then it has all three properties and G is a tree. G is circuit free. G is connected. G has n – 1 edges. Rooted Binary Trees A binary tree is rooted if it has one node designated the root. The other nodes are arranged in levels, depending on their distance from the root. Level 0 – The root. Level 1 – Nodes adjacent to the root. Level n – Nodes adjacent to level n – 1 nodes (but not the level n – 2 nodes). Counting Rooted Binary Trees How many rooted binary trees are there with n vertices? The tree must have 1 root vertex. That leaves n – 1 vertices for the left and right subtrees. Counting Rooted Binary Trees They can be divvied up in n ways: 0 on left, n – 1 on right. 1 on left, n – 2 on right. 2 on left. n – 3 on right. : n – 1 on left, 0 on right. Counting Rooted Binary Trees In each case, the number of such binary trees is the number of left subtrees of size k times the number of right subtrees of size n – k – 1. Counting Rooted Binary Trees Let Cn be the number of binary trees of size n. Then C0 1 (by definition ) n 1 Cn Ck Cn k 1 , for all n 1. k 0 Counting Rooted Binary Trees The first five terms are 1, 2, 5, 14, 41. The 6th term is 141 + 214 + 55 + 142 + 411 = 163. Is there a non-recursive formula? The Catalan Numbers These numbers turn out to be the Catalan numbers. The non-recursive formula is 2n n Cn n 1 Restricted Walks How many walks are there from A to B, by going only east and north? B N A Counting Unrooted Trees How many non-isomorphic unrooted trees are there with n vertices? n = 5: