Experimental Bst

Experimental Bst

This is a sample C++ homework. We can complete the majority assignments within 1 day, but to be sure you have the chance to go over it, it is better to contact us with time to spare.

Experimental BST

Scenario:

Binary trees should be balanced (otherwise they can end up as a linked list). We can define an unbalanced tree as one
where te height of the subtree is more than than 2 log n where n is the number of children. For example

The red numbers are the heights and the green numbers are the sizes of the subtrees.

We can rebalance the tree by making 34 the root and get a new tree with height 19.

So how do we determine 34 should be the new root? We perform an inorder walk upto depth 3, this gives a list of subtrees and single nodes, and we place these in an array:

We want to include the empty tree that is to left of 135 in the array. We can then use any singleton node as the new root.

Assignment Question:

You need to program the Experimental BST described above. You may start with a binary search tree class. You may also design your own. One of the main objectives is for you to practice recursion.

Since you are free to choose the design of the class, no header files will be provided, so the requirements are:

  • The class should be called ExpBST.
  • The header file should be ExpBST.h
  • You need to implement the functions below with the same signatures.
  • The implementation must be in a single file called ExpBST.cpp.
  • You may not use any STL library functions.

You need to have data for height and size in the class, representing the root of the subtreem that should be updated
whenever the subtree changes.

Here are the member functions you must implement in your ExpBST class.

  1. A default constructor.
    ExpBST::ExpBST() ;
  2. A constructor specifying the depth, minimum height and factor
    ExpBST::ExpBST(int depth, int minHeight, float factor) ;
  3. Getters for depth, minHeight and factor.
    int getMaxRebalanceDepth() const  ;
    
    int getMinRebalanceHeight() const ;
    
    float getRebalanceFactor() const ;
  4. A copy constructor
    ExpBST::ExpBST(const ExpBST& other) ;
  5. A destructor
    ExpBST::~ExpBST() ;
  6. An overloaded assignment operator
    const ExpBST& ExpBST::operator=(const ExpBST& rhs) ;
  7. An insert() function that adds an item to ExpBST
    void ExpBST::insert (int key) ;
  8. A remove() function that locates and removes the key.
    bool ExpBST::remove(int key) ;
  9. A find() function that returns whether the key is present.
    bool ExpBST::find(int key) ;
  10. A rebalance() function that rebalances a subtree, that should run in constant time.
  11. Functions to report on the statistics of the rebalances.
    int ExpBST::getNumRebalance() const ;
    
    int ExpBST::getFailedRebalance() const ;
    
    int ExpBST::getExceedsHeight() const ;
    
    void ExpBST::resetStats() ;
  12. An inorder() function that prints the tree (nothing should be printed if the tree is empty).
    void ExpBST::inorder() ;
  13. A locate() function that returns if there is a node at position and retrieves the key.
    bool ExpBST::locate(const char *position, int& key) ;
  14. Your ExpBST class must also have the following functions.
    bool ExpBST::empty() const  ;    // tree has no nodes
    
    int  ExpBST::height() const ;    // height of tree
    
    int  ExpBST::size() const ;      // number of nodes in tree

Your code must run without segmentation fault and without memory leaks.

Solution for Assignment 6:

Here is an example C++ project, that demonstrates the sort of C++ assignment help we can offer.

Driver.cpp

#include <iostream>
#include <cmath>
using namespace std;

#include "ExpBST.h"

void report(const ExpBST& T);

int main(int agrc, char* agrv[])
{

    ExpBST T(3, 3, 2.0);
    int n = 100000;
    for (int w = 1; w < 2 * n; w++)
    {
        T.insert(w);
    }

    for (int w = n / 2; w < n + n / 2; w++)
    {
        T.remove(w);
    }
    int m = 100;
    int k = 564;
    for (int j = 0; j < k; j++)
    {

        int base = 4 * j * m;

        for (int k = base; k < base + 4 * m; k++)
        {
            T.insert(k);
        }

        for (int k = base + m; k < base + 2 * m; k++)
        {
            T.remove(k);
        }
    }
    report(T);
    return 0;
}

void report(const ExpBST& T)
{

    cout << "***** ExpBST Report\n";

    cout << "   size = " << T.size() << endl;
    cout << "   height = " << T.height() << endl;
    cout << "   height/log(size) = " << ((float) T.height()) / log2(T.size()) << endl;

    cout << "   numRebalance = " << T.getNumRebalance() << endl;
    cout << "   failedRebalance = " << T.getFailedRebalance() << endl;
    cout << "   exceedsHeight = " << T.getExceedsHeight() << endl;

    cout << "   maxRebalanceDepth = " << T.getMaxRebalanceDepth() << endl;
    cout << "   minRebalanceHeight = " << T.getMinRebalanceHeight() << endl;
    cout << "   rebalanceFactor = " << T.getRebalanceFactor() << endl;

}

Below is a C++ project, but if you just require a C++ online tutor then we can provide that for you as well.

ExpBST.cpp

#include "ExpBST.h"
#include <iostream>
#include <cstring>
#include <math.h>
using namespace std;

int ExpBST::m_maxRebalanceDepth;
int ExpBST::m_minHeight;
float ExpBST::m_rebalanceFactor;
int ExpBST::m_numRebalance;
int ExpBST::m_failedRebalance;
int ExpBST::m_exceedHeight;

ExpBST::ExpBST()
{
    m_maxRebalanceDepth = 3;
    m_minHeight = 5;
    m_rebalanceFactor = 2;
    m_numRebalance = 0;
    m_failedRebalance = 0;
    m_exceedHeight = 0;

    m_head = NULL;
    m_rebalanceArrayStore = new Node*[int(pow(2, (m_maxRebalanceDepth + 1)) - 1)];
    m_rebalanceArrayStoreLen = 0;
}

ExpBST::ExpBST(int depth, int minHeight, float factor)
{
    m_maxRebalanceDepth = depth;
    m_minHeight = minHeight;
    m_rebalanceFactor = factor;
    m_numRebalance = 0;
    m_failedRebalance = 0;
    m_exceedHeight = 0;
    m_head = NULL;
    m_rebalanceArrayStore = new Node*[int(pow(2, (m_maxRebalanceDepth + 1)) - 1)];
    m_rebalanceArrayStoreLen = 0;
}

ExpBST::ExpBST(const ExpBST &other)
{
    m_head = copyHelper(other.m_head);
    m_maxRebalanceDepth = other.m_maxRebalanceDepth;
    m_minHeight = other.m_minHeight;
    m_rebalanceFactor = other.m_rebalanceFactor;
    m_rebalanceArrayStore = new Node*[int(pow(2, (m_maxRebalanceDepth + 1)) - 1)];
    m_rebalanceArrayStoreLen = other.m_rebalanceArrayStoreLen;

}

