1. Huffman Encoding
(a) Create a Huffman Tree on the following distribution of characters:
{'a': 30, 'c': 40, 'e': 41, 'h': 82, 'i': 87, 'n': 52, 'o': 23, 'r': 68, 's': 44, 't': 75, ' ':16}
(the last character is a space, you can free to call it 'space' or ' ' in you tree). At each split, clearly indicate which side gets '0' and which gets '1'. At each split, you should assign '0' to the subtree with the lower total weight and '1' to the other subtree. If both subtrees have the same weight, you may assign '0' and '1' arbitrarily.
(b) Using your above tree, encode the sentence "this is a secret". Using your above tree, decode the sequence '0010111101110111100011101110000111000101111100'. (If there are trailing bits at the end of your decoding, explicitly state what the trailing part of the sequence is.)
(c) What is the runtime of building a huffman encoding? Once you already have an encoding, what is the runtime of encoding a document? Once you already have an encoding, what is the runtime of decoding a document?
Define the variables you think you need. If you feel you need (reasonable) clarifying assumptions, state them next to your answer. (Different answers will be allowed depending on your assumptions, but incorrect answers will not be given credit).
2. Suppose youve been given the following code:
class AVLNode {
public:
AVLNode * left, right, parent;
int value;
int height; // root node stores tree height; a single node tree has height 1
};
//Rotate left @ top.
//E.g. top->parent should remain an ancestor of all of its descendants
//and top's location in the tree should be replaced by top->right
void rotateLeft(AVLNode * top);
void rotateRight(AVLNode * top) { /* Implementation not shown */ }
(a) Implement rotateLeft in either psuedocode or C++ (not English):
(b) Given the following method signature:
//Double rotate @ top
//so that top->parent remains an ancestor of all of its descendants
//and so that this method would be appropriate to call for
//balancing a tree consisting of three nodes:
// {top, top->left, top->left->right}
//(though this should work when there are more nodes in the tree)
void doubleRotate_LeftKink(AVLNode * top);
void doubleRotate_RightKink(AVLNode * top) { /* Implementation not shown */ }
Implement doubleRotate_LeftKink in either psuedocode or C++ (not English). You may assume the setup on the previous page, and that rotateLeft and rotateRight have been implemented:
3. Implement insert for an AVL tree in either psuedocode or C++ (not English). You may assume the code from problem (2).
//returns false if data is already in the tree, otherwise inserts
//data into the tree and returns true.
bool insert(AVLNode * root, int data);
4. Why, historically, are the colors in RB trees Red and Black?
5. Implement insert for an RB tree in either psuedocode or C++ (not English). You may assume the code below. Assume that the rotation methods correctly change all the pointers, but do not change the colors. You may use both this and the next page for your answer.
class BSTNode {
public:
BSTNode * left, right, parent;
int value;
bool color; //false is red, true is black
};
void rotateLeft(BSTNode * top) { /* Implementation not shown */ }
void rotateRight(BSTNode * top) { /* Implementation not shown */ }
void doubleRotate_LeftKink(BSTNode * top) { /* Implementation not shown */ }
void doubleRotate_RightKink(BSTNode * top) { /* Implementation not shown */ }
bool insert(BSTNode * root, int data);