Eric Roberts Handout #45CS 106B May 15, 2009Binary Search TreesContest ResultsThe CS106BSorting ContestMay 20093. Adam Adler 4.42 sec2. Fidel Hernandez 1.74 sec1. Christopher Lewis 1.58 secMap Lookup Revisited• The hash table strategy we introduced a week ago is by far themost common implementation of maps in practice.• Despite its many advantages—most notably its extraordinaryefficiency—the hash table implementation is not necessarilythe best strategy for all applications.• The hash table strategy has the following limitations:– Hash tables depend on being able to compute a hash function onsome key. Expanding the hash-function idea so that it applies totypes other than strings can be subtle.– The iterator for a map based on hash tables does not generate itsvalues in any kind of order. If the key type has a natural order(which is called lexicographic order in the case of strings), theiterator cannot take advantage of that fact.Looking Up Keys in an Array• Instead of using a map, suppose that you entered all the stateabbreviations (along with their names) in an array:• How many operations (as a function of the size N) are neededto find a state abbreviation, such as "GA"?• The lookup operation in a sorted array runs in O(log N) time.Adding a Key to an Array• But what about adding a new key? Suppose, for example, thatPuerto Rico (PR) becomes a state:• All the cells at the end of the array need to move to makeroom.• The add operation in a sorted array runs in O(N) time.Fixing the Problem• When we worked with the editor buffer two weeks ago, wesolved the insertion problem by using a linked list instead ofan array.• Unfortunately, turning a sorted array into a linked list makes itimpossible to apply binary search because there is no way tofind the middle element.• But what if you could point to the middle element in a linkedlist? That idea seems unlikely, but it is the key to finding adata structure that offers O(log N) performance for both thelookup and add operations.Binary Search Trees• The structure that ends up solving this problem is called abinary search tree. Each node in such a tree has exactly twosubtrees: a left subtree that contains all the nodes that comebefore this one and a right subtree that contains all the nodesthat come after it.• The classical example is the following binary search tree ofthe seven dwarves:– 2 –/* * File: bst.h * ----------- * This file provides an interface for a general binary search * tree class template. */#ifndef _bst_h#define _bst_h#include "cmpfn.h"/* * Class: BST * ---------- * This interface defines a class template for a binary search tree. * For maximum generality, the BST is supplied as a class template. * The data type is set by the client. The client specializes the * tree to hold a specific type, e.g. BST<int> or BST<studentT>. * The one requirement on the type is that the client must supply a * a comparison function that compares two elements (or be willing * to use the default comparison function that relies on < and ==). */template <typename ElemType>class BST {public:The bst.h Interface/* * Constructor: BST * Usage: BST<int> bst; * BST<song> songs(CompareSong); * ------------------------------------ * The constructor initializes a new empty binary search tree. * The one argument is a comparison function, which is called * to compare data values. This argument is optional, if not * given, OperatorCmp from cmpfn.h is used, which applies the * built-in operator < to its operands. If the behavior of < * on your type is defined and sufficient, you do not need to * supply your own comparison function. */ BST(int (*cmpFn)(ElemType one, ElemType two) = OperatorCmp);/* * Destructor: ~BST * Usage: (usually implicit) * ------------------------- * This function deallocates the storage for a tree. */ ~BST();The bst.h Interface/* * Method: find * Usage: if (bst.find(key) != NULL)... * --------------------------------------- * This method applies the binary search algorithm to * find a particular key in this tree. The argument is the key * to use for comparison. If a node matching key appears in the * tree, find returns a pointer to the data in that node; otherwise, * find returns NULL. */ ElemType *find(ElemType key);/* * Method: add * Usage: bst.add(val); * -------------------- * This method adds a new node to this tree. The elem * argument is compared with the data in existing nodes to find * the proper position. If a node with the same value already * exists, the contents are overwritten with the new copy and * false is returned. If no matching node is found, a new node * is allocated and added to the tree, true is returned. */ bool add(ElemType elem);The bst.h Interface/* * Method: remove * Usage: bst.remove(key); * ----------------------- * This method removes a node in this tree that matches * the specified key. If a node matching key is found, the node * is removed from the tree and true is returned. If no match * is found, no changes are made and false is returned. */ bool remove(ElemType key);/* * Method: clear * Usage: bst.clear(); * ------------------- * This method removes all elements from this tree. The * tree is made empty and will have no nodes after being cleared. */ void clear();The bst.h Interface/* * Method: mapAll * Usage: bst.mapAll(PrintToFile, outputStream); * --------------------------------------------- * This method iterates through the binary search tree * and calls the function fn once for each element, passing the * element and the client's data. That data can be of whatever * type is needed for the client's callback. The order of calls * is determined by an InOrder walk of the tree. */ template <typename ClientElemType> void mapAll(void (fn)(ElemType elem, ClientElemType &data), ClientElemType &data);private:#include "bstpriv.h"};#include "bstimpl.cpp"#endifThe bst.h Interface/* * File: bstpriv.h * --------------- * This file contains the private section of the bst.h interface. * This file contains the private section of the Queue template * class. Including this information in a separate file means * that clients don't need to look at these details. *//* Type definition for a node */ struct nodeT { ElemType data; nodeT *left, *right; };/* Instance variables */ nodeT *root; int (*cmpFn)(ElemType, ElemType);The bstpriv.h Data Structure– 3 –/* * File: cmpfn.h * ------------- * This