We can get efficient algorithms both for finding and for inserting fish into the set if we use a binary search tree.  This representation has performance comparable to binary search, O(log N), for finding a fish and similar performance for inserting and deleting fish.  Thus we get good performance even if the fish population is dynamic, and there is no dependence on a bounded grid.

We define a fish set class that is implemented using a binary search tree, ordered by position.  For example, in the diagram below we represent a 5x5 grid of fish, with fish located at positions (0,3), (2,1), (2,3), (3,1), (3,2), (4,4).

The functions in the Environment class that previously accessed the apmatrix of fish will access this set instead.  Analysis shows that with a dynamic population the complexity of some of the Environment functions, and therefore the Fish functions, is reduced compared to the vector model .

1. We need to overload operator < and operator != for the Position class, so that these comparisons can be used when searching in the lookup table ordered by position.
• There is no reason that these operators need to be free functions, as operator ==  is in the original implementation, since we will never compare a position with anything other than another position.  Make all the comparison operators, including operator ==, member functions of the Position class.
2. Construct a Directory (i.e. Lookup Table or Map) class that stores items with a key.  We can do this as a template class with two placeholders for types, one for the items to be stored (ItemType) and the other for the keys (KeyType). KeyType must have operator <  defined for it.  In our case KeyType will be Position.
• The lookup table will be implemented with a binary search tree (BST), so we need to declare a struct TreeNode that contains an ItemType item, a KeyType key, and a left and a right pointer.  It is useful to have a constructor for a node that takes an item and a key as parameters.
• We need a private data member myRoot, a pointer to the root node of the BST.
• Since to the client program, it is immaterial how the Directory is implemented, the structure of the binary tree should be invisible, so each of the member functions should not refer to tree nodes or myRoot.  This means that in order to implement recursive calls, each such function will be paired with a private helper member function that does the recursion.
• The constructor for Directory should simply set myRoot to NULL.
• We need to define the following functions, each with a helper function to do the recursion.
• Insert and InsHelp. Insert takes an item and key and adds the item to the tree with the key.  If the key is already in the tree, then the item with that key should be overwritten by the new item.
• Remove and RemHelp. Remove takes a key and removes the item stored with that key, if any, from the BST.
• Lookup and LookHelp. Lookup takes a key parameter and a reference parameter item.  If the key is found in the tree, item is set to be the item stored with key and Lookup returns true, otherwise Lookup returns false.
• InorderList and InorderHelp. InorderList should return an apqueue containing all the items in the BST in order by key. Note: The return type used to be apvector!
• We need to define a destructor that deallocates all memory from nodes in the tree.
• This is best done using another private helper member function FreeTree.
3. The BST.h file contains the class declaration for a BST implemented directory.  The BST.cpp file contains a partial implementation of Directory.  The following functions remain to be implemented in directoryBST.cpp.  These are all best done recursively.
• FreeTree
• InsHelp
• RemHelp
• LookHelp
• InorderHelp
4. After the directory based on a binary tree is done, we need to replace the apmatrix myWorld with a Directory in the fish Environment class.
• Environment will also need private data members myNumRows and myNumCols if a bounded grid is used.
5. The following Environment functions need to be changed to use the Directory for accessing fish instead of the apmatrix.
• the constructor
• AddFish
• RemoveFish
• IsEmpty
• Update
• AllFish
• The functions NumRows and NumCols need to be modified to use myNumRows and myNumCols.