Balanced Insert Heap Example, C++ (clang)

Language: Layout:

// Balanced Heap Insert Example program using TreeNode
#include <algorithm>
#include <iostream>
using namespace std;

template<class ItemType>
class TreeNode
{
private:
   ItemType  item; // A data item
   int height; // height of node in tree, a leaf has height 1
   TreeNode<ItemType>* leftChild; // Pointer to left child
   TreeNode<ItemType>* rightChild; // Pointer to left child
   
public:
    TreeNode() {leftChild = nullptr; rightChild = nullptr; height = 1;};
    void setItem(const ItemType& anItem) {item = anItem;};
    void setHeight(int h) {height = h;};
    void setLeft(TreeNode<ItemType>* treeNodePtr) {leftChild = treeNodePtr;};
    void setRight(TreeNode<ItemType>* treeNodePtr) {rightChild = treeNodePtr;};
    ItemType getItem() const {return item;};
    int getHeight() const {return height;};
    TreeNode<ItemType>* getLeft() const {return leftChild;};
    TreeNode<ItemType>* getRight() const {return rightChild;};
}; // end TreeNode

template<class ItemType>
void preorderSearch(TreeNode<ItemType> *node)
{
    if (node == nullptr) return;
    cout << node->getItem() << " ";
    preorderSearch(node->getLeft());
    preorderSearch(node->getRight());
}

template<class ItemType>
int setHeight(TreeNode<ItemType> *node)
{
    if (node == nullptr) return 0;
    int leftHeight = setHeight(node->getLeft());
    int rightHeight = setHeight(node->getRight());
    int height = std::max(leftHeight,rightHeight) + 1;
    node->setHeight(height);
    return height;
}

template<class ItemType>
void insert(TreeNode<ItemType>* node, ItemType value)
{
    // swap value based on minHeap criteria
    if (value < node->getItem()) {
        ItemType temp = node->getItem();
        node->setItem(value);
        value = temp;
    }
    if (node->getHeight() == 1) // leaf, insert on left
    {
        TreeNode<ItemType> *newNode = new TreeNode<ItemType>;
        newNode->setItem(value);
        node->setLeft(newNode);
        return;
    }
    if (node->getRight()==nullptr) // insert on right if not leaf and right is nullptr
    {
        TreeNode<ItemType> *newNode = new TreeNode<ItemType>;
        newNode->setItem(value);
        node->setRight(newNode);
        return;
    }
    if (node->getLeft()->getHeight() <= node->getRight()->getHeight()) // insert on left if height <= right height
    {
        insert(node->getLeft(),value);
    } 
    else // otherwise right
    {
        insert(node->getRight(),value);
    }
    return;
}

int log2func(int x)
{
    int returnValue = 0;
    while (x > 0) {
        x = x >> 1;
        returnValue++;
    }
    return returnValue;
}
        
int main()
{
    cout << "*** Tree Example Program for ECE 2574 ***\n\n";
    int testSize = 30000;

// set root and search tree
    TreeNode<int> rootNode;
    rootNode.setItem(testSize + 1);
    TreeNode<int> *root = &rootNode;    
    int treeSize = 1;
    int height = setHeight(root);;
    
    // add nodes using insert
    float maxRatio = 1.0;
    for (int i = 1; i <= testSize; i++) 
    {
        insert(root,i);
        height = setHeight(root);
        treeSize++;
        int optimalHeight = log2func(treeSize);
        float ratio = (float)height/(float)optimalHeight;
        if (ratio > maxRatio) maxRatio = ratio;
        /*
        cout << "Inserted value " << i << " and new height = " << height << 
            " Optimal Tree Height = " << optimalHeight << " Tree size = "
            << treeSize  << " Ratio = " << (float)height/(float)optimalHeight << endl;
            */
    }
    cout << "Max ratio of tree height to optimal tree height = " << maxRatio;

cout << endl;
    //preorderSearch(root);
    cout << endl;
    cout << "Height of tree is " << height << endl;
    
    return 0;
}

Show compiler warnings [ + ] Compiler args [ + ] Show input
Compilation time: 1.46 sec, absolute running time: 6.34 sec, cpu time: 8.74 sec, memory peak: 3 Mb, absolute service time: 7,81 sec