EECE 330 Chapter, Fall 2011

EECE 330 Data Structures & Algorithms Binary Search Trees Binary Search Trees © Hassan Artail American University of Beirut Binary Search Trees BST Property: All elements stored in the left subtree of a node with value K have values < K. All elements stored in the right subtree of a node with value K have values  K. BST ADT(1) // BST implementation for the Dictionary ADT template <class Key, class Elem, class KEComp, class EEComp> class BST : public Dictionary<Key, Elem, KEComp, EEComp> {//Private Data and Helper Functions private: BinNode<Elem>* root; // Root of the BST int nodecount; // Number of nodes void clearhelp(BinNode<Elem>*); BinNode<Elem>* inserthelp(BinNode<Elem>*, const Elem&); BinNode<Elem>* deletemin(BinNode<Elem>*,BinNode<Elem>*&); BinNode<Elem>* removehelp(BinNode<Elem>*, const Key&, BinNode<Elem>*&); bool findhelp(BinNode<Elem>*, const Key&, Elem&) const; void printhelp(BinNode<Elem>*, int) const; BST ADT(2) public: BST() { root = NULL; nodecount = 0; } ~BST() { clearhelp(root); } void clear() { clearhelp(root); root = NULL; nodecount = 0; } bool insert(const Elem& e) { root = inserthelp(root, e); nodecount++; return true; } bool remove(const Key& K, Elem& e) { BinNode<Elem>* t = NULL; //we check for null below root = removehelp(root, K, t);//root may change if (t == NULL) return false; e = t->val(); // t points to a floating node now, get the nodecount--; // value that it points to before deleting it delete t; //Now, we can get rid of it return true; } Reminder • Always pass objects to functions by reference • If we are passing pointers to objects – If we are changing the pointers within the function, then pass the reference to the pointer. – Otherwise, pass the pointer itself BST ADT(3) bool removeMin(Elem& e) { // Delete node with record having minimum key value if (root == NULL) return false; // Empty BinNode<Elem>* t; // return pointer to node with minimum value root = deletemin(root, t); e = t->val(); // Get the value of t before deleting it delete t; nodecount--; return true; } bool find(const Key& K, Elem& e) const { return findhelp(root, K, e); } int size() { return nodecount; } void print() const { if (root == NULL) cout << "The BST is empty.\n"; else printhelp(root, 0); } BST Search template <class Key, class Elem, class KEComp, class EEComp> bool BST<Key, Elem, KEComp, EEComp>:: findhelp(BinNode<Elem>* subroot, const Key& K, Elem& e) const { if (subroot == NULL) return false; else if (KEComp::lt(K, subroot->val())) return findhelp(subroot->left(), K, e); else if (KEComp::gt(K, subroot->val())) return findhelp(subroot->right(), K, e); //found it. Get its value e which will traverse through the // chain of recursive calls all the way to the calling function else { e = subroot->val(); return true; } } 34 54 77 30 25 28 27 16 29 BST Insert (1) BST Insert (2) template <class Key, class Elem, class KEComp, class EEComp> BinNode<Elem>* BST<Key,Elem,KEComp,EEComp>:: inserthelp(BinNode<Elem>* subroot, const Elem& val) { if (subroot == NULL) // Empty: create node // the returned node becomes an argument to setLeft or setRight return new BinNodePtr<Elem>(val,NULL,NULL); // application of EEComp: comparing node values (records) if (EEComp::lt(val, subroot->val())) subroot->setLeft(inserthelp(subroot->left(), val)); else subroot->setRight( inserthelp(subroot->right(), val)); // Return subtree with node inserted return subroot; } 34 54 77 30 25 28 27 16 29 Remove Minimum Value template <class Key, class Elem, class KEComp, class EEComp> BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>:: deletemin(BinNode<Elem>* subroot, BinNode<Elem>*& min) { if (subroot->left() == NULL) { min = subroot; return subroot->right(); } else { // Minimum value is always found as the left-most node subroot->setLeft( deletemin(subroot->left(), min)); return subroot; // in the last step into the recursion, the original subroot will be returned } } 20 9 5 5 10 subroot BST Remove (1) BST Remove (2) template <class Key, class Elem, class KEComp, class EEComp> BinNode<Elem>* BST<Key,Elem,KEComp,EEComp>:: removehelp(BinNode<Elem>* subroot, const Key& K, BinNode<Elem>*& t) { //t is the node to remove (if we find it using K) if (subroot == NULL) return NULL; else if (KEComp::lt(K, subroot->val())) subroot->setLeft( removehelp(subroot->left(), K, t)); else if (KEComp::gt(K, subroot->val())) subroot->setRight( removehelp(subroot->right(), K, t)); BST Remove (2) else { // Found it: remove it BinNode<Elem>* temp; t = subroot; if (subroot->left() == NULL) //replace it with subroot = subroot->right();//its right child else if (subroot->right() == NULL)//replace it subroot = subroot->left(); //with its left child else { // Both children are non-empty; look for min in right subtree deletemin(subroot->right(), temp); Elem te = subroot->val(); subroot->setVal(temp->val()); temp->setVal(te); t = temp; } } return subroot; } Cost of BST Operations Find: O (log n) in a close-to-balanced tree Insert: O (log n) if nodes arrive randomly O (n) if nodes arrive in increasing value Delete: 2O(log n) involves finding the node and then replacing it with the node with minimum in the right sub-tree Array Implementation Node 0 1 2 3 4 5 6 7 8 9 10 11 Parent -- 0 0 1 1 2 2 3 3 4 4 5 Left Child 1 3 5 7 9 11 -- -- -- -- -- -- Right Child 2 4 6 8 10 -- -- -- -- -- -- -- Left Sibling -- -- 1 -- 3 -- 5 -- 7 -- 9 -- Right Sibling -- 2 -- 4 -- 6 -- 8 -- 10 -- -- Array Implementation Parent (r) = (r-1)/2 if r  0 Leftchild(r) = 2r+1 if 2r+1 < n Rightchild(r) = 2r+2 if 2r+2 < n Leftsibling(r) = r-1 if r is even Rightsibling(r) = r+1 if r is odd and r+1 < n Heaps Heap: Complete binary tree with the heap property: • Min-heap: All values in parent are less than child values. • Max-heap: All values in parent are greater than child values. The values are partially ordered. Heap representation: Normally the array- based complete binary tree representation. Heap ADT template<class Elem,class Comp> class maxheap { private: Elem* Heap; // Pointer to the heap array int size; // Maximum size of the heap int n; // Number of elems now in heap void siftdown(int); // Put element in place public: maxheap(Elem* h, int num, int max); int heapsize() const; bool isLeaf(int pos) const; int leftchild(int pos) const; int rightchild(int pos) const; int parent(int pos) const; bool insert(const Elem&); bool removemax(Elem&); bool remove(int, Elem&); void buildHeap(); }; Siftdown For fast heap construction: • Work from high end of array to low end. • Call Call siftdown siftdown for each item for each item, except leaf nodes. template <class Elem, class Comp> void maxheap<Elem,Comp>:: siftdown(int pos) { while (!isLeaf(pos)) { int j = leftchild(pos); int rc = rightchild(pos); //get index of child with maximum value if ((rc<n) && Comp::lt(Heap[j],Heap[rc])) j = rc; //j is always made to be the index of greater child if (!Comp::lt(Heap[pos], Heap[j])) return; swap(Heap, pos, j); pos = j; //position becomes the index of child with } //greater value } 11 10 9 8 7 6 5 4 3 2 1 0 12 Value -- -- -- -- -- -- 12 10 8 6 4 2 Right Child -- -- -- -- -- -- 11 9 7 5 3 1 Left Child 5 4 4 3 3 2 2 1 1 0 0 -- Parent Node Position -- -- 5 Leaf Nodes 50 8 16 10 2 70 66 40 13 4 18 20 3 18 66 2 50 40 13 10 70 8 16 3 4 20 50 8 16 10 2 70 66 40 13 4 18 20 3 18 66 2 50 40 13 10 70 8 16 3 4 20 50 8 16 10 2 70 66 40 13 20 18 4 3 18 66 2 50 40 13 10 70 8 16 3 20 4 50 8 16 10 2 70 66 40 13 20 18 4 3 18 66 2 50 40 13 10 70 8 16 3 20 4 50 8 16 66 2 70 10 40 13 20 18 4 3 18 10 2 50 40 13 66 70 8 16 3 20 4 50 8 16 66 2 70 10 40 13 20 18 4 3 18 10 2 50 40 13 66 70 8 16 3 20 4 8 50 16 66 2 70 10 40 13 20 18 4 3 18 10 2 40 13 8 66 50 70 16 3 20 4 8 50 16 66 2 70 10 40 13 20 18 4 3 18 10 2 40 13 8 66 50 70 16 3 20 4 8 50 70 66 2 16 10 40 13 20 18 4 3 18 10 2 40 13 8 66 50 16 70 3 20 4 8 50 70 66 2 16 10 40 13 20 18 4 3 18 10 2 40 13 8 66 50 16 70 3 20 4 8 50 70 66 2 40 10 16 13 20 18 4 3 18 10 2 16 13 8 66 50 40 70 3 20 4 8 50 70 66 2 40 10 16 13 20 18 4 3 18 10 2 16 13 8 66 50 40 70 3 20 4 8 50 3 66 2 40 10 16 13 20 18 4 70 18 10 2 16 13 8 66 50 40 3 70 20 4 8 50 3 66 2 40 10 16 13 20 18 4 70 18 10 2 16 13 8 66 50 40 3 70 20 4 8 50 66 3 2 40 10 16 13 20 18 4 70 18 10 2 16 13 8 3 50 40 66 70 20 4 8 50 66 3 2 40 10 16 13 20 18 4 70 18 10 2 16 13 8 3 50 40 66 70 20 4 8 50 66 10 2 40 3 16 13 20 18 4 70 18 3 2 16 13 8 10 50 40 66 70 20 4 8 50 66 10 2 40 3 16 13 20 18 4 70 18 10 2 3 16 8 13 50 40 66 70 20 4 Buildheap Cost Cost for heap construction: log n  (i - 1) n/2i  n. i=1 Insert template <class Elem, class Comp> bool maxheap<Elem, Comp>:: insert (const Elem& it) { if (n>=size) return false; // Heap full Heap[n++] = it; // put the value at the end for (i=floor(n/2.0)-1; i>=0; i--) siftdown(i); // This restores the order return true; } Remove template <class Elem, class Comp> bool maxheap<Elem, Comp>:: remove (int i, Elem& it) { if (i>=n || n==0) return false; // invalid index or Heap empty swap(Heap, i, --n); // Swap max with end if (n != 0) siftdown(i); // This restores the order it = Heap[n]; // Return max value return true; } Remove Max Value template <class Elem, class Comp> bool maxheap<Elem, Comp>:: removemax(Elem& it) { if (n == 0) return false; // Heap empty swap(Heap, 0, --n); // Swap max with end if (n != 0) siftdown(0); // This restores the order it = Heap[n]; // Return max value return true; } Priority Queues (1) A priority queue stores objects, and on request releases the object with greatest value. Example: Scheduling jobs in a multi-tasking operating system. The priority of a job may change, requiring some reordering of the jobs. Implementation: Use a heap to store the priority queue. Priority Queues (2) To support priority reordering (change the priority of a certain item), we may need to know the index of the object in question, and then remove it and reinsert it. template <class Elem, class Comp> bool maxheap<Elem, Comp>::remove(int pos, Elem& it) { if ((pos < 0) || (pos >= n)) return false; swap(Heap, pos, --n); //swap with last value while ((pos != 0) && (Comp::gt(Heap[pos], Heap[parent(pos)]))) swap(Heap, pos, parent(pos)); siftdown(pos); //restore order if needed it = Heap[n]; return true; } Huffman Coding Trees ASCII codes: 8 bits per character. • Fixed-length coding. Can take advantage of relative frequency (weight) of letters to save space. • Variable-length coding Assign shorter codes to characters that are used more commonly, and thus save space  Compression Z K F C U D L E 2 7 24 32 37 42 42 120 Huffman Coding Trees • Huffman code for each letter is derived from a full binary tree called Huffman coding tree. • Each leaf of the tree corresponds to a letter  weight of the leaf node is the weight (frequency) of its associated letter. • Goal is to build a tree with the minimum external path weight (MEPW). – For a leaf, the MEPW is its weight times its depth. – The binary tree with the MEPW is the one with the minimum sum of weighted path lengths for the given set of leaves. – A letter with high weight should have low depth, so it counts the least against the total path weight  another letter should be pushed deeper into the tree if it has less weight Building a Huffman Coding Tree 1. Having a string of n letters, 2. Create a collection of n initial Huffman trees, each of which is a single leaf node containing one of the letters. 3. Put the n partial trees in a list in ascending order by weight. 4. Remove the first two trees 5. Join these two trees to create a new one whose root has the two trees as children and whose weight is the sum of weights of the two trees 6. Put this tree back in the list in the correct place necessary to preserve the order of the list 7. Repeat steps 4 through 6 until all of the partial trees have been combined into one. Huffman Tree Construction for 8 selected letters Huffman Tree Construction (2) Assigning Codes Letter Freq Code Bits C 32 D 42 E 120 K 7 L 42 M 24 U 37 Z 2 1110 4 1111 3 0 1 111101 6 110 3 11111 5 11112 3 111100 6 Assigning and Using Huffman Codes • Once the tree has been constructed, we need to assign codes to individual letters. • Beginning at the root, we assign either a ‘0’ or a ‘1’ to each edge in the tree: ‘0’ to the left child and ‘1’ to the right child. • The Huffman code for a letter is a binary number determined by the path from the root to the leaf corresponding to that letter. • Decoding the message is done by looking at the bits in the coded string from left to right until a letter is decoded. • This is done by using the Huffman tree in a reverse process compared to that used in the generation process. • Decoding the bit string begins at the root of the tree • Take branches depending on the bit value: left for ‘0’ and right for ‘1’ until reaching a leaf node. • This leaf contains the first character in the message. • Next, process the following bit in the code starting at the new root to begin the next character Decoding a code • Consider the code string 1011001110111101. • Begin at the root, taking a right branch, left branch, right branch (101)  we reach a leaf corresponding to the letter D. – The remaining code is 1001110111101 • Begin at the root, taking a right branch, left branch, left branch (100)  we reach a leaf corresponding to the letter U. – The remaining code is 1110111101 • Begin at the root, taking a right branch, right branch, right branch, left branch (1110)  we reach a leaf corresponding to the letter C. – The remaining code is 111101 • Begin at the root, taking a right branch, right branch, right branch, right branch, left branch, and then a right branch (111101)  we reach a leaf corresponding to the letter K. – The code is exhausted • The decoded message is “DUCK”