Node* ExpBST::copyHelper(const Node* copy)
{
    if (copy == NULL)
        return NULL;
    Node *copiedNode = new Node(copy->value);
    copiedNode->size = copy->size;
    copiedNode->height = copy->height;
    //recursive calls to copy left and right children
    copiedNode->left = copyHelper(copy->left);
    copiedNode->right = copyHelper(copy->right);
    return copiedNode;
}

void ExpBST::makeEmpty(Node*& head)
{
    if (head != NULL)
    {
        // delete both children, then currNode
        makeEmpty(head->left);
        makeEmpty(head->right);
        delete head;
        // set currNode to NULL after deletion
        head = NULL;
    }
}

ExpBST::~ExpBST()
{
    makeEmpty(m_head);
    m_head = NULL;
    //clears out rebalance array correctly
    delete[] m_rebalanceArrayStore;
    m_rebalanceArrayStore = NULL;
}

const ExpBST& ExpBST::operator=(const ExpBST& rhs)
{
    makeEmpty(m_head);
    delete[] m_rebalanceArrayStore;
    m_rebalanceArrayStore = NULL;
    //assign values from rhs to lhs
    m_head = copyHelper(rhs.m_head);
    m_maxRebalanceDepth = rhs.m_maxRebalanceDepth;
    m_minHeight = rhs.m_minHeight;
    m_rebalanceFactor = rhs.m_rebalanceFactor;
    m_rebalanceArrayStore = new Node*[int(pow(2, (m_maxRebalanceDepth + 1)) - 1)];
    m_rebalanceArrayStoreLen = rhs.m_rebalanceArrayStoreLen;
    return *this;
}

bool ExpBST::insertHelper(int key, Node*& currNode)
{
    bool isDuplicate = true;
    //if the head is empty
    if (m_head == NULL)
    {
        m_head = new Node(key);
        return false;
    }
    else if (currNode == NULL)
    { // no node here (make a new leaf)
        currNode = new Node(key, 0);
        isDuplicate = false;
    }
    // value in CURRENT root < new value
    else if (key < currNode->value)
    {
        isDuplicate = insertHelper(key, currNode->left);
    }
    // value in CURRENT root  > new value
    else if (key > currNode->value)
    {
        isDuplicate = insertHelper(key, currNode->right);
    }
    //duplicate value
    else if (key == currNode->value)
        return true;
    //updates the height and size of the node on traceback
    if (!isDuplicate)
    {
        currNode->size += 1;
        //updates the height based on various conditions and whether or not the height
        //should be updated
        Node* potential = (currNode->left != NULL) ? currNode->left : currNode->right;
        if (currNode->left != NULL and currNode->right != NULL)
            currNode->height = max(currNode->left->height, currNode->right->height) + 1;
        else if (potential != NULL)
            currNode->height = potential->height + 1;
        else
            currNode->height = 0;
    }
    //decides whether to rebalance or not
    if (float(currNode->height) > (m_rebalanceFactor * log2(currNode->size)) and currNode->height >= m_minHeight and !isDuplicate)
    {
        rebalanceHelper(currNode);
    }
    return isDuplicate;
}
/*
 * Insert node with value is key
 */
void ExpBST::insert(int key)
{
    insertHelper(key, m_head);
}

/*
 * Helper remove
 */
bool ExpBST::removeHelper(int key, Node*& currNode)
{
    bool hasRemoved;
    //check if need to update for 2 children, automatically need to update for 0 or 1 children
    if (currNode == NULL)
        return false; // item not found; return false
    // continue to traverse until we find the element
    else if (key < currNode->value)
        hasRemoved = removeHelper(key, currNode->left);
    else if (currNode->value < key)
        hasRemoved = removeHelper(key, currNode->right);
    else if (currNode->left != NULL and currNode->right != NULL)
    { // two children
      // find left's highest value
        currNode->value = findMax(currNode->left)->value;
        //now delete that found value
        hasRemoved = removeHelper(currNode->value, currNode->left);
    }
    else
    { // zero or one child
        Node *oldNode = currNode;
        // ternary operator
        currNode = (currNode->left != NULL) ? currNode->left : currNode->right;
        //replace the currentNode then delete it
        delete oldNode;
        if (currNode != NULL)
            currNode->size += 1;
        hasRemoved = true;
    }
    //update heights on traceback
    if (currNode != NULL and hasRemoved)
    {
        Node* potential = (currNode->left != NULL) ? currNode->left : currNode->right;
        currNode->size -= 1;
        //updates height based off various conditions
        if (currNode->left != NULL and currNode->right != NULL)
            currNode->height = max(currNode->left->height, currNode->right->height) + 1;
        else if (potential != NULL)
            currNode->height = potential->height + 1;
        else
            currNode->height = 0;

        //determine whether to rebalance or not on traceback
        if (currNode->height > (m_rebalanceFactor * log2(currNode->size)) and currNode->height >= m_minHeight and hasRemoved)
            rebalanceHelper(currNode);
    }
    return hasRemoved;
}

/*
 * Remove Node
 */
bool ExpBST::remove(int key)
{
    //calls the helper function
    return removeHelper(key, m_head);
}
Node* ExpBST::findMax(Node*& currNode)
{
    // empty tree
    if (currNode == NULL)
        return NULL;
    // no further nodes to the right
    if (currNode->right == NULL)
        return currNode;
    else
        return findMax(currNode->right);
}

bool ExpBST::findHelper(int key, Node*& currNode)
{
    if (currNode == NULL)
        return false;
    // our value is lower than the current node's
    else if (key < currNode->value)
        return findHelper(key, currNode->left);
    // our value is higher than the current node's
    else if (currNode->value < key)
        return findHelper(key, currNode->right);
    else
        return true; // Match
}
/*
 * Find a key in value
 */
bool ExpBST::find(int key)
{
    return findHelper(key, m_head);
}

int ExpBST::getMaxRebalanceDepth() const
{
    return m_maxRebalanceDepth;
}
int ExpBST::getMinRebalanceHeight() const
{
    return m_minHeight;
}
float ExpBST::getRebalanceFactor() const
{
    return m_rebalanceFactor;
}

int ExpBST::getNumRebalance() const
{
    return m_numRebalance;
}

int ExpBST::getFailedRebalance() const
{
    return m_failedRebalance;
}

int ExpBST::getExceedsHeight() const
{
    return m_exceedHeight;
}

void ExpBST::resetStats()
{
    m_maxRebalanceDepth = 0;
    m_minHeight = 0;
    m_rebalanceFactor = 0.0;
    m_numRebalance = 0;
    m_failedRebalance = 0;
    m_exceedHeight = 0;

}

