Answer the question
In order to leave comments, you need to log in
Balancing a binary tree, what's wrong?
This code throws an error:
/usr/lib/gcc/x86_64-linux-gnu/4.9/../../../x86_64-linux-gnu/crt1.o: In function `_start':
(.text+0x20 ): undefined reference to `main'
collect2: error: ld returned 1 exit status
How to fix it?
class Node
{
public:
int key;
char height;
Node *right;
Node *left;
Node(int k) { key=k; height=1; left=right=0; }
};
char height(Node *p)
{
if (p) return p->height;
else return 0;
}
int BF(Node *p)
{ return height(p->right)-height(p->left); }
void OverHeight(Node *p)
{
char hleft=height(p->left);
char hright=height(p->right);
p->height=(hleft>hright ? hleft : hright)+1;
}
Node* RightRotation(Node *x)
{
Node *y=x->left;
x->left=y->right;
y->right=x;
OverHeight(x);
OverHeight(y);
return y;
}
Node *LeftRotation(Node *y)
{
Node *x=y->right;
y->right=x->left;
x->left=y;
OverHeight(y);
OverHeight(x);
return x;
}
Node *Balance(Node *x)
{
OverHeight(x);
if (BF(x)==2)
{
if (BF(x->right)<0) x->right=RightRotation(x->right);
return LeftRotation(x);
}
if (BF(x)==-2)
{
if (BF(x->left)>0) x->left=LeftRotation(x->left);
return RightRotation(x);
}
return x;
}
Node *Insert(Node *x, int k)
{
if (!x) return new Node(k);
if (k<x->key) x->left=Insert(x->left, k);
else x->right=Insert(x->right, k);
return Balance(x);
}
Node *SearchMin(Node *x)
{
if (x->left) return SearchMin(x->left);
else return x;
}
Node *DeleteMin(Node *x)
{
if (x->left==0) return x->right;
x->left=DeleteMin(x->left);
return Balance(x);
}
Node *Delete(Node *x, int k)
{
if (!x) return 0;
if (k<x->key) x->left=Delete(x->left, k);
else if (k>x->key) x->right=Delete(x->right, k);
else
{
Node *y=x->left;
Node *z=x->right;
delete x;
if (!z) return y;
Node* min=SearchMin(z);
min->right=DeleteMin(z);
min->left=y;
return Balance(min);
}
return Balance(x);
}
Answer the question
In order to leave comments, you need to log in
It says that an undefined reference to main. Where is the main function?
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question