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.
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);
}