void ExpBST::inorderHelper(Node*& currNode)
{
    if (currNode == NULL)
        return;
    cout << "(";
    /* first recur on left child */
    inorderHelper(currNode->left);
    /* then print the data of node */
    cout << currNode->value << ":" << currNode->height << ":" << currNode->size;
    /* now recur on right child */
    inorderHelper(currNode->right);
    cout << ")";
}

void ExpBST::inorder()
{
    inorderHelper(m_head);
}

bool ExpBST::locateHelper(const char *position, int& key, int index, Node* currNode)
{
    //checks if the node is empty, not found
    if (currNode == NULL)
        return false;
    //base case if the index is equal to the length of the array, position is found
    else if (strlen(position) == index)
    {
        key = currNode->value;
        return true;
    }
    //if the next position is to the left
    else if (position[index] == 'L')
    {
        //recursion call
        return locateHelper(position, key, index + 1, currNode->left);
    }
    //if the next position is to the right
    else if (position[index] == 'R')
    {
        //recursion call
        return locateHelper(position, key, index + 1, currNode->right);
    }
    return true;
}

bool ExpBST::locate(const char *position, int& key)
{
    return locateHelper(position, key, 0, m_head);
}

void ExpBST::rebalanceArrayHelper(int depth, Node*& currNode)
{
    if (depth > getMaxRebalanceDepth())
        return;
    else if (currNode == NULL)
    {
        m_rebalanceArrayStore[m_rebalanceArrayStoreLen] = NULL;
        m_rebalanceArrayStoreLen += 1;
        return;
    }
    /* first recur on left child */
    rebalanceArrayHelper(depth + 1, currNode->left);
    m_rebalanceArrayStore[m_rebalanceArrayStoreLen] = currNode;
    m_rebalanceArrayStoreLen += 1;
    /* now recur on right child */
    rebalanceArrayHelper(depth + 1, currNode->right);
    return;
}

void ExpBST::rebalanceHelper(Node*& currNode)
{
    int prevHeight = currNode->height;
    m_rebalanceArrayStoreLen = 0;
    //creates array to use for rebalancing nodes
    rebalanceArrayHelper(0, currNode);
    //finds the best root for the new subtree then creates the new subtree
    int possibleRoot = shortestBSTRoot(0, m_rebalanceArrayStoreLen - 1);
    currNode = rebalance(0, m_rebalanceArrayStoreLen - 1, possibleRoot);
    //updates postrebalance statistics
    m_numRebalance += 1;
    if (currNode->height >= prevHeight)
        m_failedRebalance += 1;
    if (currNode->height > (m_rebalanceFactor * log2(currNode->size)))
        m_exceedHeight += 1;
}

int ExpBST::shortestBSTRoot(int begin, int end)
{
    //base case
    if (begin >= end)
    {
        return end;
    }
    int bestLeft = 0, bestRight = 0, bestRoot = 0;
    int height = -1, tempHeight = 0, leftHeight = -1, rightHeight = -1;
    for (int i = begin; i <= end; i++)
    {
        if (i % 2 == 1)
        {
            //finds the best possible child for left and right subtree in the array
            bestLeft = shortestBSTRoot(begin, i - 1);
            bestRight = shortestBSTRoot(i + 1, end);
            //finds the heights of the two children
            if (m_rebalanceArrayStore[bestLeft] != NULL)
                leftHeight = m_rebalanceArrayStore[bestLeft]->height;
            if (m_rebalanceArrayStore[bestRight] != NULL)
                rightHeight = m_rebalanceArrayStore[bestRight]->height;
            if (height == -1)
            {
                //finds the height of the current root
                height = max(leftHeight, rightHeight) + 1;
                bestRoot = i;
            }
            //compares the heights for all the possible roots and chooses the best one
            else
            {
                //finds the height of the current root
                tempHeight = max(leftHeight, rightHeight) + 1;
                if (height > tempHeight)
                {
                    height = tempHeight;
                    bestRoot = i;
                }
            }
        }
    }
    m_rebalanceArrayStore[bestRoot]->height = height;
    return bestRoot;
}

Node* ExpBST::rebalance(int begin, int end, int root)
{
    //base case
    if (begin >= end)
        return m_rebalanceArrayStore[begin];
    //recursively create the left subtree from the left child of the root
    m_rebalanceArrayStore[root]->left = rebalance(begin, root - 1, shortestBSTRoot(begin, root - 1));
    //recursively create the right subtree from the right child of the root
    m_rebalanceArrayStore[root]->right = rebalance(root + 1, end, shortestBSTRoot(root + 1, end));
    //change sizes and heights based on various conditions
    if (m_rebalanceArrayStore[root]->left == NULL and m_rebalanceArrayStore[root]->right == NULL)
    {
        m_rebalanceArrayStore[root]->height = 0;
        m_rebalanceArrayStore[root]->size = 1;
    }
    else if (m_rebalanceArrayStore[root]->left != NULL and m_rebalanceArrayStore[root]->right != NULL)
    {
        m_rebalanceArrayStore[root]->height = max(m_rebalanceArrayStore[root]->left->height, m_rebalanceArrayStore[root]->right->height) + 1;
        m_rebalanceArrayStore[root]->size = m_rebalanceArrayStore[root]->left->size + m_rebalanceArrayStore[root]->right->size + 1;
    }
    else
    {
        Node* onlyNode = (m_rebalanceArrayStore[root]->left != NULL) ? m_rebalanceArrayStore[root]->left : m_rebalanceArrayStore[root]->right;
        m_rebalanceArrayStore[root]->height = onlyNode->height + 1;
        m_rebalanceArrayStore[root]->size = onlyNode->size + 1;
    }
    return m_rebalanceArrayStore[root];
}

bool ExpBST::empty() const
{
    return m_head == NULL;
}

int ExpBST::height() const
{
    if (m_head == NULL)
        return -1;
    return m_head->height;
}

int ExpBST::size() const
{
    if (m_head == NULL)
        return 0;
    return m_head->size;
}

You will find an example C++ project, that illustrates the style of the work we can do for you.

ExpBST.h

#include <cstddef>
#ifndef EXPBST_H_
#define EXPBST_H_

// define Node
typedef struct Node
{
        int value;
        int height;
        int size;
        struct Node* left;
        struct Node *right;
        Node()
        {
            this->value = 0;
            this->left = NULL;
            this->right = NULL;
            this->size = 1;
            this->height = 0;
        }

        Node(int val)
        {
            this->value = val;
            this->left = NULL;
            this->right = NULL;
            this->size = 1;
            this->height = 0;
        }
        Node(int val, int height)
        {
            this->value = val;
            this->height = height;
            this->size = 0;
            this->left = NULL;
            this->right = NULL;
        }
} Node;
class ExpBST
{
    public:
        //Constructor
        ExpBST();
        ExpBST(int depth, int minHeight, float factor);
        // Copy constructor
        ExpBST(const ExpBST& other);

