Adding Nodes to an AVL Tree in C

[ashwyn]

I'm programming in C and I'm having some big problems in my program that leads me to believe that my functions for adding new elements to my AVL tree structure are not working properly.

I'm hoping that someone would be willing to give me a second opinion on my implementation for my add functions for these structures.

Here are some definitions I'm working with:

#define EQ(a, b) (a == b)
#define LT(a, b) (a < b)

struct AVLnode {
	TYPE         val;
	struct AVLnode *left;
	struct AVLnode *right;
	int height;
};

struct AVLTree {
	struct AVLnode *root;
	int          cnt;
};

Here are the two functions in question:

/* add newValue to subtree of current node */
struct AVLnode * AVLnodeAdd(struct	AVLnode * current, TYPE newValue)
{


	if(EQ(current,NULL)){ /* Stop Condition |  Allocate memory for newnode */
			struct AVLnode *newnode = (struct AVLnode *)malloc(sizeof(struct AVLnode));
			printf("\nadded node");
			newnode->val = newValue;
			newnode->right = NULL;
			newnode->left = NULL;
		return newnode;								/* Return newnode to occupy an empty leaf space */
	}
	else{
		if(LT(newValue, current->val))
			current->left = AVLnodeAdd(current->left, newValue);
		else
			current->right = AVLnodeAdd(current->right, newValue);
	}

	return _balance(current);
}

/* add val to AVL tree */
void addAVLTree(struct AVLTree *tree, TYPE val)
{

tree->root = AVLnodeAdd(tree->root, val);
tree->cnt++;

}

It seems to me like the problem must be coming from the addition of new nodes to the tree struct.


It is called in main, read from a file like so:

	/* Read input file and add numbers to the AVL tree */
	while((fscanf(file, "%i", &num)) != EOF){
		addAVLTree(tree, num);
	}

Side Note:
I feel as though the _balance() function called at the end of AVLnodeAdd is sound, and should be working. I will provide it's implementation here just in case though.

/* balance subtree of current node */
struct AVLnode * _balance(struct AVLnode * current)
{

	int	tbf = 0;
	int cbf = bf(current);

	if(cbf > 1){    /* Heavy on the Right, Rotate Left */

		tbf = bf(current->right);

		if(tbf < 0){	/* If child is heavy on the left, Rotate child Right first */
			rotateRight(current->right);
		}

		rotateLeft(current);
	}

	if(cbf < -1){		/* Heavy on the left, Rotate Right */

		tbf = bf(current->left);

		if(tbf > 0){		/* If child is heavy on the right, Rotate child left first*/
			rotateLeft(current->left);
		}

		rotateRight(current);
	}

	setHeight(current);
	return current;

}

Any and all help or advice is greatly appreciated

[Niccolo]

Since I can't compile a working example I can only read and notice what mere mortals might see.

I'm not sure what could be the problem yet, but I have this one piece of advice...get the tree working first, THEN implement the balance. Trees do work without balance. They degrade, yes, but when you COMBINE the two concepts you're asking for a debugging nightmare. Comment out the call for tree balancing, and just build the tree. Feed "random" data for evaluation at first, and debug that.

As an alternative, use a define or some other means to conditionally enable/disable balancing for development/debug purposes.

AT the moment I don't see what's wrong with the adding a new entry, except for what can happen if you enter duplicate values (they're supposed to be rejected, do you have that implemented?).

Another point that strikes me is the EQ and LT defines. Is there really any purpose here? I suggest you reconsider them. I don't expect they're giving bugs, but it took longer for me to recognize what that meant, where A == B is obvious, and I can't say I understand exactly why a macro makes sense here.

I understand the notion of a parametric comparator, where you could substitute comparison with a function pointer, but that would better work as a "comp" function for EQ and "LessThan" function for LT, which you could transform from a simple function call to call by pointer to function (or some other mechanism).

[ashwyn]

Thank you for the thoughtful advice.

When I omit the balance function, things do start to look a bit better. This tells me something is definitely going on somewhere in the balancing chain.

Some of this code I was given as a skeleton as an assignment from a course, and the EQ and LT functions are just a staple. Sometimes they make sense, like when making code universal to many data types. But yeah, here it is not necessary. I can confirm they are not a source of problem though.

Anyway, I'll have to go deeper into this. Thank you for your guidance here. :)

[ashwyn]

These are the function involved in _balance.

I feel like I'd be asking a lot to eyeball all this since you can't compile it yourself, as you mention.

I'm just feeling pretty nuts at this point after so much time looking at these functions.
I'm also not great at thinking recursively, so the debugging process gets mind-boggling after a short period.

/* return balance factor value */
int bf(struct AVLnode * current)
{
	return h(current->right) - h(current->left);
}



/* left-rotate subtree of current node */
struct AVLnode * rotateLeft(struct AVLnode * current)
{
	struct AVLnode * newtop = current->right;

 	current->right = newtop->left;

	newtop->left = current;				     	/* Assigns new right child to current root */

	setHeight(current);											/* Update heights- bottom-most first */
	setHeight(newtop);

	return newtop;
}

/* right-rotate subtree of current node */
struct AVLnode * rotateRight(struct AVLnode * current)
{
	struct AVLnode * newtop = current->left;

	current->left = newtop->right;

	newtop->right = current;

	setHeight(current);
	setHeight(newtop);

	return newtop;
}




/* set height for current node */
void setHeight (struct AVLnode * current)
{
	int lch = h(current->left);						/*Because these are absolute heights, the new height is with respect to the longest path below */
	int rch = h(current->right);					/* h() simply returns the height of the node */
	if (lch < rch)
		current->height = 1 + rch;
	else
		current->height = 1 + lch;
}

[Niccolo]

I'm also not great at thinking recursively, so the debugging process gets mind-boggling after a short period.

This isn't a unique viewpoint, most of us find recursive design challenging, and debugging it even worse. After 40 years it still boggles me a bit.

Likewise, this stuff soaks up hours. That, too, is common with this kind of subject material. I went through this same thing, about like you're doing (but in C++) in the 90's. It is why I suggested separating balance from tree creation, as it was key for me at that time.

The hour requires me to sleep, so I'll check into this late tomorrow. If not someone else, I'll try to come back and check/think/suggest what I can see, but at this point there just isn't enough coffee to make my 16th hour functional.

[lastchance]

@ashwyn,
In your procedure _balance(), what, if anything, are you doing with the return values of
rotateLeft() in
rotateLeft(current);
and similarly rotateRight().

Also, are you sure that you are actually changing current from what it entered the routine as?