Z
Z
Z_phyr2020-12-06 13:47:33
C++ / C#
Z_phyr, 2020-12-06 13:47:33

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

1 answer(s)
A
Alexander Ananiev, 2020-12-06
@Z_phyr

It says that an undefined reference to main. Where is the main function?

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question