        // Deconstructor
        ~ExpBST();

        //Operator
        const ExpBST& operator=(const ExpBST& rhs);

        // Insert node to tree
        void insert(int key);
        /*
         * A remove() member function that finds and removes an item with the given key value.
         * The remove() function should return a boolean value that indicates whether the key was found.
         * Your remove() function should not abort or throw an exception when the key is not stored in the BST
         */
        bool remove(int key);
        /*
         * A find() function that reports whether the given key is stored in the tree
         */
        bool find(int key);

        /*
         * A member function rebalance() that rebalances a subtree of the ExpBST as described above.
         * The running time of rebalance() must be constant.
         * Note that a proper implementation would require you the keep track of the size and height of the subtree
         */
        Node* rebalance(int begin, int end, int bestRoot);
        //
        int getMaxRebalanceDepth() const;
        int getMinRebalanceHeight() const;
        float getRebalanceFactor() const;

        /*
         * Your ExpBST class must have the following functions report on statistics of the ExpBST tree related to the rebalance
         */
        int getNumRebalance() const;
        int getFailedRebalance() const;
        int getExceedsHeight() const;
        static void resetStats();
        /*
         * A member function inorder() that performs an inorder walk of the ExpBST and at each node,
         * prints out the key followed by a : followed by the height of the node followed by another :
         * followed by the size of the subtree rooted at that node.
         * Furthermore, inorder() should print an open parenthesis before visiting the left subtree and a close parenthesis after visiting the right subtree.
         * Nothing should be printed when inorder() is called on an empty tree, not even parentheses.
         * For example in the BST above:
         * A call to locate("LRL",key) should return true and store 26 in key.
         * A call to locate("RRLR",key) should return true and store 75 in key.
         * A call to locate("RLR",key) should return false and not make any changes to key since there is not a node in that position.
         * Note: locate() must not abort and must not throw an exception in this situation.
         * A call to locate("",key) should return true and store 41 in key, since the empty string indicates the root of tree.
         */
        void inorder();

        /*
         * A function locate() that returns whether there is a node in a position of the ExpBST and stores the key in the reference parameter.
         * The position is given by a constant C string, where a character 'L' indicates left and a character 'R' indicates right
         */
        bool locate(const char *position, int& key);

        /*
         * Your ExpBST class must have the following functions to report on attributes of the ExpBST tree:
         */

        bool empty() const; // tree has no nodes
        int height() const; // height of tree
        int size() const; // number of nodes in tree

    private:
        // Internal function
        Node* copyHelper(const Node* copy);
        //insert function helper
        bool insertHelper(int key, Node*& currNode);
        //remove function helper
        bool removeHelper(int key, Node*& currNode);
        //clear function
        void makeEmpty(Node*& header);
        //findHelper
        bool findHelper(int key, Node*& currNode);
        //inorderHelper
        void inorderHelper(Node*& currNode);
        //findMax
        Node* findMax(Node*& currNode);
        //locateHelper
        bool locateHelper(const char *position, int& key, int index, Node* currNode);

        void rebalanceArrayHelper(int depth, Node*& currNode);

        int shortestBSTRoot(int begin, int end);

        void rebalanceHelper(Node*& currNode);

        // static variable
        static int m_maxRebalanceDepth;
        static int m_minHeight;
        static float m_rebalanceFactor;
        static int m_numRebalance;
        static int m_failedRebalance;
        static int m_exceedHeight;

        Node* m_head;
        Node** m_rebalanceArrayStore;
        int m_rebalanceArrayStoreLen;
};

#endif /* EXPBST_H_ */

For all your C++ homework help that you need, you won’t find a better place.

p3test1.cpp

#include <iostream>
#include <cmath>
using namespace std ;

#include "ExpBST.h"

void report(const ExpBST& T) {

   cout << "***** ExpBST Report\n" ;

   cout << "   size = " << T.size() << endl ;
   cout << "   height = " << T.height() << endl ;
   cout << "   height/log(size) = " << ( (float) T.height() ) / log2(T.size()) << endl ;

   cout << "   numRebalance = " << T.getNumRebalance() << endl ;
   cout << "   failedRebalance = " << T.getFailedRebalance() << endl ;
   cout << "   exceedsHeight = " << T.getExceedsHeight() << endl ;

   cout << "   maxRebalanceDepth = " << T.getMaxRebalanceDepth() << endl ;
   cout << "   minRebalanceHeight = " << T.getMinRebalanceHeight() << endl ;
   cout << "   rebalanceFactor = " << T.getRebalanceFactor() << endl ;

}

int main() {

   ExpBST T(3, 3, 2.0) ;
   int k ;

   T.insert(70) ;
   T.inorder() ; cout << endl ;

   T.insert(30) ;
   T.inorder() ; cout << endl ;

   T.insert(110) ;

   T.inorder() ; cout << endl ;

   cout << "\n\n***** Insert 40 *****\n" ;
   T.insert(40) ;
   T.inorder() ; cout << endl ;

   cout << "\n\n***** Insert 20 *****\n" ;
   T.insert(20) ;
   T.inorder() ; cout << endl ;

   cout << "\n\n***** Insert 41 *****\n" ;
   T.insert(41) ;
   T.inorder() ; cout << endl ;

   cout << "\n\n***** Insert 31 *****\n" ;
   T.insert(31) ;
   T.inorder() ; cout << endl ;

   cout << "\n\n***** Insert 32 *****\n" ;
   T.insert(32) ;
   T.inorder() ; cout << endl ;

   cout << "\n\n***** Insert 33 *****\n" ;
   T.insert(33) ;
   T.inorder() ; cout << endl ;

   cout << "\n\n***** Insert 19 *****\n" ;
   T.insert(19) ;
   T.inorder() ; cout << endl ;

   cout << "\n\n***** Insert 34 *****\n" ;
   T.insert(34) ;
   T.inorder() ; cout << endl ;

   cout << "\n\n***** Insert 35 *****\n" ;
   T.insert(35) ;
   T.inorder() ; cout << endl ;

   cout << "\n\n***** Insert 36 *****\n" ;
   T.insert(36) ;
   T.inorder() ; cout << endl ;

   cout << "\n\n***** Insert 37 *****\n" ;
   T.insert(37) ;
   T.inorder() ; cout << endl ;

   cout << "\n\n***** Insert 38 *****\n" ;
   T.insert(38) ;
   T.inorder() ; cout << endl ;

   cout << "\n\n***** Insert 39 *****\n" ;
   T.insert(39) ;
   T.inorder() ; cout << endl ;

   cout << endl << endl ;
   report(T) ;

}

