Part A: B-tree ------- Understand B-trees from class, including insertion and deletion. In the B-tree below, to indicate X and Y are IN THE SAME NODE, we use notation: X-Y or X--Y or X---Y etc. I-------N / | \ D K Q / \ / \ / \ A-B E-G J M P S--T A LEVEL-ORDER traversal of the above B-tree is: I.N.D.K.Q.A.B.E.G.J.M.P.S.T Q0: Do a level-order traversal of the tree: Use a dot between keys, as above. TRY THE TRAVERSAL FIRST, then... Check your solution is : 10.20.5.7.15.30.57.2.6.8.9.11.17.25.29.40.59 For all remaining questions: - BTree1 -Once the insertion/deletion is complete, do a level-order traversal of the resulting tree, putting a dot between keys like above. Q1: Do an level-order traversal of the 2-3 tree (B-Tree order 3) in: BTree1 TRY THE TRAVERSAL FIRST, then... Check your solution is : 50.30.41.70.90.10.20.34.37.47.60.80.97.100 Q2: Insert 95 into the 2-3 tree (B-Tree order 3) in: BTree1 Use "rotation with sibling" WHEN POSSIBLE; otherwise use node splitting (push up to parent). THEN, insert 93 into the resulting B-tree. Use "rotation with sibling" WHEN POSSIBLE; otherwise use node splitting (push up to parent). Q3: Delete 70 from the ORIGINAL 2-3 tree (B-Tree order 3) in: BTree1 Do the deletion using the method described in class--but you must use the inorder PREDECESSOR as the replacement key. (see below for more on inorder predecessor). Q4: Delete 70 from the ORIGINAL 2-3 tree (B-Tree order 3) in: BTree1 Do the deletion using the method described in class--but you must use the inorder SUCCESSOR as the replacement key. (see below for more on inorder successor). ------------------------------------------------------------------------ INORDER PREDECESSOR/SUCCESSOR: As discussed in class... One way to find the inorder predecessor/successor of key X: -Print all the keys of the tree in order (sorted). i.e., do an inorder traversal. -X's inorder predecessor is the key that is printed JUST BEFORE X. -X's inorder successor is the key that is printed JUST AFTER X. Part B: Huffman ------- 0. Consider the first letter of your CS userid (login name). Use this letter to determine your NUMBER for this lab as follows: First Letter of Userid Number ---------------------- ------ a,b,c 1 d,e,f 2 g,h,i 3 j,k,l 4 m,n,o 5 p,q,r 6 s,t 7 u,v,w 8 x,y,z 9 sample answer structure: 0. My number is: XXXX 1. My tree has XXXX nodes. Its height is XXXX. 2. XXXX 3. XXXX Copy it to your filespace, and complete it by replacing XXXX with the correct answer for each question. 1. Consider an alphabet containing only the following 11 characters, with the given frequencies: Char Freq ---- ---- _ 99 (the underscore character) a 10 d 9 e 8 h 7 i 6 n 5 r 4 (choose r before 0 when making tree) o 4 s 2 t 1 Construct a huffman tree for the alphabet using the method from T-22 in class notes, as follows. When pairing 2 items, the one with the smaller frequency goes on the left, and its arc has label 1. If two items with the SAME frequency are being paired, then this is how you must determine which one goes on the left: -if both items are characters in the alphabet above, then the one that is smaller, in alphabetical order, as given above, goes on the left. -if one is a character of the alphabet, and the other is a created node, then the character goes on the left -if both are created nodes, then the one was the one created first goes on the left. If you are trying to choose between 2 items on the list which have the same frequency, choose this one: -the one that existed on the list first (e.g., if one is a character of the alphabet, and one is a created node, choose the character first). How many nodes does your Huffman tree have? What is your tree's height? 2. Give the encoding for the word that corresponds to your NUMBER, which you found in question 0. 1. tarnished 2. ordinates 3. adhesion 4. handiest 5. hairnets 6. hardnose 7. antihero 8. nerdish 9. hinders 3. Find the phrase that corresponds to your NUMBER by decoding the code that corresponds to your NUMBER. 1. 1011111100101001100111101101001100001000110111010101001011110000101111110111001010101101000101100111101110011101100111110110110100001010101111 2. 11101011111111011010000110110111011001010100101100100011000010011110101110101010011111000001001111101110110010101011100111110010101111001 3. 1011111100101001100100011000010101011101011110110010101000001011101100111101101010100101100101010110010011111000011011011101100 4. 101110110011110011010011001101100001001101010110101110010111111110000101110011011000001011111100101001000010001101101011111100 5. 10111111001010011001000110110101110101001011111011011111011000010101011001011101100100011011010111110101000010111001011111100101001011010101101100001011100 6. 10000101010110100101100101010110100011011100100110001100001111011111010010111110110111110110000101010010100110110100011000010101011100 7. 10111111001010010110100011001101010000101111101110010011101100001010100101000110000010110100011111011101011111010100101011011110011101101110110010101011100 8. 1000110110100001111011111010010110110011011000010001011001000110110100001011100111100110001101101000001011111100101011011011001011101100110110110101111101110 9. 111101110101111101010110100011101100110111001011011111011000010101001010001100000101110101111100011000010100101110110010001101101010101110