Trees (Ch. 9.2) Longin Jan Latecki Temple University based on slides by Simon Langley and Shang-Hua TengBasic Data Structures - TreesTrees - TerminologyTypes of TreeBinary Search TreesSlide 6This is NOT a binary search treeTry it!!Searching a binary search treeSlide 10Slide 11Insertion in a binary search tree: we need to search before we insertInsertionComparison – Insertion in an ordered listData CompressionData Compression: A Smaller ExampleHow to decode?Prefix CodesPrefix codes allow easy decodingPrefix codesSome PropertiesOptimal Prefix Coding ProblemGreedy AlgorithmsGreedy algorithmsDavid Huffman’s ideaBuilding the Encoding TreeSlide 27Slide 28Slide 29Slide 30Trees (Ch. 9.2) Longin Jan LateckiTemple University based on slides bySimon Langley and Shang-Hua TengBasic Data Structures - TreesInformal: a tree is a structure that looks like a real tree (up-side-down)Formal: a tree is a connected graph with no cycles.Trees - Terminologyxb e mc d arootleafheight=3size=7Every node must have its value(s)Non-leaf node has subtree(s)Non-root node has a single parent nodeA parent may have 0 or more childrenvaluesubtreenodesTypes of TreeBinary Treem-ary TreesEach node has at most 2 sub-treesEach node has at most m sub-treesBinary Search TreesA binary search tree:… is a binary tree. if a node has value N, all values in its left sub-tree are less than or equal to N, and all values in its right sub-tree are greater than N.inorder (t) if t != NIL: { inorder (left[t]);write (label[t]);inorder (right[t]); }Inorder Traversal is an algorithm which visits each node of a tree after its left subtree and before its right subtree. It shows the values stored in a binary search tree in order.This is NOT a binary search tree54 73 2 8 9Try it!!Build binary search trees for the following input sequences•7, 4, 2, 6, 1, 3, 5, 7•7, 1, 2, 3, 4, 5, 6, 7•7, 4, 2, 1, 7, 3, 6, 5•1, 2, 3, 4, 5, 6, 7, 8•8, 7, 6, 5, 4, 3, 2, 1Searching a binary search treesearch(t, s) {If(s == label(t)) return t;If(t is leaf) return nullIf(s < label(t))search(t’s left tree, s)elsesearch(t’s right tree, s)} hTime per levelO(1)O(1)Total O(h)Searching a binary search treesearch( t, s ) { while(t != null) { if(s == label(t)) return t; if(s < label(t) t = leftSubTree(t); else t = rightSubTree; } return null; hTime per levelO(1)O(1)Total O(h)Here’s another function that does the same (we search for label s): TreeSearch(t, s) while (t != NULL and s != label[t]) if (s < label[t]) t = left[t]; else t = right[t]; return t;Insertion in a binary search tree:we need to search before we insert53 82 4 7 9Time complexity?Insert 66666Insert 11111111O(height_of_tree)O(log n) if it is balancedn = size of the treealways insert to a leafInsertioninsertInOrder(t, s){ if(t is an empty tree) // insert here return a new tree node with value s else if( s < label(t)) t.left = insertInOrder(t.left, s ) else t.right = insertInOrder(t.right, s) return t }Comparison –Insertion in an ordered listInsert 6Time complexity?2 3 4 5 7986 6 6 6 6O(n) n = size of the listinsertInOrder(list, s) { loop1: search from beginning of list, look for an item >= s loop2: shift remaining list to its right, start from the end of list insert s} 6 7 8 9Suppose we have 1000000000 (1G) character data file that we wish to include in an email.Suppose file only contains 26 letters {a,…,z}.Suppose each letter in {a,…,z} occurs with frequency f.Suppose we encode each letter by a binary codeIf we use a fixed length code, we need 5 bits for each characterThe resulting message length isCan we do better?Data Compression zbafff 5Data Compression: A Smaller ExampleSuppose the file only has 6 letters {a,b,c,d,e,f} with frequenciesFixed length 3G=3000000000 bitsVariable length 11001101111100101010110001101000100005.09.16.12.13.45.fedcbaFixed length Variable length G24.2405.409.316.312.313.145. ------How to decode?At first it is not obvious how decoding will happen, but this is possible if we use prefix codesPrefix CodesNo encoding of a character can be the prefix of the longer encoding of another character: we could not encode t as 01 and x as 01101 since 01 is a prefix of 01101By using a binary tree representation we generate prefix codes with letters as leaveseatns0 1111000Prefix codes allow easy decodingeatns0 1111000Decode:11111011100s 1011100sa 11100san 0sanePrefix codesA message can be decoded uniquely.Following the tree until it reaches to a leaf, and then repeat!Draw a few more tree and produce the codes!!!Some PropertiesPrefix codes allow easy decodingAn optimal code must be a full binary tree (a tree where every internal node has two children)For C leaves there are C-1 internal nodesThe number of bits to encode a file is ccfTTCclength )()B( -where f(c) is the freq of c, lengthT(c) is the tree depth of c, which corresponds to the code length of cOptimal Prefix Coding ProblemInput: Given a set of n letters (c1,…, cn) with frequencies (f1,…, fn).Construct a full binary tree T to define a prefix code that minimizes the average code length iTniicfT length )Average(1-Greedy AlgorithmsMany optimization problems can be solved using a greedy approach•The basic principle is that local optimal decisions may be used to build an optimal solution•But the greedy approach may not always lead to an optimal solution overall for all problems•The key is knowing which problems will work with this approach and which will notWe study•The problem of generating Huffman codesGreedy algorithmsA greedy algorithm always makes the choice that looks best at the moment•My everyday examples: •Driving in Los Angeles, NY, or Boston for that matter•Playing cards•Invest on stocks•Choose a university•The hope: a locally optimal choice will lead to a globally optimal solution•For some problems, it worksGreedy algorithms tend to be easier to codeDavid Huffman’s ideaA Term paper at MITBuild the tree (code) bottom-up in a greedy fashionEach tree has a weight in its root and symbols as its leaves.We start with a forest of one vertex trees representing the input symbols.We recursively merge two trees whose sum of weights is minimal until we have only one tree.Building the Encoding
View Full Document