If you are looking for a C++ tutor or want someone to help with C++ assignment then we can deliver a solution.

p3test2.cpp

#include <iostream>
#include <cmath>
using namespace std ;

#include "ExpBST.h"

void report(const ExpBST& T) {

   cout << "***** ExpBST Report\n" ;

   cout << "   size = " << T.size() << endl ;
   cout << "   height = " << T.height() << endl ;
   cout << "   height/log(size) = " << ( (float) T.height() ) / log2(T.size()) << endl ;

   cout << "   numRebalance = " << T.getNumRebalance() << endl ;
   cout << "   failedRebalance = " << T.getFailedRebalance() << endl ;
   cout << "   exceedsHeight = " << T.getExceedsHeight() << endl ;

   cout << "   maxRebalanceDepth = " << T.getMaxRebalanceDepth() << endl ;
   cout << "   minRebalanceHeight = " << T.getMinRebalanceHeight() << endl ;
   cout << "   rebalanceFactor = " << T.getRebalanceFactor() << endl ;

}

int main() {

   ExpBST T(3, 3, 2.0) ;

   T.insert(14) ;

   T.insert(7) ;   T.insert(21) ;

   T.insert(6) ;   T.insert(22) ;
   T.insert(8) ;   T.insert(20) ;

   T.insert(5) ;   T.insert(23) ;
   T.insert(9) ;   T.insert(19) ;

   T.insert(4) ;   T.insert(24) ;
   T.insert(10);   T.insert(18) ;

   T.insert(3) ;   T.insert(25) ;
   T.insert(11);   T.insert(17) ;

   T.insert(2) ;   T.insert(26) ;
   T.insert(12);   T.insert(16) ;

   T.insert(1) ;   T.insert(27) ;
   T.insert(13);   T.insert(15) ;

   T.inorder() ;
   cout << endl << endl ;

   report(T) ;

   cout << endl ;
   cout << "removing ..." << endl;

   int n ;

   n = 27 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 26 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 25 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 24 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 23 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 22 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 21 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 20 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 19 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 18 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 17 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 16 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 15 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 9 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ;

   cout << endl ;
   report(T) ;

   return 0 ;
}

We can solve your C++ assignment for you, or if you are unable to complete the assignment yourself then we can help with C++ assignment using the code you have already completed.

p3test3.cpp

// Simple test of inserting and removing.
// This test includes inserting duplicates and
// attempt to remove keys not in the tree.
//

#include <iostream>
#include <cmath>
using namespace std ;

#include "ExpBST.h"

void report(const ExpBST& T) {

   cout << "***** ExpBST Report\n" ;

   cout << "   size = " << T.size() << endl ;
   cout << "   height = " << T.height() << endl ;
   cout << "   height/log(size) = " << ( (float) T.height() ) / log2(T.size()) << endl ;

   cout << "   numRebalance = " << T.getNumRebalance() << endl ;
   cout << "   failedRebalance = " << T.getFailedRebalance() << endl ;
   cout << "   exceedsHeight = " << T.getExceedsHeight() << endl ;

   cout << "   maxRebalanceDepth = " << T.getMaxRebalanceDepth() << endl ;
   cout << "   minRebalanceHeight = " << T.getMinRebalanceHeight() << endl ;
   cout << "   rebalanceFactor = " << T.getRebalanceFactor() << endl ;

}

int main() {

   ExpBST T(3, 4, 2.0) ;

   T.insert(14) ;

   T.insert(9) ; 
   T.insert(8) ; 
   T.insert(7) ;
   T.insert(6) ; 
   T.insert(5) ; 
   T.insert(4) ;

   T.insert(18) ; 
   T.insert(25) ;
   T.insert(32) ;

// Inserting duplicates

   T.insert(3) ; T.insert(32) ; 
   T.insert(9) ; T.insert(18) ;

   T.insert(1) ; T.insert(44) ;
   T.insert(12) ; T.insert(15) ; 
   T.insert(4) ; T.insert(29) ; 
   T.insert(10) ; T.insert(21) ;

   T.inorder() ; cout << endl ;

   cout << "removing ..." << endl; 
   int answer ;
//   T.dump() ;

   int n ;

   n = 14 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 12 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n =  7 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 25 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n =  3 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 29 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 32 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 15 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ;

// Removing items that do not exist
   cout << endl ;
   n = 19 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 101 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = -32 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   cout << endl ;

   n = 44 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 21 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 18 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n = 10 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n =  9 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n =  8 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n =  6 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n =  5 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n =  4 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ; 
   n =  1 ; cout << "removing " << n << endl ; T.remove(n) ; T.inorder() ; cout << endl ;

// Final report
   cout << endl ;
   report(T) ;

   return 0 ;
}

This is a sample C++ assignment, so if you would like help with C++ then contact us for help you can depend on.

p3test4.cpp

#include <iostream>
#include <cmath>
using namespace std ;

#include "ExpBST.h"

void report(const ExpBST& T) {

   cout << "***** ExpBST Report\n" ;

   cout << "   size = " << T.size() << endl ;
   cout << "   height = " << T.height() << endl ;
   cout << "   height/log(size) = " << ( (float) T.height() ) / log2(T.size()) << endl ;

   cout << "   numRebalance = " << T.getNumRebalance() << endl ;
   cout << "   failedRebalance = " << T.getFailedRebalance() << endl ;
   cout << "   exceedsHeight = " << T.getExceedsHeight() << endl ;

   cout << "   maxRebalanceDepth = " << T.getMaxRebalanceDepth() << endl ;
   cout << "   minRebalanceHeight = " << T.getMinRebalanceHeight() << endl ;
   cout << "   rebalanceFactor = " << T.getRebalanceFactor() << endl ;

}

