/////IN header filetypedef struct treenode* tree;typedef struct treenode{ tree left; tree right; int height; int data;}treenode;///// END HEADERclass UnbalancedTreeSearcher : public ISearch{public: UnbalancedTreeSearcher(const data_array& data) { data_array::const_iterator i; bst=NULL; for(i = data.begin(); i != data.end(); i++) bst=unbal_add(bst,*i); } virtual int* find(int element){ return bst_find(bst,element); }private: tree bst; int Max(int a, int b){ return a>b?a:b; } int height(tree bst){ //returns height or -1 if the node exists or not, respectively //this keeps the height right for leaf nodes if(!bst) return -1; return bst->height; } tree unbal_add(tree bst, int data){ //adds a node with value 'data' to binary tree 'bst' if(bst==NULL){ //this is the final resting place of our node, allocate and initialize it bst=(tree)malloc(sizeof(treenode)); bst->data=data; bst->left=bst->right=NULL; } else if(data > bst->data) //add this node to the right subtree bst->right=unbal_add(bst->right,data); else if(data < bst->data) //add this node to the left subtree bst->left=unbal_add(bst->left,data); bst->height=Max(height(bst->left),height(bst->right))+1; return bst; } int* bst_find(tree bst, int data){ if(!bst)return NULL; if(bst->data==data) return &bst->data; if(bst->data > data) return bst_find(bst->left,data); else return bst_find(bst->right,data); }};class BalancedTreeSearcher : public ISearch{public: BalancedTreeSearcher(const data_array& data) { data_array::const_iterator i; bst=NULL; for(i = data.begin(); i != data.end(); i++) bst=bal_add(bst,*i); } virtual int* find(int element){ return bst_find(bst,element); }private: int Max(int a, int b){ return a>b?a:b; } int height(tree bst){ //returns height or -1 if the node exists or not, respectively //this keeps the height right for leaf nodes if(!bst) return -1; return bst->height; } tree bst; tree bal_add(tree bst, int data){ //adds a node with value 'data' to binary tree 'bst' if(bst==NULL){ //this is the final resting place of our node, allocate and initialize it bst=(tree)malloc(sizeof(treenode)); bst->data=data; bst->left=bst->right=NULL; } else if(data > bst->data){ //add this node to the right subtree bst->right=bal_add(bst->right,data); if(height(bst->right)-height(bst->left)==2) //if the tree is out of balance, do rotations to get it back if(data > bst->right->data) //we added to the right subtree of the right node; do a single left rotation bst=sleft(bst); else //we added to the left subtree of the right node; do a double left rotation bst=dleft(bst); } else if(data < bst->data){ //add this node to the left subtree bst->left=bal_add(bst->left,data); if(height(bst->left)-height(bst->right)==2) //if the tree is out of balance, do rotations to get it back if(data < bst->left->data) //we added to the left subtree of the left node, do a single right rotation bst=sright(bst); else //we added to the right subtree of the left node, do a double right rotation bst=dright(bst); } bst->height=Max(height(bst->left),height(bst->right))+1; return bst; } tree sleft(tree tn){ //Does a single left rotation about tn //reassign pointers tree worker=tn->right; tn->right=worker->left; worker->left=tn; //recalculate heights tn->height=Max(height(tn->left),height(tn->right))+1; worker->height=Max(height(worker->right),tn->height)+1; //return pointer to new pivot node. when called, make sure this value is assigned, //otherwise the subtree is lost and a memory leak occurs return worker; } tree dleft(tree tn){ //Does a double left rotation about tn tn->right=sright(tn->right); return sleft(tn); } tree sright(tree tn){ //Does a single right rotation about tn //reassign pointers tree worker=tn->left; tn->left=worker->right; worker->right=tn; //recalculate heights tn->height=Max(height(tn->left),height(tn->right))+1; worker->height=Max(height(worker->left),tn->height)+1; //return pointer to new pivot node return worker; } tree dright(tree tn){ //Does a double right rotation about tn tn->left=sleft(tn->left); return sright(tn); } int* bst_find(tree bst, int data){ if(!bst)return NULL; if(bst->data==data) return &bst->data; if(bst->data > data) return bst_find(bst->left,data); else return bst_find(bst->right,data); }};