AVL Tree Height Problem

[maikens]

Hi all,

I have written a balanced binary search tree as part of an assignment (make a simple Spell Checker). Each node has, among other values, two height ints, leftHeight and rightHeight, to keep track of the heights of any subtrees. My problem is that after a rotation, the heights of any parent nodes and their preceding parents can be incorrect. For example, consider the following tree:

B
 / \ 
A   C
     \
      D
       \
        E

According to my program, this tree is unbalanced because the difference between the leftHeight and rightHeight fields of node B is greater than 1 (1-3) . To fix this, a single left rotation is performed on node D, making the tree look like this:

B
 / \
A   D
   / \
  C   E

The way my program is written, the reassignment of the heights of nodes D, C, E, is done within the rotation function, and those are correct. However, node B's rightHeight field remains the same (3), and is now incorrect (should be 2). This problem occurs each time a rotation is done, and may cause the program to attempt to rotate a node that shouldn't be rotated (in turn causing an access violation).

I have thought of adding another field to each node, parent, to facilitate readjustment of the parent's heights, but my nodes already take up more memory than I'd like, so I need another solution.

I have attached my code for the program, including a set of Inserts that illustrates the problem resulting from the height value problem.

If anyone has the time, I'd appreciate any advice on how to solve this problem. Preferably, I'd like to avoid writing another recursive function, or adding any additional fields to the AVLNode class. The best solution in this case would be to write a non-recursive function to do the height adjustment, or to add code to an existing recursive method (to increase efficiency) - I'm just not certain how to do it.

Thanks!

[Greywolf333]

Hi all,

I have written a balanced binary search tree as part of an assignment (make a simple Spell Checker). Each node has, among other values, two height ints, leftHeight and rightHeight, to keep track of the heights of any subtrees. My problem is that after a rotation, the heights of any parent nodes and their preceding parents can be incorrect. For example, consider the following tree:

B
 / \ 
A   C
     \
      D
       \
        E

According to my program, this tree is unbalanced because the difference between the leftHeight and rightHeight fields of node B is greater than 1 (1-3) . To fix this, a single left rotation is performed on node D, making the tree look like this:

B
 / \
A   D
   / \
  C   E

The way my program is written, the reassignment of the heights of nodes D, C, E, is done within the rotation function, and those are correct. However, node B's rightHeight field remains the same (3), and is now incorrect (should be 2). This problem occurs each time a rotation is done, and may cause the program to attempt to rotate a node that shouldn't be rotated (in turn causing an access violation).

I have thought of adding another field to each node, parent, to facilitate readjustment of the parent's heights, but my nodes already take up more memory than I'd like, so I need another solution.

I have attached my code for the program, including a set of Inserts that illustrates the problem resulting from the height value problem.

If anyone has the time, I'd appreciate any advice on how to solve this problem. Preferably, I'd like to avoid writing another recursive function, or adding any additional fields to the AVLNode class. The best solution in this case would be to write a non-recursive function to do the height adjustment, or to add code to an existing recursive method (to increase efficiency) - I'm just not certain how to do it.

Thanks!

You uploaded your code as an archive, within an archive, with no extension. I had to use notepad to discover its filetype and realize it was another pkzip file. You may want to fix that so more people can help you. I'm looking at it now but it's 4:30 in the morning :)

[maikens]

Whoops. Thanks, I'll resubmit it.

[maikens]

Hmm...it won't let me edit it..30 minutes is up.

[Zjarek]

Don't update height during first phase of insertions. You have this tree:

B
|1   \2
A     C
       \1
        D
         \
          E

And you mark D node to update, it gets 2 and on C node there is imbalance. You left rotate it and update C height. This way B is balanced (there is still 2 in right, but on D node) and heights are good:

B
|1   \2
A     D
     |1 \1
     C   E

[maikens]

Actually, in my particular implementation, I have nodes with no children assigned a height of zero, and leaves are -1. Either way, node B is balanced, but its rightHeight is incorrect, because the rotation function doesn't know of that node, only D and C. My problem isn't the heights of D, C, and E, but of B.

[Zjarek]

B right height is the same before insertions and after balancing.

[Greywolf333]

Is this a common implementation? I'm having a little trouble understanding some of it.

During your insertions, you increase the leftheight and rightheight of the current node automatically if you move left or right recursively. But just moving left or right doesn't guarantee that you'll increase the height the parent tree: If you have some root node "D", and you insert "B", you correctly increment leftheight of "D". But what happens if you then insert "A" and then "C"? You would have:

D
  B
A   C

But would your code incorrectly increment D's leftheight to 3, for the 3 insertions, when it should be 2?

If your code works then I'm probably overlooking something.

As to your original question: If you really wanted to avoid a parent pointer (though how much memory does a pointer really use? All a pointer stores is the memory address)... you could simply keep track of the parent node in your balance function. i.e Balance(currPointer, parentPointer), and then adjust parentPointer's height in the Balance function itself.
-Greywolf

[Zjarek]

Greywolf is right, you have wrong height calculation while inserting. In AVL trees you should have parent pointer in nodes, it is really helpful. I think you should just use Wirth's, Wiki and some imagination to write it again from scratch.
@ Greywolf: pointer just stores address, type is known only to compiler.

[maikens]

Thanks for looking over my code, guys (or gals).

I am unlikely to start from scratch, mainly because the assignment only requires serial insertion, and won't break during that. But also because I feel a solution to my problem wouldn't require me to scrap the whole shebang...unless you feel my code is THAT crappy..heh.

