Question
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
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
} // namespace
int main(int argc, char **argv) { if (argc != 3) { cout << "Usage: " << argv[0] << "
return 0; }
avl_tree.h #include "dsexceptions.h" template
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
Step by Step Solution
There are 3 Steps involved in it
Step: 1
![blur-text-image](https://dsd5zvtm8ll6.cloudfront.net/includes/images/document_product_info/blur-text-image.webp)
Get Instant Access with AI-Powered Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
![blur-text-image](https://dsd5zvtm8ll6.cloudfront.net/includes/images/document_product_info/blur-subtext-image.webp)
Step: 3
![blur-text-image](https://dsd5zvtm8ll6.cloudfront.net/includes/images/document_product_info/blur-subtext-image.webp)
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started