AVL Tree Help

[GybDjE8b]

Whenever i compile it my height output is giving me 0 1 0 1....
this shouldn't be happening.... Can any1 explain why and check if my insert_internal & my rotation if it is correct

  class AVLSearch
{
    public:
    AVLSearch(){
        root = NULL;
    }
    void insert(int key, string value);
    string search(int key);
    int getHeight();
    bool delete_node(int key);
    int getbalance(Node *node);

    private:
    Node *root;
    int delete_internal(Node*& root, int key);
    Node* popMinNode(Node*& root);
    void insert_internal(Node* &root, Node* newptr);
    string search_internal(Node* root, int key);
    int getHeight_internal(Node* root);
    Node* rightRotate(Node* y);
    Node* leftRotate(Node* x);
};


bool AVLSearch::delete_node(int key)
{
    int del = delete_internal(root, key);
    if(del == 0)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}


int AVLSearch::getHeight()
{
       return getHeight_internal(root);
}

int AVLSearch::getHeight_internal(Node *node)
{
    if(node == NULL)  return -1;
    else
    {
        int h_left = getHeight_internal(node->leftchild);
        int h_right = getHeight_internal(node->rightchild);
        cout << h_left << " " << h_right << endl;
        if(h_left >= h_right)
        {
            return h_left + 1;
        }
        else
        {
            return h_right + 1;
        }
    }
}


string AVLSearch::search(int key)
{
    return search_internal(root, key);
}

string AVLSearch::search_internal(Node *root, int key)
{
    if(root == NULL)
    {
       return "Not found";
    }
    else if(root->key == key)
    {
       return root->value;
    }
    else if(root->key > key)
    {
        return search_internal(root->leftchild, key);
    }
    else if(root->key < key)
    {
        return search_internal(root->rightchild, key);
    }
}

int AVLSearch::delete_internal(Node*& root, int key)
{
    if(root == NULL)
    {
        return 0;
    }
    else if(root->key > key)
    {
        return delete_internal(root->leftchild, key);
    }
    else if(root->key < key)
    {
        return delete_internal(root->rightchild, key);
    }
    else if(root->key == key)
    {
    if(root->leftchild == NULL && root->rightchild == NULL)
    {
            delete root;
                root = NULL;
    }
    else if(root->leftchild == NULL && root->rightchild != NULL)
    {
        Node * temp = root->rightchild;
        delete root;
        root = temp;
    }
    else if(root->rightchild == NULL && root->leftchild != NULL)
    {
        Node * temp = root->leftchild;
                delete root;
                root = temp;
    }
    else
    {
        Node* min = popMinNode(root->rightchild);
        cout << "Min key : " << min->key << endl;
        root->key = min->key;
                root->value = min->value;
    }
    return 1;
    }
}

Node* AVLSearch::popMinNode(Node*& root)
{
    if(root->leftchild == NULL)
    {
        Node *temp = root;
        root = root->rightchild;
        return temp;
    }
    else
    {
        return popMinNode(root->leftchild);
    }
}


void AVLSearch::insert(int key, string value)
{
    Node *newptr = new Node(key, value);
    insert_internal(root, newptr);
}


void AVLSearch::insert_internal(Node* &root, Node* newptr)
{
    if(root == NULL)
    {
           root = newptr;
    }
    else if(root->key > newptr->key)
    {
        insert_internal(root->leftchild, newptr);
    }
    else if(root->key < newptr->key)
    {
        insert_internal(root->rightchild, newptr);
    }
    
    int balance = getbalance(root);

    if (balance > 1 && newptr->key < root->leftchild->key)
        rightRotate(root);

    // Right Right Case
    else if (balance < -1 && newptr->key > root->rightchild->key)
        leftRotate(root);

    // Left Right Case
    else if (balance > 1 && newptr->key > root->leftchild->key)
    {
        root->leftchild =  leftRotate(root->leftchild);
        rightRotate(root);
    }
    // Right Left Case
    else if (balance < -1 && newptr->key < root->rightchild->key)
    {
        root->rightchild = rightRotate(root->rightchild);
        leftRotate(root);
    }

}
Node* AVLSearch::rightRotate(Node *y)
{
    Node *x = y->leftchild;
    Node *T2 = x->rightchild;
    x->rightchild= y;
    y->leftchild = T2;
    return x;
}
Node* AVLSearch::leftRotate(Node *x)
{
    Node *y = x->rightchild;
    Node *T2 = y->leftchild;
    y->leftchild = x;
    x->rightchild = T2;
    return y;
}

int AVLSearch::getbalance(Node *node)
{
    int h_left = getHeight_internal(node->leftchild);
    int h_right = getHeight_internal(node->rightchild);
    return (h_left - h_right);
}




int main()
{
    cout << "Hello World" << endl;
    AVLSearch bst;
    bst.insert(1001,"Hello");
    cout << "Height : " << bst.getHeight() << endl;
    bst.insert(1002,"World");
    cout << "Height : " << bst.getHeight() << endl;
    bst.insert(1003,"What");
    cout << "Height : " << bst.getHeight() << endl;
    bst.insert(1004,"Where");
    cout << "Height : " << bst.getHeight() << endl;
    bst.insert(1005,"Which");
    cout << "Height : " << bst.getHeight() << endl;
    cout << bst.search(1001) << endl;
    bst.delete_node(1001);
    cout << bst.search(1001) << endl;
    cout << "New Height : " << bst.getHeight() << endl;
    return 0;
}

[TheIdeasMan]

Hi,

The easiest thing to do, is to use a debugger, this will save you days of staring at code.

Hopefully there will be a GUI one in your IDE somewhere.

Set some breakpoints before where you think there might be a problem.

Make a watch list of variables, of whose values you want to keep an eye on.

When the break point is hit, step through 1LOC at a time, look at the values, and deduce where things went wrong.

[Smac89]

Just wanted to make a point:

int AVLSearch::getHeight_internal(Node *node)
{
    if(node == NULL)  return -1;
    else
    {
        int h_left = getHeight_internal(node->leftchild);
        int h_right = getHeight_internal(node->rightchild);
        cout << h_left << " " << h_right << endl;
        if(h_left >= h_right)
        {
            return h_left + 1;
        }
        else
        {
            return h_right + 1;
        }
    }
}

This is not how height information is stored in an AVL tree. Doing this will make the performance worse than that of a normal balanced tree. Height information is stored at each node i.e. each node knows what level it is located on the tree

[GybDjE8b]

I've tried to set up breakpoints to check when i do the getheight it shows -1 for leftchild all the time i dont get why
and whenever i do h_left - h_right it obviously gonna be more of a negative number