create a test routine named test_tree that does the following in the sequence described below: Tasks:

1. Parses the database and construct a search tree . 2. Prints the number of nodes in your tree .

3. Computes the average depth of your search tree, i.e. the internal path length divided by . a. Prints the average depth. b. Prints the ratio of the average depth to log % . E.g., if average depth is 6.9 *.+ and log % = 5.0, then you should print ,.- = 1.38.

4. Searches (find()) the tree for each string in the sequences.txt file and counts the total number of recursive calls for all executions of find(). a. Prints the total number of successful queries (number of strings found). b. Prints the average number of recursion calls, i.e. #total number of recursion calls / number of queries.

5. Removes every other sequence in sequences.txt from the tree and counts the total number of recursion calls for all executions of remove(). a. Prints the total number of successful removes. b. Prints the average number of recursion calls, i.e. #total number of recursion calls / number of remove calls.

6. Redo steps 2 and 3: a. Prints number of nodes in your tree b. Prints the average depth.c. Prints the ratio of the average depth to log % .

The output of Part2(b) #Note that it is possible to deviate a little bit from these numbers.

Input files are rebase210.txt and sequences.txt Type of tree is AVL 2: 565 3a: 7.37522 3b: 0.806731 4a: 420 4b: 8.04048 5a: 161 5b: 9.11905 6a: 404 6b: 7.02228 6c: 0.811054

test_tree.cc // Main file

#include "avl_tree.h" #include "sequence_map.h"

namespace {

// @db_filename: an input database filename. @seq_filename: an input sequences filename. @a_tree: an input tree of the type TreeType. It is assumed to be template void TestTree(const string &db_filename, const string &seq_filename, TreeType &a_tree) { // Code for running Part2(b) }

} // namespace

int main(int argc, char **argv) { if (argc != 3) { cout << "Usage: " << argv[0] << " " << endl; return 0; } const string db_filename(argv[1]); const string seq_filename(argv[2]); cout << "Input file is " << db_filename << ", and sequences file is " << seq_filename << endl; // Note that you will replace AvlTree with AvlTree AvlTree a_tree; TestTree(db_filename, seq_filename, a_tree);

return 0; }

avl_tree.h #include "dsexceptions.h" template class AvlTree { public: const Comparable & findMin( ) const { if( isEmpty( ) ) throw UnderflowException{ }; return findMin( root )->element; }

const Comparable & findMax( ) const { if( isEmpty( ) ) throw UnderflowException{ }; return findMax( root )->element; }

void insert( Comparable && x ) { insert( std::move( x ), root ); } void remove( const Comparable & x ){ remove( x, root ); }

void printValue(const Comparable &x) const { printValueHelper(x, root); } int CountNodes() const { return CountNodesHelper(root); } int PathLength() const { int depth = 0; return PathLengthHelper(root, depth); }

