AVL Tree crashes on remove

[Bill Horstkamp]

Hello, I am trying to program a simple AVL Tree, but it crashes when removing in some cases, I am pretty sure the problem is with remove() not balancedup(), here is my whole code.

#include <iostream>
#include "BalancedTree.h"


using namespace std;


Node::Node()
{
    left = NULL;
    right = NULL;
    height = 0;
}


Node::Node(int input)
{
    data = input;
    left = NULL;
    right = NULL;
    height = 0;
}


Node::~Node()
{
  if (left != NULL)
    delete left;
  if (right != NULL)
    delete right; 
}


AVLTree::AVLTree()
{
    root = NULL;
}


AVLTree::~AVLTree()
{
    delete root;
}


void AVLTree::balanceup(Node*& p)
{
    if ((bsheight(p->left) - bsheight(p->right))==2)
    {
        if ((bsheight(p->left->left) - bsheight(p->left->right)) == 1)
            p = srl(p);
        if ((bsheight(p->left->right) - bsheight(p->left->left)) == 1)
            p = drl(p);
        if ((bsheight(p->left->left) - bsheight(p->left->right)) == 0)
            p = srl(p);
    }
    else if ((bsheight(p->right) - bsheight(p->left))==2)
    {
        if ((bsheight(p->right->left) - bsheight(p->right->right)) == 1)
            p = drr(p);
        if ((bsheight(p->right->right) - bsheight(p->right->left)) == 1)
            p = srr(p);
        if ((bsheight(p->right->left) - bsheight(p->right->right)) == 0)
            p = srr(p);
    }
    else if ((bsheight(p->left) - bsheight(p->right))==1)
        return;
    else if ((bsheight(p->right) - bsheight(p->left))==1)
        return;
    int m,n,d;
    m=bsheight(p->left);
    n=bsheight(p->right);
    d=max(m,n);
    p->height = d + 1;
    if (p->left != NULL)
    {
        m=bsheight(p->left->left);
        n=bsheight(p->left->right);
        d=max(m,n);
        p->left->height = d + 1;
    }
    if (p->right != NULL)
    {
        m=bsheight(p->right->left);
        n=bsheight(p->right->right);
        d=max(m,n);
        p->right->height = d + 1;
    }
}
void AVLTree::balance(Node*& p)
{
    if ((bsheight(p->left) - bsheight(p->right))==2)
    {
        if ((bsheight(p->left->left) - bsheight(p->left->right)) == 1)
            p = srl(p);
        if ((bsheight(p->left->right) - bsheight(p->left->left)) == 1)
            p = drl(p);
    }
    else if ((bsheight(p->right) - bsheight(p->left))==2)
    {
        if ((bsheight(p->right->left) - bsheight(p->right->right)) == 1)
            p = drr(p);
        if ((bsheight(p->right->right) - bsheight(p->right->left)) == 1)
            p = srr(p);
    }
    int m,n,d;
    m=bsheight(p->left);
    n=bsheight(p->right);
    d=max(m,n);
    p->height = d + 1;
    if (p->left != NULL)
    {
        m=bsheight(p->left->left);
        n=bsheight(p->left->right);
        d=max(m,n);
        p->left->height = d + 1;
    }
    if (p->right != NULL)
    {
        m=bsheight(p->right->left);
        n=bsheight(p->right->right);
        d=max(m,n);
        p->right->height = d + 1;
    }
}


void AVLTree::insert(int x)
{
    insert(x, root);
}


void AVLTree::insert(int x,Node*& p)
{
    if (root == NULL)
    {
        root = new Node(x);
    }
    else if (p == NULL)
    {
        p = new Node(x);
    }
    else
    {
        if (x<p->data)
        {
            if (p->left == NULL)
                p->left = new Node(x);
            else
                insert(x,p->left);
            balance(p);
        }
        else if (x>p->data)
        {
            if (p->right == NULL)
                p->right = new Node(x);
            else
                insert(x,p->right);
            balance(p);
        }
    }
}


int AVLTree::next(int x)
{
    int out = next(x, -1, root);
    return out;
}


int AVLTree::next(int x,int max, Node*& p)
{
    if (p==NULL)
    {
        return max;
    }
    else
    {
        if (x == p->data)
            return p->data;
        else if (x < p->data)
        {
            if (max == -1)
                next (x, p->data, p->left);
            else if(max > p->data)
                next(x, p->data, p->left);
            else if (max < p ->data)
                next(x, max, p->left);
        }
        else if (x > p->data)
            next(x, max, p->right);
    }
}


Node*& AVLTree::getMax(Node*& curr){
    if (curr -> right != NULL)
        return getMax(curr -> right);
    else
        return curr;
}


void AVLTree::remove(int x)
{
    remove(x, root);
}


