/* Delete the the node and the info within it */
void avlDeleteNode(AVLTree *tree, AVLNode *node)
{
	tree->destroyElem(node->elem);
	free(node);
}

/* Rebalance the tree after delete */
void avlDeleteFixUp(AVLTree* tree, AVLNode* y)
{
	while (y != tree->root) {
		/* Update the height and get the balance factor */
    	y->height = max(y->l->height, y->r->height) + 1;
    	int balance = avlGetBalance(y);

    	/* Rebalance the tree */
    	if (balance > 1) {
    		if (avlGetBalance(y->l) >= 0) {
    			/* Single right rotation */
    			avlRightRotate(tree, y);
    		} else {
    			/* Double right rotation */
    			avlLeftRotate(tree, y->l);
        		avlRightRotate(tree, y);
    		}
    	} else if (balance < -1) {
    		if (avlGetBalance(y->l) <= 0) {
    			/* Single left rotation */
    			avlLeftRotate(tree, y);
    		} else {
    			/* Double left rotation */
    			avlRightRotate(tree, y->r);
        		avlLeftRotate(tree, y);
    		}
    	}

		/* Move upward */
    	y = y->p;
	}
}

/* Delete a node from the tree or from the list */
void avlDelete(AVLTree* tree, Item1 elem)
{
	/* Get the node we need to delete */
	/* sNode = searchedNode */
	/* pNode = parentNode   */
	/* cNode = childNode    */
	AVLNode *sNode = avlExactQuery(tree, elem);
	AVLNode *pNode = sNode->p;
	AVLNode *cNode;
	tree->size--;

	/* Duplicate case: delete a node from the list */
	if (sNode != sNode->end) {
		/* Set up the new links betweekn the nodes */
		sNode->next = sNode->end->next;
		sNode->end->next->prev = sNode;

		/* Create a copy & move the end & destroy */
		AVLNode *toDelete = sNode->end;
		sNode->end = sNode->end->prev;
		avlDeleteNode(tree, toDelete);
		return;
	}

	/* Get the number of the childs of the node */
	int childsNumber = (sNode->l != tree->nil) + (sNode->r != tree->nil);

	/* Simple node case: delete from the tree & list */
	switch (childsNumber) {
		case 0:
			/* Leaf: Detatch the child */
			if (pNode->l == sNode)
				pNode->l = tree->nil;
			else
				pNode->r = tree->nil;
			break;
		case 1:
			/* Get the left or right child */
			cNode = (sNode->l != tree->nil) ? sNode->l : sNode->r;

			/* Set up the links */
			cNode->p = sNode->p;
			if (sNode->p->l == sNode)
				sNode->p->l = cNode;
			else
				sNode->p->r = cNode;
			break;
		case 2:
			/* Get the pivot */
			pNode = avlMinimum(tree, sNode->r);

			/* Move the childs */
			pNode->l = sNode->l;
			pNode->r = sNode->r;
			sNode->l->p = pNode;
			sNode->r->p = pNode;

			/* Set up the parents */
			pNode->p = sNode->p;
			if (sNode->p->l == sNode)
				sNode->p->l = pNode;
			else
				sNode->p->r = pNode;

			/* Remove self references */
			if (pNode->r == pNode)
				pNode->r = tree->nil;
			if (pNode->l == pNode)
				pNode->l = tree->nil;

			break;
	}

	/* Set up the links in the list */
	if (sNode->prev != tree->nil)
		sNode->prev->next = sNode->next;
	sNode->next->prev = sNode->prev;

	/* Delete & rebalance */
	avlDeleteNode(tree, sNode);
	avlDeleteFixUp(tree, pNode);
}