private: struct AvlNode { Comparable element; AvlNode *left; AvlNode *right; int height;

AvlNode( const Comparable & ele, AvlNode *lt, AvlNode *rt, int h = 0 : element{ ele }, left{ lt }, right{ rt }, height{ h } { }

AvlNode( Comparable && ele, AvlNode *lt, AvlNode *rt, int h = 0 ) : element{ std::move( ele ) }, left{ lt }, right{ rt }, height{ h } { } };

AvlNode *root; void insert( const Comparable & x, AvlNode * & t ) { if( t == nullptr ) t = new AvlNode{ x, nullptr, nullptr }; else if( x < t->element ) insert( x, t->left ); else if( t->element < x ) insert( x, t->right ); else { t->element.Merge(x); } balance( t ); } void insert( Comparable && x, AvlNode * & t ) { if( t == nullptr ) t = new AvlNode{ std::move( x ), nullptr, nullptr }; else if( x < t->element ) insert( std::move( x ), t->left ); else if( t->element < x ) insert( std::move( x ), t->right );

balance( t ); }

void remove( const Comparable & x, AvlNode * & t ) { if( t == nullptr ) return; // Item not found; do nothing

if( x < t->element ) remove( x, t->left ); else if( t->element < x ) remove( x, t->right ); else if( t->left != nullptr && t->right != nullptr ) // Two children { t->element = findMin( t->right )->element; remove( t->element, t->right ); } else { AvlNode *oldNode = t; t = ( t->left != nullptr ) ? t->left : t->right; delete oldNode; }

balance( t ); }

static const int ALLOWED_IMBALANCE = 1;

void balance( AvlNode * & t ) { if( t == nullptr ) return;

if( height( t->left ) - height( t->right ) > ALLOWED_IMBALANCE ) if( height( t->left->left ) >= height( t->left->right ) ) rotateWithLeftChild( t ); else doubleWithLeftChild( t ); else if( height( t->right ) - height( t->left ) > ALLOWED_IMBALANCE ) if( height( t->right->right ) >= height( t->right->left ) ) rotateWithRightChild( t ); else doubleWithRightChild( t );

t->height = max( height( t->left ), height( t->right ) ) + 1; }

AvlNode * findMin( AvlNode *t ) const { if( t == nullptr ) return nullptr; if( t->left == nullptr ) return t; return findMin( t->left ); } AvlNode * findMax( AvlNode *t ) const{ if( t != nullptr ) while( t->right != nullptr ) t = t->right; return t; } bool contains( const Comparable & x, AvlNode *t ) const { if( t == nullptr ) return false; else if( x < t->element ) return contains( x, t->left ); else if( t->element < x ) return contains( x, t->right ); else return true; } } void makeEmpty( AvlNode * & t ) { if( t != nullptr ) { makeEmpty( t->left ); makeEmpty( t->right ); delete t; } t = nullptr; } void printTree( AvlNode *t ) const{ if( t != nullptr ) { printTree( t->left ); cout << t->element << endl; printTree( t->right ); } } AvlNode * clone( AvlNode *t ) const { if( t == nullptr ) return nullptr; else return new AvlNode{ t->element, clone( t->left ), clone( t->right ), t->height }; }

int height( AvlNode *t ) const {return t == nullptr ? -1 : t->height; }

int max( int lhs, int rhs ) const { return lhs > rhs ? lhs : rhs; } void rotateWithLeftChild( AvlNode * & k2 ) { AvlNode *k1 = k2->left; k2->left = k1->right; k1->right = k2; k2->height = max( height( k2->left ), height( k2->right ) ) + 1; k1->height = max( height( k1->left ), k2->height ) + 1; k2 = k1; } void rotateWithRightChild( AvlNode * & k1 ) { AvlNode *k2 = k1->right; k1->right = k2->left; k2->left = k1; k1->height = max( height( k1->left ), height( k1->right ) ) + 1; k2->height = max( height( k2->right ), k1->height ) + 1; k1 = k2; }

void doubleWithLeftChild( AvlNode * & k3 ) { rotateWithRightChild( k3->left ); rotateWithLeftChild( k3 ); }

void doubleWithRightChild( AvlNode * & k1 ) { rotateWithLeftChild( k1->right ); rotateWithRightChild( k1 ); } int PathLengthHelper(AvlNode * node, int depth) const { if (node == nullptr) { return 0; } else { return PathLengthHelper(node->left, depth + 1) + PathLengthHelper(node->right, depth + 1) + depth; }} }; #endif

sequence_map.h #include "dsexceptions.h"

class SequenceMap{ public: // BIG FIVE default for all of them, assume copy, move, copy assignment, move assingment, destructor SequenceMap::SequenceMap(const string & a_rec_seq, const string & an_enz_acro) : recognition_sequence_{}, enzyme_acronyms_{}{ recognition_sequence_ = a_rec_seq; enzyme_acronyms_.push_back(an_enz_acro); } bool SequenceMap::operator <(const SequenceMap &rhs) const { if( recognition_sequence_ < rhs.recognition_sequence_) return true; else return false; } ostream& operator<<(ostream &os, const SequenceMap &rhs) { for (string x : rhs.enzyme_acronyms_){ os << x << ' '; } return os; } void SequenceMap:: Merge(const SequenceMap &other_sequence) { if(recognition_sequence_ != other_sequence.recognition_sequence_) { return; } for (const auto& x : enzyme_acronyms_) { if (x == other_sequence.enzyme_acronyms_[0]) { return; } } enzyme_acronyms_.push_back(other_sequence.enzyme_acronyms_[0]);

}private: string recognition_sequence_; vector enzyme_acronyms_; }; Please help me in writing test_tree.cc Everything else is written out. Thank you.