I am unsure of how to handle the height-incrementing and decrementing if it's not performed inside the Insert function. I don't want to have to write a recursive function to traverse the tree and adjust the heights after each insertion - that would require way too much overhead

[Zjarek]

Rotation looks good, one problem is that you use NULL and not a dummy node and you don't have parent node. I experienced that in other uses for a tree this is a must (for example it's the easiest way for a working bidirectional iterator). Following is common way to implement AVL trees.
First of all, add parent pointer for every node. If you have them, don't modify height of the nodes during insertion. Instead just imagine inserted node as +1. Then go from this point up the tree keeping in mind this imbalance. For example if you have this +1 in left node, and right node is bigger add +1 to left node and stop further balancing. If right node and left node were in equilibrium add +1 to left node height and use this parent as new +1. And finally if left node was bigger do the rotation balancing and then your tree is balanced (you must of course modify heights during rotations).
In erasing you act accordingly (but you have -1 balance), main difference is that after rotation you still have this -1 mark, and you need balance tree further.

[Greywolf333]

Rotation looks good, one problem is that you use NULL and not a dummy node and you don't have parent node. I experienced that in other uses for a tree this is a must (for example it's the easiest way for a working bidirectional iterator). Following is common way to implement AVL trees.
First of all, add parent pointer for every node. If you have them, don't modify height of the nodes during insertion. Instead just imagine inserted node as +1. Then go from this point up the tree keeping in mind this imbalance. For example if you have this +1 in left node, and right node is bigger add +1 to left node and stop further balancing. If right node and left node were in equilibrium add +1 to left node height and use this parent as new +1. And finally if left node was bigger do the rotation balancing and then your tree is balanced (you must of course modify heights during rotations).
In erasing you act accordingly (but you have -1 balance), main difference is that after rotation you still have this -1 mark, and you need balance tree further.

If you don't want to modify your code so much, you could technically do it in the insertion function, post insertion, by using a while loop and parent nodes:

//If you insert left or right, check before you insert if the opposite node exists.  So if you insert node->left, and node->right does not exist, then you must adjust all heights since the entire side of that tree is now greater.  However if you were to insert->left, and node->right DOES exist, then only its parent has a new left height, and the rest of the tree remains the same since that level is already partially filled.

//If the insertion results in a greater height for the whole side...
while (node) { //will break when root->parent is found to be null.
  if (node->parent->left == node) node->parent->leftHeight += 1;
  else node->parent->rightHeight += 1;
  node = node->parent;
  }

-Greywolf

[maikens]

Excellent, thanks a lot both of you. I think I've been working on this for so long that my brain finally mutinied on me! I think I will use a parent node after all. I will try this and let you know how it worked out.

[maikens]

Greywolf, the problem with your code is that there could be an access violation if a node without a sibling is inserted

if(!hasSibling)
		{
			while(node != NULL) // iterate until root's parent is reached)
			{ 
				if(node->parent->left == node) // this will break
				{
					node->parent->rightHeight += 1;
				}
				else 
				{
					node->parent->leftHeight += 1;
				}

				node = node->parent;  
			}
		}

[Greywolf333]

Greywolf, the problem with your code is that there could be an access violation if a node without a sibling is inserted

if(!hasSibling)
		{
			while(node != NULL) // iterate until root's parent is reached)
			{ 
				if(node->parent->left == node) // this will break
				{
					node->parent->rightHeight += 1;
				}
				else 
				{
					node->parent->leftHeight += 1;
				}

				node = node->parent;  
			}
		}

Actually it would break... but not for the reason you think. You know node exists, and if you know parent exists (see below), it is safe to do node->parent->left. Sure node->parent->left might be null, but that doesn't mean it will cause an access violation since you're not doing anything with it. Parent exists, therefore the "left" pointer has been initialized as per your Node.h. It could still be NULL, but you can still use NULL in comparison. i.e. if (anything == NULL) do something;

The mistake I made is that it should be while (parent->node), not while (node). Sorry :)

[Greywolf333]

Actually it would break... but not for the reason you think. You know node exists, and if you know parent exists (see below), it is safe to do node->parent->left. Sure node->parent->left might be null, but that doesn't mean it will cause an access violation since you're not doing anything with it. Parent exists, therefore the "left" pointer has been initialized as per your Node.h. It could still be NULL, but you can still use NULL in comparison. i.e. if (anything == NULL) do something;

The mistake I made is that it should be while (parent->node), not while (node). Sorry :)

I mean node->parent not parent->node. -1 points. This is why I never got good grades in college hehe.

[maikens]

Ah ok. I couldn't get that to work anyways. However, I found that with a very minimal change in the code, I was able to fix it. Before, I was increasing the height before the recursive call:

else if(str < node->data)
{
	// Increase height of node and move to the node's left
            node->leftHeight++;
	   Insert(str, node->left);	
}

I modified the code so that the height increased after the insert, and it didn't increment the height, instead, it took its left node and added 1. Also, I call the Balance function after each recursion to ensure the heights are correct.

else if(str < node->data)
{
	// Increase height of node and move to the node's left
	Insert(str, node->left);
	node->leftHeight = GetHeight(node->left) + 1;
	Balance(root);
}

There was also an error in the double rotations - I fixed this (passed node->right or node->left, should have been node)

These fixed it, and the tree balances correctly. Also, the tree balances correctly after Removes.