int main() {

   ExpBST T(3,3,2.0) ;

   T.insert(14) ;

   T.insert(12) ; 
   T.insert(10) ; 
   T.insert(9) ; 
   T.insert(7) ;
   T.insert(4) ; 
   T.insert(3) ; 
   T.insert(1) ;

   T.insert(15) ; 
   T.insert(18) ; 
   T.insert(21) ; 
   T.insert(25) ;
   T.insert(29) ; 
   T.insert(32) ; 
   T.insert(44) ;

   T.insert(7) ;
   T.insert(3) ; T.insert(1) ; T.insert(4) ;
   T.insert(10) ; T.insert(9) ; T.insert(12) ;

   T.insert(25) ;
   T.insert(18) ; T.insert(15) ; T.insert(21) ;
   T.insert(32) ; T.insert(29) ; T.insert(44) ;

//   T.dump() ;
   T.inorder() ; cout << endl ;

   int n, answer ;

   n = 3  ;
   cout << "Find " << n << endl ;
   if ( T.find(n) ) { 
      cout << "found = " << n << endl ;
   } else {
      cout << "did not find = " << n << endl ;
   }
   cout << endl ;

   n = 4  ;
   cout << "Find " << n << endl ;
   if ( T.find(n) ) { 
      cout << "found = " << n << endl ;
   } else {
      cout << "did not find = " << n << endl ;
   }
   cout << endl ;

   n = 29  ;
   cout << "Find " << n << endl ;
   if ( T.find(n) ) { 
      cout << "found = " << n << endl ;
   } else {
      cout << "did not find = " << n << endl ;
   }
   cout << endl ;

   n = 39  ;
   cout << "Find " << n << endl ;
   if ( T.find(n) ) { 
      cout << "found = " << n << endl ;
   } else {
      cout << "did not find = " << n << endl ;
   }
   cout << endl ;

   n = 301  ;
   cout << "Find " << n << endl ;
   if ( T.find(n) ) { 
      cout << "found = " << n << endl ;
   } else {
      cout << "did not find = " << n << endl ;
   }
   cout << endl ;

// Checking remove...

   n = 21  ;
   cout << "Remove " << n << endl ;
   if ( T.remove(n) ) { 
      cout << n << " removed\n" ;
   } else {
      cout << n << " not found\n" ;
   }
   T.inorder() ; cout << endl ;

   n = 18  ;
   cout << "Remove " << n << endl ;
   if ( T.remove(n) ) { 
      cout << n << " removed\n" ;
   } else {
      cout << n << " not found\n" ;
   }
   T.inorder() ; cout << endl ;

   n = 7  ;
   cout << "Remove " << n << endl ;
   if ( T.remove(n) ) { 
      cout << n << " removed\n" ;
   } else {
      cout << n << " not found\n" ;
   }
   T.inorder() ; cout << endl ;

   n = 13  ;
   cout << "Remove " << n << endl ;
   if ( T.remove(n) ) { 
      cout << n << " removed\n" ;
   } else {
      cout << n << " not found\n" ;
   }
   T.inorder() ; cout << endl ;

   n = 29  ;
   cout << "Remove " << n << endl ;
   if ( T.remove(n) ) { 
      cout << n << " removed\n" ;
   } else {
      cout << n << " not found\n" ;
   }
   T.inorder() ; cout << endl ;

   n = 32  ;
   cout << "Remove " << n << endl ;
   if ( T.remove(n) ) { 
      cout << n << " removed\n" ;
   } else {
      cout << n << " not found\n" ;
   }
   T.inorder() ; cout << endl ;

   n = 14  ;
   cout << "Remove " << n << endl ;
   if ( T.remove(n) ) { 
      cout << n << " removed\n" ;
   } else {
      cout << n << " not found\n" ;
   }
   T.inorder() ; cout << endl ;

}

As an example C++ program this is the style of help with C++ project we are able to provide.

p3test5.cpp

#include <iostream>
using namespace std ;

#include "ExpBST.h"

int main() {

   ExpBST T1(3,3,2.0) ;

   T1.insert(14) ;

   T1.insert(9) ; 
   T1.insert(8) ; 
   T1.insert(7) ;
   T1.insert(6) ; 
   T1.insert(5) ; 
   T1.insert(4) ;

   T1.insert(18) ; 
   T1.insert(25) ;
   T1.insert(32) ;

   cout << "Original T1:         " ;
   T1.inorder() ; cout << endl ;

   // Use copy constructor
   ExpBST *Tptr = new ExpBST(T1) ;

   cout << "Copied T1:           " ;
   Tptr->inorder() ; cout << endl;

   ExpBST T2(3,3,2.0) ;

   T2.insert(50) ;
   T2.insert(25) ; T2.insert(75) ;
   // T2.inorder() ; cout << endl ;

   T2 = *Tptr ;
   cout << "Second copy:         " ;
   T2.inorder() ; cout << endl ;

   cout << "Delete first copy...\n" ;
   delete Tptr ;

   cout << "Recheck original:    " ;
   T1.inorder() ; cout << endl ;
   cout << "Recheck second copy: " ;
   T2.inorder() ; cout << endl ;

   return 0 ; 
}

Do you want help with C++ assignment, if so please think about using our service, we guarantee results or a full refund if we can’t deliver.

p3test6.cpp

#include <iostream>
#include <cmath>
using namespace std ;

#include "ExpBST.h"

void report(const ExpBST& T) {

   cout << "***** ExpBST Report\n" ;

   cout << "   size = " << T.size() << endl ;
   cout << "   height = " << T.height() << endl ;
   cout << "   height/log(size) = " << ( (float) T.height() ) / log2(T.size()) << endl ;

   cout << "   numRebalance = " << T.getNumRebalance() << endl ;
   cout << "   failedRebalance = " << T.getFailedRebalance() << endl ;
   cout << "   exceedsHeight = " << T.getExceedsHeight() << endl ;

   cout << "   maxRebalanceDepth = " << T.getMaxRebalanceDepth() << endl ;
   cout << "   minRebalanceHeight = " << T.getMinRebalanceHeight() << endl ;
   cout << "   rebalanceFactor = " << T.getRebalanceFactor() << endl ;

}

int main() {

   ExpBST T(3,3,2.0) ;

   T.insert(140) ;

   T.insert(90) ; 
   T.insert(80) ; 
   T.insert(70) ;
   T.insert(60) ; 
   T.insert(50) ; 
   T.insert(40) ; 
   T.insert(180) ; 
   T.insert(250) ;
   T.insert(320) ;

   T.insert(85) ;
   T.insert(65) ;
   T.insert(55) ;

   T.insert(120) ;
   T.insert(115) ;
   T.insert(125) ;

   T.inorder() ; cout << endl ;

   int key = 9999 ;
   bool ans ;
   const char *str ;

   ans = T.locate(str="", key=-1) ;
   cout << str << ": " << ans << " " << key << endl ;

   ans = T.locate(str="LL", key=-1) ;
   cout << str << ": " << ans << " " << key << endl ;

   ans = T.locate(str="LLR", key=-1) ;
   cout << str << ": " << ans << " " << key << endl ;

   ans = T.locate(str="RRLR", key=-1) ;
   cout << str << ": " << ans << " " << key << endl ;

}

This is one example of the soirt of help with C++ homework we can provide, but if you need something specific let us know and we can deliver.

p3test7.cpp

#include <iostream>
#include <stdexcept>
#include <cmath>
#include <set>
using namespace std ;

#include "ExpBST.h"

const int depthLimit = 50 ;

