Bug in AVL tree code, data structures c++

Question

I am really trying to figure out the bug in my code I wrote for AVL tree but there seems to be a bug in it.

It calls the rotation functions but when it finishes rotation there are several problem:

1. root doesn't change
2. only root value is displayed when in-order traversal is done, other values seem to disappear

I have been trying to fix this bug since 2-3 days but cant seem to solve it.

Would love some help from you guys. I will be attaching the code with this.

/*
insertion
rotations all DONE
level order DONE
deletion
*/
#include <iostream>
#include <queue>
using namespace std;

struct node
{
    int data;
    int height;
    node *left;
    node *right;

    node()
    {
        height = 0;
        left = right = NULL;
    }
};

class AVL
{
public:
    node *root;

    AVL()
    {
        root = NULL;
    }
    // search function
    bool search(int num)
    {
        node *nodePtr = root;

        if (root->data == num)
        {
            cout << "FOUND " << endl;
            return true;
        }

        else
        {
            while (nodePtr != NULL)
            {
                if (nodePtr->data < num)
                {
                    nodePtr = nodePtr->right;
                }

                else if (nodePtr->data > num)
                {
                    nodePtr = nodePtr->left;
                }

                else
                {
                    cout << "FOUND " << endl;
                    return true;
                }
            }
            cout << "NOT FOUND " << endl;
            return false;
        }
    }
    // inorder
    void inorder()
    {
        inorder(root);
    }
    // postorder
    void postorder()
    {
        postorder(root);
    }
    // preorder
    void preorder()
    {
        preorder(root);
    }
    // inorder utility function
    void inorder(node *&nodePtr)
    {
        if (nodePtr)
        {
            inorder(nodePtr->left);
            cout << nodePtr->data << ", ";
            inorder(nodePtr->right);
        }
    }
    // preorder utility function
    void preorder(node *&nodePtr)
    {
        if (nodePtr)
        {
            cout << nodePtr->data << ", ";
            preorder(nodePtr->left);
            preorder(nodePtr->right);
        }
    }
    // postorder utility function
    void postorder(node *&nodePtr)
    {
        if (nodePtr)
        {
            postorder(nodePtr->left);
            postorder(nodePtr->right);
            cout << nodePtr->data << ", ";
        }
    }
    // returns the number of nodes in the tree
    int size(node *&nodePtr)
    {
        if (!nodePtr)
        {
            return 0;
        }

        else
        {
            return  (size(nodePtr->left) + size(nodePtr->right)) + 1;
        }
    }
    // function to check if tree is empty or not
    bool isempty()
    {
        if (root == NULL)
        {
            return true;
        }

        else
        {
            return false;
        }
    }
    // max function to calculate height and also the balance factor
    int maximum(int x, int y)
    {
        if (x>y)
        {
            return x;
        }

        else
        {
            return y;
        }
    }
    // returns the level of the tree
    int returnHeight(node *&nodePtr)
    {
        if (nodePtr == NULL)
        {
            return 0;
        }

        else
        {
            return nodePtr->height;
        }
    }
    // assigning the height to the node
    void assignHeightToNode(node *&nodePtr)
    {
        int left = returnHeight(nodePtr->left);
        int right = returnHeight(nodePtr->right);
        nodePtr->height = maximum(left, right) + 1;
    }
    // single left rotate
    node *singleLeftRotate(node *&nodePtr)
    {
        //      if (nodePtr==NULL)
        //      {
        //          return;
        //      }

        node * b = nodePtr->right;
        nodePtr->right = b->left;
        b->left = nodePtr;
        return b;
    }
    // single right rotate
    node *singleRightRotate(node *&nodePtr)
    {
        //      if (nodePtr==NULL)
        //      {
        //          return ;
        //      }

        node * b = nodePtr->left;
        nodePtr->left = b->right;
        b->right = nodePtr;
        assignHeightToNode(nodePtr);
        assignHeightToNode(b);
        return b;
    }
    // double left rotate
    node *doubleLeft(node *&nodePtr)
    {
        nodePtr->right = singleRightRotate(nodePtr->right);
        return singleLeftRotate(nodePtr);
    }
    // double right rotate
    node *doubleRight(node *&nodePtr)
    {
        nodePtr->left = singleLeftRotate(nodePtr->left);
        return singleRightRotate(nodePtr);
    }
    //   insert function
    void insert1(int x)
    {
        cout << "NOW INSERTING " << x << endl;
        insert2(x, root);
    }
    // insert utility function
    void insert2(int &x, node *&nodePtr)
    {

        if (nodePtr == NULL)
        {
            node *newNode = new node;
            newNode->data = x;
            newNode->height = 0;
            nodePtr = newNode;
            checkRotations(nodePtr, x);
            return;
        }

        else
        {
            if (x < nodePtr->data)
            {
                cout << endl << "GOING LEFT " << endl;
                insert2(x, nodePtr->left);
            }

            else if (x > nodePtr->data)
            {
                cout << endl << "GOING RIGHT " << endl;
                insert2(x, nodePtr->right);
            }

            else if (nodePtr->data == x)
            {
                cout << "DUPLICATE VALUES NOT ALLOWED " << endl;
                return;
            }
        }
        checkRotations(nodePtr, x);
    }
    // checking if rotations needed
    void checkRotations(node *&nodePtr, int &x)
    {
        assignHeightToNode(nodePtr);

        cout << endl << endl << "HEIGHT OF " << nodePtr->data << " IS " << nodePtr->height << endl;
        int bf = returnHeight(nodePtr->left) - returnHeight(nodePtr->right);
        cout << endl << endl << "BALANCE FACTOR AT NODE " << nodePtr->data << " IS " << bf << endl;

        if (bf < -1 || bf > 1)
        {
            cout << endl << endl << "ROTATION IS HAPPEENING " << endl << endl;
            if (x > nodePtr->data)
            {
                singleLeftRotate(nodePtr);
                cout << endl << "ROTATION DONE SINGLE LEFT " << endl;
                return;
            }

            else if (x < nodePtr->data)
            {
                singleRightRotate(nodePtr);
                cout << endl << "ROTATION DONE SINGLE RIGHT " << endl;
                return;
            }

            else if (x < root->data && x > root->left->data)
            {
                doubleRight(nodePtr);
                cout << endl << "ROTATION DONE DOUBLE LEFT " << endl;
                return;
            }

            else if (x > root->data && x < root->right->data)
            {
                doubleLeft(nodePtr);
                cout << endl << "ROTATION DONE DOUBLE LEFT " << endl;
                return;
            }
        }
    }
    // level order display code
    void levelOrderDisplay()
    {
        levelOrderDisplay2(root);
    }
    // level order display utility function
    void levelOrderDisplay2(node *&nodePtr)
    {
        if (nodePtr == NULL)
        {
            cout << "THE TREE IS EMPTY" << endl;
            return;
        }

        queue <node *> displayer;
        displayer.push(nodePtr);

        while (!displayer.empty())
        {
            node *currentNode = displayer.front();
            cout << currentNode->data << ", ";

            if (currentNode->left != NULL)
            {
                displayer.push(currentNode->left);
            }

            else if (currentNode->right != NULL)
            {
                displayer.push(currentNode->right);
            }
            displayer.pop();
        }
    }

    void rootD()
    {
        cout << "root is " << root->data << endl;
    }
};

int main()
{
    AVL tree;
    tree.insert1(3);
    tree.insert1(2);
    tree.insert1(1);

    tree.insert1(4);
    tree.insert1(5);
    tree.insert1(6);
    tree.insert1(7);
    tree.inorder();
    //  tree.rootD();

    //  tree.levelOrderDisplay();
    //  tree.rootD();

    return 0;
}

Answer 1

Really late answer, but this is what you had to do. You should set the node passed in the function equal to the temporary node made in the function. In coding language, nodePtr=b should have been the last line of the single rotate functions.

Hope this helps :)

Answer 2

I suggest you that do not pass node pointer by reference where your code does not change pointer value such as print. Try this... I completed my avl tree code just 2 3 day before and i have similar problem, when i debug my program i came to know that somehow in print function my pointer value is changed because i passed it by reference..... So.. Try this and see if work or not.... Hope this might help you.