CHAPTER 7Trees7.1. Trees7.1.1. Terminology. Let T be a graph with n vertices. The fol-lowing properties are equivalent:1. T is connected and acyclic (has no cycles).2. T is connected and has n − 1 edges.3. T is acyclic and has n − 1 edges.4. If v and w are vertices in T, there is a unique simple path fromv to w.A graph having any of the above equivalent properties is called afree tree or simply tree. A union of trees, or equivalently a simple graphwith no cycles, is called forest.A rooted tree is a tree in which a particular vertex is designated asthe root.rabcde fghijkl m n o pFigure 7.1. A rooted tree.The level of a vertex v is the length of the simple path from the rootto v. The height of a rooted tree is the maximum level of its vertices.Let T be a tree with root v0. Suppose that x, y and z are verticesin T and that (v0, v1, . . . , vn) is a simple path in T . Then:977.1. TREES 981. vn−1is the parent of vn.2. v0, v1, . . . , vn−1are ancestors of vn.3. vnis a child of vn−1.4. If x is an ancestor of y, y is a descendant of x.5. If x and y are children of z, x and y are siblings.6. If x has no children, it is called a terminal vertex or leaf.7. Ifx is not a terminal vertex, it is an internal or branch vertex.8. The subtree of T rooted at x is the graph (V, E), where V is xtogether with its descendants and E = edges of simple pathsfrom x to some vertex in E.7.1.2. Huffman Codes. Usually characters are represented in acomputer with fix length bit strings. Huffman codes provide an alter-native representation with variable length bit strings, so that shorterstrings are used for the most frequently used characters. As an exampleassume that we have an alphabet with four symbols: A = {a, b, c, d}.Two bits are enough for representing them, for instance a = 11, b = 10,c = 01, d = 00 would be one such representation. With this encodingn-character words will have 2n bits. However assume that they do notappear with the same frequency, instead some are more frequent thatothers, say a appears with a frequency of50%, b 30%, c 15% and d5%. Then the following enconding would be more efficient than the fixlength encoding: a = 1, b = 01, c = 001, d = 000. Now in average ann-character word will have 0.5n a’s, 0.3n b’s, 0.15n c’s and 0.05n d’s,hence its length will be 0.5n·1+0.3n·2+0.15n·3+0.05n·3 = 1.7n, whichis shorter than 2n. In general the length per character of a given en-coding with characters a1, a2, . . . , anwhose frequencies are f1, f2, . . . , fnis1FnXk=1fkl(ak) ,where l(ak) = length of akand F =Pnk=1fk. The problem now is,given an alphabet and the frequencies of its characters, find an optimalencoding that provides minimum average length for words.Fix length and Huffman codes can be represented by trees like infigure 7.2.The code of each symbol consists of the sequence of labels ofthe edges in the pathfrom the root to the leaf with the desired symbol.7.1.3. Constructing an Optimal Huffman Code. An optimalHuffman code is a Huffman code in which the average length of thesymbols isminimum. In general an optimal Huffman code can be made7.1. TREES 99ab d01 01 01abc d1 01 01 0Huffman codeFix length codecFigure 7.2. Fix length code and Huffman code.as follows. First we list the frequencies of all the codes and representthe symbols asvertices (which at the end will be leaves of a tree).Then we replace the two smallest frequencies f1and f2with their sumf1+ f2, and join the corresponding two symbols to a common vertexabove them by two edges, one labeled 0 and the other one labeled 1.Than common vertex plays the role of a new symbol with a frequencyequal to f1+ f2. Then we repeat the same operation with the resultingshorter list of frequencies until the listis reduced to one element andthe graph obtained becomes a tree.Example: Find the optimal Huffman code for the following table ofsymbols:character frequencya 2b 3c 7d 8e 12Answer: : The successive reductions of the list of frequencies are asfollows:2, 3|{z}5, 7, 8, 12 → 5, 7|{z}12, 8, 12 → 12, 8, 12Here we have a choice, we can choose to add the first 12 and 8, or8 and the second 12. Let’s choose theformer:12, 8|{z}20, 12 → 20, 12|{z}32→ 327.1. TREES 100The tree obtained is the following:a bde1111 00002378125122032cFigure 7.3. Optimal Huffman code 1.The resulting code is as follows:character codea 1111b 1110c 110d 10e 0The other choice yields the following:12, 8, 12|{z}20→ 20, 12|{z}32→ 32abc de1 0110013212 2057 812230Figure 7.4. Optimal Huffman code 2.7.1. TREES 101character codea 111b 110c 10d 01e