// This function recursively checks if a ExpBST is correct, by checking:
//
//   1. keys are in order
//   2. left subtree is not more than twice the size of right subtree
//      or vice versa
//
// This function relies on locate() member function working correctly.
//
// Parameters:  
//   ExpBST& T  = tree to be checked, passed by reference
//   char pos[]  = must be pre-allocated with depthLimit chars
//   int& key    = stores key in node indicated by pos, if it exists
//   int& height = stores height of node indicated by pos, if it exists
//   int& size   = stores size of node indicated by pos, if it exists
//   bool report = give report for current node? defaults to true.
//
// Return value:
//    true if T has a node at pos
//    false if T does not have a node at pos
//

bool sanityCheck(ExpBST& T, char pos[], int depth, int& key, int& height, int& size, bool report=true) {

   int leftKey, rightKey ;
   int leftHeight=-1, rightHeight=-1 ;
   int leftSize=0, rightSize=0 ;
   bool hasLeft, hasRight ;

   // Try to catch bad BST with cycles
   //
   if (depth >= depthLimit) {
      throw out_of_range("Depth limit reached. Something looks wrong!\n") ;
   }

   // Is does current position have a node?
   //
   if ( ! T.locate(pos, key) ) return false ;

   // Add extra '\0' so pos string can be extended
   //
   pos[depth+1] = '\0' ;

   // Recursively checks left subtree.
   //
   pos[depth] = 'L' ;
   hasLeft= sanityCheck(T, pos, depth+1, leftKey, leftHeight, leftSize, report) ;

   // Recursively checks right subtree.
   //
   pos[depth] = 'R' ;
   hasRight= sanityCheck(T, pos, depth+1, rightKey, rightHeight, rightSize, report) ;

   pos[depth] = '\0' ;  // restores pos[]

   // Compute current node's height and size
   //
   height = 1 + ( (leftHeight > rightHeight) ? leftHeight : rightHeight ) ; 
   size = 1 + leftSize + rightSize ;

   // Check key ordering for left child
   //
   if (hasLeft && leftKey >= key) {
      cerr << "\nIn position " << pos 
           << " (key=" << key << ",height=" << height << ",size=" << size << ")"
           << " left child's key not less than current node's key:"
       << leftKey << " " << key << endl ;
   }

   // Check key ordering for right child
   //
   if (hasRight && rightKey <= key) {
      cerr << "\nIn position " << pos 
           << " (key=" << key << ",height=" << height << ",size=" << size << ")"
           << " right child's key not greater than current node's key:"
       << rightKey << " " << key << endl ;
   }

   // Check height <= RebalanceFactor * log2(size)
   //
   float factor =  T.getRebalanceFactor() ;

   if (height > T.getMinRebalanceHeight() ) {
      if ( height > factor * log2(size) ) {
     cerr << "\nIn position " << pos 
              << " (key=" << key << ",height=" << height << ",size=" << size << ")"
          << " tree too tall, " << factor <<  "* log(size) = "
          << factor * log2(size) << endl ;
      }
   }

   // Give stats for current node, if so desired.
   //

   if (report) {
      cout << "\nNode report on position " << pos << " :" << endl ;
      cout << "   key = " << key 
       << "   height = " << height 
       << "   size = " << size 
       << endl ;

      if (hasLeft) {
     cout << "   left child key = " << leftKey << endl ;
      } else {
     cout << "   no left child\n" ;
      }

      if (hasRight) {
     cout << "   right child key = " << rightKey << endl ;
      } else {
     cout << "   no right child\n" ;
      }
   }

   return true ;

}

bool checkAgainstSTLSet (ExpBST& T, set<int>& S) {

   if (T.size() != S.size() ) {
      cout << "\nError: sizes mismatched:\n" ;
      cout << "   T.size() = " << T.size() << endl ;
      cout << "   S.size() = " << S.size() << endl ;
      return false ;
   }

   set<int>::iterator it ;
   const int *ptr ;
   for (it = S.begin() ; it != S.end() ; it++) {
      if (! T.find(*it) ) {
         cout << "\nError: " << *it << " in S but not in T.\n" ;
     return false ;
      }
   }
   return true ;
}

void report(const ExpBST& T) {

   cout << "***** ExpBST Report\n" ;

   cout << "   size = " << T.size() << endl ;
   cout << "   height = " << T.height() << endl ;
   cout << "   height/log(size) = " << ( (float) T.height() ) / log2(T.size()) << endl ;

   cout << "   numRebalance = " << T.getNumRebalance() << endl ;
   cout << "   failedRebalance = " << T.getFailedRebalance() << endl ;
   cout << "   exceedsHeight = " << T.getExceedsHeight() << endl ;

   cout << "   maxRebalanceDepth = " << T.getMaxRebalanceDepth() << endl ;
   cout << "   minRebalanceHeight = " << T.getMinRebalanceHeight() << endl ;
   cout << "   rebalanceFactor = " << T.getRebalanceFactor() << endl ;
//   printf("   rebalanceFactor = %f\n", rebalanceFactor) ;

}

int main() {

   ExpBST T(3,5,1.5) ;
   set<int> S ;

   // add a bunch of numbers
   //
   T.insert(70) ;
   T.insert(30) ;
   T.insert(110) ;
   T.insert(40) ;
   T.insert(20) ;
   T.insert(41) ;
   T.insert(31) ;
   T.insert(32) ;
   T.insert(33) ;
   T.insert(19) ;
   T.insert(34) ;
   T.insert(15) ;
   T.insert(14) ;
   T.insert(38) ;
   T.insert(81) ;
   T.insert(95) ;
   T.insert(43) ;
   T.insert(17) ;

   S.insert(70) ;
   S.insert(30) ;
   S.insert(110) ;
   S.insert(40) ;
   S.insert(20) ;
   S.insert(41) ;
   S.insert(31) ;
   S.insert(32) ;
   S.insert(33) ;
   S.insert(19) ;
   S.insert(34) ;
   S.insert(15) ;
   S.insert(14) ;
   S.insert(38) ;
   S.insert(81) ;
   S.insert(95) ;
   S.insert(43) ;
   S.insert(17) ;

   T.inorder() ; cout << endl ;

   char pos[depthLimit] ;
   pos[0] = '\0' ;
   int key, height, size ;

   // Do check
   //
   cout << "First a small test...\n" ;
   sanityCheck(T,pos,0,key,height,size) ;
   cout << "\n\nSmall tree has root with key=" << key
        << ", height=" << height 
    << ", size=" << size 
    << endl;

   if ( checkAgainstSTLSet(T,S) )  {
      cout << "Passed check against STL set S\n" ;
   } else {
      cout << "*** Failed check against STL set S\n" ;
   }

   report(T) ;

   cout << endl << endl ;

   cout << "Now a big test...\n" ;

   ExpBST::resetStats() ;

   ExpBST T2(3,5,2.0) ;
   set<int> S2 ;

   for (int i=1000 ; i<1500 ; i++) {
      T2.insert(i) ;
      S2.insert(i) ;
   }
   for (int i=1200 ; i<1300 ; i++) {
      T2.remove(i) ;
      S2.erase(i) ;
   }
   for (int i=250 ; i<900 ; i++) {
      T2.insert(i) ;
      S2.insert(i) ;
   }
   for (int i=450 ; i<650 ; i++) {
      T2.remove(i) ;
      S2.erase(i) ;
   }
   for (int i=3000 ; i>1600 ; i--) {
      T2.insert(i) ;
      S2.insert(i) ;
   }
   for (int i=2700 ; i>2300 ; i--) {
      T2.remove(i) ;
      S2.erase(i) ;
   }
   for (int i=3500 ; i<6000 ; i++) {
      T2.insert(i) ;
      S2.insert(i) ;
   }
   for (int i=4200 ; i<4750 ; i++) {
      T2.remove(i) ;
      S2.erase(i) ;
   }

   sanityCheck(T2,pos,0,key,height,size,false) ;
   cout << "\n\nBig tree has root with key=" << key
        << ", height=" << height 
    << ", size=" << size 
    << endl;

   if ( checkAgainstSTLSet(T2,S2) )  {
      cout << "Passed check against STL set S2\n" ;
   } else {
      cout << "*** Failed check against STL set S2\n" ;
   }

   report(T2) ;

}