void AVLTree::remove(int x,Node*& p)
{
    Node* d;
    if (p==NULL)
    {
        cout<<"Sorry! data not found\n"<<endl;
    }
    else if ( x < p->data)
    {
        remove(x,p->left);
        balanceup(p);
    }
    else if (x > p->data)
    {
        remove(x,p->right);
        balanceup(p);
    }
    else if ((p->left == NULL) && (p->right == NULL))
    {
        d=p;
        p=NULL;
        delete d;
    }
    else if (p->left == NULL)
    {
        d=p;
        p=p->right;
        delete d;
        balanceup(p);
    }
    else if (p->right == NULL)
    {
        d=p;
        p=p->left;
        delete d;
        balanceup(p);
    }
    else
    {    
        Node*& m = getMax(p->left);
        p->data = m->data;
        remove(m->data, m);
        balanceup(p);
    }
}


void AVLTree::preorder()
{
    preorder(root);
}


void AVLTree::preorder(Node* p)
{
    if (p!=NULL)
    {
        cout<<p->data<<"\t";
        preorder(p->left);
        preorder(p->right);
    }
}


void AVLTree::print()
{
    inorder(root);
}


void AVLTree::inorder()
{
    inorder(root);
}


void AVLTree::inorder(Node* p)
{
    if (p!=NULL)
    {
        inorder(p->left);
        cout<<p->data<<"\t";
        inorder(p->right);
    }
}


void AVLTree::postorder()
{
    postorder(root);
}


void AVLTree::postorder(Node* p)
{
    if (p!=NULL)
    {
        postorder(p->left);
        postorder(p->right);
        cout<<p->data<<"\t";
    }
}


int AVLTree::max(int value1, int value2)
{
    return ((value1 > value2) ? value1 : value2);
}


int AVLTree::bsheight()
{
    bsheight(root);
}


int AVLTree::bsheight(Node* p)
{
    int t;
    if (p == NULL)
    {
        return -1;
    }
    else
    {
        t = p->height;
        return t;
    }
}


Node* AVLTree:: srl(Node*& p1)
{
    Node* p2;
    p2 = p1->left;
    p1->left = p2->right;
    p2->right = p1;
    p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
    p2->height = max(bsheight(p2->left),p1->height) + 1;
    return p2;
}


Node* AVLTree:: srr(Node*& p1)
{
    Node* p2;
    p2 = p1->right;
    p1->right = p2->left;
    p2->left = p1;
    p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
    p2->height = max(p1->height,bsheight(p2->right)) + 1;
    return p2;
}


Node* AVLTree:: drl(Node*& p1)
{
    p1->left=srr(p1->left);
    return srl(p1);
}


Node* AVLTree::drr(Node*& p1)
{
    p1->right = srl(p1->right);
    return srr(p1);
}

[iMalc]

Welcome to the forum. It looks like there is a lot we can help you with there.

First off, I like to do a bit of a code review, so here are my observations:

Best practice is to use constructor initialisation lists, which you are currently not doing. Have a search on the web as to what that is. You can also combine constructors using a default parameter. Basically your only constructor could look like this:

Node::Node(int input = 0) :
    data(input), left(NULL), right(NULL), height(0) {}

Your destructor performs unnecessary NULL checks. 'delete' already checks for NULL pointers and as such it is always safe to just do: delete left; delete right;

AVLTree: Use a constructor initialisation list again. Your destructor is good though.

balanceup and balance: Comparing my own AVL tree implementation to yours, I can tell you straight away that these funtions are too complicated. There are definitely not this many cases that need to be considered. Once you've noticed that the heights differ by two, then you must perform a rotate. Right now you have several if-statements which when true perform a rotate, but what should happen if none of those were true? If that's not possible, then the last one can just be an else. See if you can find other ways of simplifying it.

insert: In this bit of code:

            if (p->left == NULL)
                p->left = new Node(x);
            else
                insert(x,p->left);

The only line you need is the last line. Just let the recursive call do its work and create the node for you.

getMax: I set it as a small challenge for you to write this one non-recursively using a loop instead.

preorder, inorder, print, postorder, bsheight: Best practice is to mark member functions which read but do not modify any member variables as const. You do this by putting const at the end of the function signature. E.g.

void AVLTree::postorder() const

If you continue to program in C++ then you will sooner of later come across a case where it is not only best-practice, but where it wont actually work without doing it.

inorder: It doesn't look like you use the zero-parameter version of this function. I suggest you remove it.

max: Any reason not to use std::max? I hope you marked this function as static.

Okay start with that stuff and see where that gets you. My final advice for now would be to isolate exactly what case it doesn't work in. I.e. what exact sequence of actions causes the bug.
You would also benefit from a tree-verify routine. That's a function you can call at any time which tells you for certain that the tree is well structured, correctly ordered and correctly-balanced. Call that before and after each insert or remove etc to help narrow down the problem.