CSC152 2006S, Class 39: Dictionaries (3): Experimenting with Binary Search Trees Admin: * Are there questions on the exam? * Question 1c. is now optional. (Extra credit, no negative extra credit.) * No reading for Friday (since you wouldn't do it anyway). * Sorry about temperature. Overview: * Balanced Trees. * Terminology. * BSTs and Dictionaries. * Removing Values. Balanced Trees * For insertion and search in BSTs to be fast, the depth must be logarithmic in the size. * We often say that we need it to be balanced. * What does balanced mean? * Informal: "Stuff on both sides" * More formal: Left and right subtrees of the root are approximately equal size. * Most of us get the definitions wrong. All of the prior ones accept the following tree with pretty bad depth * / \ * * / \ * * / \ * * / \ * * * A possible defintiion: Leaves are no more than one level apart. + Also accepts the above * Revised definition: "Left and right subtrees are approximately the same size and each subtree has the same property" * Approximate might mean "difference of 1" * The revised definition is good, but hard to guarantee. * Best workable definition: A tree is balanced if the depth of the two subtrees differ by no more than 1 and each subtree is balanced * The christmas tree is *not* balanced by this definition. Other terms: * Full - All nodes have either 0 or two children * Complete - Full + all leaves are at the same level * Nearly complete: Leaves can be at two levels, but shoved to the left * Full but not complete * / \ * * / \ * * / \ / \ How do you use a BST to implement a dictionary * Organize the nodes by their keys, rather than their values. * Search by keys When we implement public class BSTNode { K key; V value; BSTNode left; BSTNode right; } public class BST { BSTNode root; public V find(K key) { return find(key, root); } V find(K findme, BSTNode position) throws NoSuchKeyException { // If we've run out of tree if (position == null) { throw new NoSuchKeyException(key); } // if (findme is the key of position) then else if (c.compare(findme,position.key) == 0) { // return the value of that position return position.value; } // else if (finme is smaller than the key of position) then else if (c.compare(findme, position.key) < 0) { // recurse on the left subtree return find(findme, position.left); } // else, findme is larger than the key of position else { // recurse on the right subtree return find(findme, position.right); } } Whoops! Objects of type K may not provide the compareTo method. * Solutions: * Make it a precondition public class BST, V> * Provide a comparator for the tree public BST(Comparator c) { this.c = c; } } Removing values! * Find the key/value pair to remove (using technique above) * Find the leftmost key/value pair in the right subtree * Replace the original key/value pair by the found one * Move up what was below the key/value pair * Hidden issue: * If no right subtree, shift up left * If no subtrees, just delete