AVL tree deletion

[andreeaflorea]

So I am new when it comes to tree data structures and I am supposed to implement an AVL tree. My problem is the way the deletion of a node works. I have this code and I am not sure why the rebalancing of the tree after the deletion of a certain node does not work well. I don't guess it could have anything to do with the way I insert the data? (The insertion alone works) I am really lost here.

In the main program, I use the avlRebalance function after inserting a data.
Also, in case of deletion, I only use avlRebalance once, after the deletion of the data (so the deletion is the ordinary one I have already done for BST) to rebalance the entire tree: avlRebalance(tree).

Can anybody please take a look and see whether you see anything that should be different?

struct node 
{
	int info, h;
	node *st, *dr, *par;
};

typedef struct node *nodeptr;

nodeptr search(nodeptr rad, int x)
{
	while (rad)
		if (rad->info == x)
			return rad;
		else
		if (x < rad->info)
			rad = rad->st;
		else
			rad = rad->dr;
	return NULL;
}

int bsheight(nodeptr nod)
{
	if (nod == NULL)
		return 0;
	return nod->h;
}

int avlH(nodeptr &nod) 
{
	if (!nod) 
		return 0;
	int sth, drh;
	sth = bsheight(nod->st);
	drh = bsheight(nod->dr);
	nod->h = max(sth, drh) + 1;
	return nod->h;
}

int avlHDif(nodeptr nod) 
{
	if (!nod) 
		return 0;
	int sth, drh;
	sth = bsheight(nod->st);
	drh = bsheight(nod->dr);
	return drh - sth;
}

void rotLeft(nodeptr &p)
{
	 nodeptr aux, aux2, q;
	 int ok;
	 aux = p->st;
	 aux2 = p->dr;
	 p->st = aux2;
	 q = aux2->dr;
	 aux2->dr = aux2->st;
	 aux2->st = aux;
	 p->dr = q;
	 ok = p->info;
	 p->info = aux2->info;
	 aux2->info = ok;
	 if (q) 
		 q->par = p;
	 if (aux) 
		 aux->par = aux2;
}

void rotRight(nodeptr &p)
{
	 nodeptr aux, aux2, q;
	 int ok;
	 aux = p->dr;
	 aux2 = p->st;
	 q = aux2->st;
	 p->dr = aux2;
	 p->st = q;
	 aux2->st = aux2->dr;
	 aux2->dr = aux;
	 ok = p->info;
	 p->info = aux2->info;
	 aux2->info = ok;
	 if (aux) 
		aux->par = aux2;
	 if (q) 
		q->par = p;    
}

void avlRebalance(nodeptr &balans) 
{
	if (!balans) 
		return;
	avlRebalance(balans->dr);
	avlRebalance(balans->st);
	avlH(balans);
	if (abs(avlHDif(balans)) < 2)
		return;
	if (avlHDif(balans) > 0)
		rotLeft(balans);
	else
		rotRight(balans);
}

void avlInsert(nodeptr &rad, int val)
{
	 nodeptr x, y, nod;
	 nod = (nodeptr)malloc(sizeof(node));
	 nod->info = val;
	 nod->st = NULL;
	 nod->dr = NULL;
	 nod->par = NULL;
	 nod->h = -1;
	 y = NULL;
	 x = rad;
	 while(x != NULL)
	 {
		y = x;
		if (nod->info < x->info)
		    x = x->st;
		else 
			x = x->dr;
	  }
	  if (y == NULL) 
		  rad = nod;
	  else
		  if (nod->info < y->info)
		  {
			  y->st = nod; 
			  nod->par = y;
		  }
		  else
		  {
			  y->dr = nod; 
			  nod->par = y;
		  }
}

nodeptr succesorNod(nodeptr rad) 
{
	nodeptr aux = rad;
	while (aux->st) 
		aux = aux->st;
	return aux;
}


void deletemin(nodeptr &p, nodeptr rad)
{
	nodeptr q;
	int aux;
    q = p->dr;
	while (q->st != NULL) 
		q = q->st;
	aux = q->info;
	q->info = p->info;
	p->info = aux;
	if (q->par->st == q) 
	{
		if (q->dr) 
		{
			q->par->st = q->dr; 
			q->dr->par = q->par;
		}
		else 
			q->par->st = NULL;
	}
	else 
	{
		q->par->dr = q->dr; 
		if (q->dr) 
			q->dr->par = q->par;
	}
	
}


void avlDelete(nodeptr &rad, int v)
{
	nodeptr p; 
	int aux;
	p = rad;
	while (p->info != v)
	{
		if (v < p->info) 
			p = p->st;
		else 
			p = p->dr;
    }
	if (p == rad && p->dr == NULL && p->st == NULL)
		 rad = NULL;

	else 
		if (p == rad && p->st != NULL && p->dr==NULL) 
		{
			rad = p->st; 
			p->st->par = NULL;
		}
		else 
			if (p == rad && p->dr != NULL && p->st == NULL) 
			{
				rad = p->dr; 
				p->dr->par = NULL;
			}
			else 
				if (p->st != NULL && p->dr == NULL)
					if (p->par->st == p) 
					{
						p->par->st = p->st; 
						p->st->par = p->par;						
					}
					else
					{
						p->par->dr = p->st; 
						p->st->par = p->par;
					}
							    
				else 
					if (p->st == NULL && p->dr != NULL)
						if (p->par->st == p)
						{
							p->par->st = p->dr; 
							p->dr->par = p->par;              
						}
						else
						{
							p->par->dr = p->dr; 
							p->dr->par = p->par;
						}
                    					 
					else 
						if (p->st == NULL && p->dr == NULL) 
							if (p->par->st == p)
								p->par->st = p->st; 
							else
								p->par->dr = p->dr;      
						else 
							deletemin(p, rad);
}

My main is something like this:

switch (opt)
		{
			case 1:
				cout << "Value: ";
				cin >> x;
				avlInsert(rad, x);
				avlRebalance(rad);
				cout << endl;
				break;
		
			case 2:
				cout << "Delete value: ";
				cin >> x;
				aux = search(rad, x);
				if (aux)
				{
					avlDelete(rad, x);
					avlRebalance(rad);
				}
				else
					cout << "The data is not found";
				break;