If you want help with your C++ proect or are looking for a C++ online tutor to help you complete your C++ proect then we can provide that for you.

p3test8.cpp

// Use on command line: 
//
//   ./p3test8.out 1500 3 4 2.0
//
// 1500 = # of reps
// 3 = depth
// 4 = smallest height for rebalance
// 2.0 = factor
//

#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std ;

#include "ExpBST.h"

void report(const ExpBST& T) {

   cout << "***** ExpBST Report\n" ;

   cout << "   size = " << T.size() << endl ;
   cout << "   height = " << T.height() << endl ;
   cout << "   height/log(size) = " << ( (float) T.height() ) / log2(T.size()) << endl ;

   cout << "   numRebalance = " << T.getNumRebalance() << endl ;
   cout << "   failedRebalance = " << T.getFailedRebalance() << endl ;
   cout << "   exceedsHeight = " << T.getExceedsHeight() << endl ;

   cout << "   maxRebalanceDepth = " << T.getMaxRebalanceDepth() << endl ;
   cout << "   minRebalanceHeight = " << T.getMinRebalanceHeight() << endl ;
   cout << "   rebalanceFactor = " << T.getRebalanceFactor() << endl ;
}

int main(int argc, char* argv[]) {

   if (argc < 4) {
      cout << "Usage: " << argv[0]
           << " reps depth min_height factor.\n" ;
      return 1 ;
   }

   int n = atoi(argv[1]) ;
   int depth = atoi(argv[2]) ;
   int min_height = atoi(argv[3]) ;
   float factor = atof(argv[4]) ;

   ExpBST T(depth, min_height, factor) ;

   for(int k = 1 ; k < 2 * n ; k++) {
      T.insert(k) ;
   }

   for (int k = n/2 ; k < n + n/2 ; k++) {
      T.remove(k) ;
   }

   report(T) ;
}

The following C++ assignment, is an example C++ assignment which demonstrates a potential solution, we’ve done as many as six versions of the same assignment and each was completely unique (not just the variable names, and functions but the algorithms used, and the type of constructs).

test9.cpp

// Use on command line: 
//
//   ./p3test8.out 1500 3 4 2.0
//
// 1500 = # of reps
// 3 = depth
// 4 = smallest height for rebalance
// 2.0 = factor
//

#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std ;

#include "ExpBST.h"

void report(const ExpBST& T) {

   cout << "***** ExpBST Report\n" ;

   cout << "   size = " << T.size() << endl ;
   cout << "   height = " << T.height() << endl ;
   cout << "   height/log(size) = " << ( (float) T.height() ) / log2(T.size()) << endl ;

   cout << "   numRebalance = " << T.getNumRebalance() << endl ;
   cout << "   failedRebalance = " << T.getFailedRebalance() << endl ;
   cout << "   exceedsHeight = " << T.getExceedsHeight() << endl ;

   cout << "   maxRebalanceDepth = " << T.getMaxRebalanceDepth() << endl ;
   cout << "   minRebalanceHeight = " << T.getMinRebalanceHeight() << endl ;
   cout << "   rebalanceFactor = " << T.getRebalanceFactor() << endl ;
}

int main(int argc, char* argv[]) {

   if (argc < 4) {
      cout << "Usage: " << argv[0]
           << " reps depth min_height factor.\n" ;
      return 1 ;
   }

   int n = atoi(argv[1]) ;
   int depth = atoi(argv[2]) ;
   int min_height = atoi(argv[3]) ;
   float factor = atof(argv[4]) ;

   int m = sqrt(n) / 2 ;

   ExpBST T(depth, min_height, factor) ;

   for (int j = 0 ; j < m ; j++) {

      int base = 4 * j * m ;

      for(int k = base ; k < base + 4 * m ; k++) {
     T.insert(k) ;
      }

      for (int k = base + m ; k < base + 2 * m ; k++) {
     T.remove(k) ;
      }
   }

   report(T) ;
}

If you want help with your C++ project then look at this example.

Typescript.sh

#!/bin/bash
time ./t8.out 100000 3 5 2.0
time ./t8.out 200000 3 5 2.0
time ./t8.out 400000 3 5 2.0
time ./t9.out 100000 3 5 2.0
time ./t9.out 200000 3 5 2.0
time ./t9.out 400000 3 5 2.0

Below is a C++ homework, but if you just want a C++ online tutor then we can do that for you as well.

Compile.sh

#!/bin/bash
g++ -g -I . Driver.cpp ExpBST.cpp -o Driver.out
g++ -g -I . p3test1.cpp ExpBST.cpp -o t1.out
g++ -g -I . p3test2.cpp ExpBST.cpp -o t2.out
g++ -g -I . p3test3.cpp ExpBST.cpp -o t3.out
g++ -g -I . p3test4.cpp ExpBST.cpp -o t4.out
g++ -g -I . p3test5.cpp ExpBST.cpp -o t5.out
g++ -g -I . p3test6.cpp ExpBST.cpp -o t6.out
g++ -g -I . p3test7.cpp ExpBST.cpp -o t7.out
g++ -g -I . p3test8.cpp ExpBST.cpp -o t8.out
g++ -g -I . p3test9.cpp ExpBST.cpp -o t9.out

Index:

You may contact us to provide the C++ homework help that you need.