need help with my avl tree implementation

[FlashBurn]

I´ve written an avl tree implementation, but there seems to be at least one error in my code and I can´t find it I hope the code for my insert, delete and rotations functions is enough, because I think there is the problem, with the height calculation.

Code: Select all

struct avlNode_t *avlInsert(struct avlNode_t *startNode, struct avlNode_t *newNode, int (*comperator)(struct avlNode_t*, struct avlNode_t*)) {
	if(unlikely(startNode == 0)) {
		newNode->left= 0;
		newNode->right= 0;
		newNode->height= 0;
		
		return newNode;
	}
	
	if(comperator(startNode,newNode) >= 0) {
		startNode->left= avlInsert(startNode->left,newNode,comperator);
		
		if(unlikely((startNode->left->height - startNode->right->height) > 1)) {
			if(startNode->left->right != 0) {
				startNode= avlRotateLeftRight(startNode);
			} else {
				startNode= avlRotateRight(startNode);
			}
		}
	} else {
		startNode->right= avlInsert(startNode->right,newNode,comperator);
		
		if(unlikely((startNode->right->height - startNode->left->height) > 1)) {
			if(startNode->right->left != 0) {
				startNode= avlRotateRightLeft(startNode);
			} else {
				startNode= avlRotateLeft(startNode);
			}
		}
	}
	
	if(startNode->left == 0)
		startNode->height= 1 + startNode->right->height;
	else if(startNode->right == 0)
		startNode->height= 1 + startNode->left->height;
	else
		startNode->height= 1 + MAX(startNode->left->height,startNode->right->height);
	
	return startNode;
}

struct avlNode_t *avlDelete(struct avlNode_t *node, struct avlNode_t *del, int (*comperator)(struct avlNode_t*, struct avlNode_t*)) {
	struct avlNode_t *new;
	
	if(unlikely(node == 0))
		return 0;
	
	if(unlikely(node == del)) {
		//found the node
		if(node->left == 0) {
			if(node->right == 0) {
				//we have no children
				return 0;
			} else {
				//we have one child
				return node->right;
			}
		} else if(node->right == 0) {
			//we have one child
			return node->left;
		} else {
			//we have two children
			if(node->left->height > node->right->height) {
				//get the max node
				new= avlMax(node->left);
				new->left= avlDelete(node->left,new,comperator);
				new->right= node->right;
			} else {
				//get the min node
				new= avlMin(node->right);
				new->left= node->left;
				new->right= avlDelete(node->right,new,comperator);
			}
			node= new;
		}
	} else if(comperator(node,del) > 0) {
		node->left= avlDelete(node->left,del,comperator);
		
		if(unlikely((node->left->height - node->right->height) > 1)) {
			if(node->left->right != 0) {
				node= avlRotateLeftRight(node);
			} else {
				node= avlRotateRight(node);
			}
		}
	} else {
		node->right= avlDelete(node->right,del,comperator);
		
		if(unlikely((node->right->height - node->left->height) > 1)) {
			if(node->right->left != 0) {
				node= avlRotateRightLeft(node);
			} else {
				node= avlRotateLeft(node);
			}
		}
	}
	
	if(node->left == 0)
		if(node->right == 0)
			node->height= 0;
		else
			node->height= 1 + node->right->height;
	else if(node->right == 0)
		node->height= 1 + node->left->height;
	else
		node->height= 1 + MAX(node->left->height,node->right->height);
	
	return node;
}

struct avlNode_t *avlRotateLeft(struct avlNode_t *node) {
	struct avlNode_t *newNode= node->right;
	
	node->right= newNode->left;
	
	if(node->left == 0)
		if(node->right == 0)
			node->height= 0;
		else
			node->height= 1 + node->right->height;
	else if(node->right == 0)
		node->height= 1 + node->left->height;
	else
		node->height= 1 + MAX(node->left->height,node->right->height);
	
	newNode->left= node;
	
	return newNode;
}

struct avlNode_t *avlRotateLeftRight(struct avlNode_t *node) {
	node->left= avlRotateLeft(node->left);
	
	return avlRotateRight(node);
}

struct avlNode_t *avlRotateRight(struct avlNode_t *node) {
	struct avlNode_t *newNode= node->left;
	
	node->left= newNode->right;
	
	if(node->left == 0)
		if(node->right == 0)
			node->height= 0;
		else
			node->height= 1 + node->right->height;
	else if(node->right == 0)
		node->height= 1 + node->left->height;
	else
		node->height= 1 + MAX(node->left->height,node->right->height);
	
	newNode->right= node;
	
	return newNode;
}

struct avlNode_t *avlRotateRightLeft(struct avlNode_t *node) {
	node->right= avlRotateRight(node->right);
	
	return avlRotateLeft(node);
}

[FlashBurn]

Ok, I´ve written a function for calculating the height of a node (instead of the way I was doing it) and now it seems to work. Is there a way to implement an avl tree w/o using a function to calc the height, but save the height in every node and calc it only when it is need (w/o calling a function which uses recursion)? The point is that I want to get rid of the recursive function which calcs the height of every node.

[Combuster]

The height property is recursive one, so anything that deals with height has to be recursive of itself.

That said, the height changes only with modifications of the tree itself: insertion and deletion, possibly with reordering. Both these operations are already recursive, and since the height can only be modified in the subtree affected by either operation, height updates can be easily contained in both operations.

So if you add a node, you know the height of that node is zero. Your function will have seen all nodes on the way down. So when your function returns, you can check if the height of the node above it is still valid, or that it has increased by the addition, and update it if necessary. The algorithmic cost is none, since you do not have to process any more nodes than you would have otherwise.

[FlashBurn]

I rewrote my algo to use a balance value instead of a height value, because so it was easier to compare my algo to some others.

In these other algos there is a condition and if it is true the algo can end. But this is only true for the insert function (every time you set a balance to "0" you can end). I think that in the delete function you can end if you went left and set the balance to "1" or if you went right and set the balance to "-1". Is this right or is there no abort condition?

Will there be a big difference (in speed) if I use an iterative algo instead of a recursive algo?

[FlashBurn]

So I´m back

I´ve written a new version of my avl code and it seems there is something wrong with it, I insert many nodes, but when I then walk the tree I only have a small number of the nodes, which should be there, in the tree.

So here is the code, it is a recursive algorithm with iterative programming:

Code: Select all

#define AVL_MAX_LEVEL 28

struct avlDebugNode_t {
	struct avlDebugNode_t *left;
	struct avlDebugNode_t *right;
	int balance;
	uint32t val;
	char *name;
};

struct avlDebugNode_t *avlInsert(struct avlDebugNode_t *startNode, struct avlDebugNode_t *newNode) {
	struct avlDebugNode_t *node= startNode, *levelNode[AVL_MAX_LEVEL];
	int level= 0, res;
	uint8t levelDirection[AVL_MAX_LEVEL];
	
	newNode->left= 0;
	newNode->right= 0;
	newNode->balance= 0;
	
	if(likely(node)) {
		while(1) {
			levelNode[level]= node;
			res= (int)(node->val - newNode->val);
			
			if(likely(res)) {
				if(res > 0) {
					levelDirection[level]= 1;
					
					if(likely(node->left)) {
						node= node->left;
					} else {
						node->left= newNode;
						
						break;
					}
				} else {
					levelDirection[level]= 0;
					
					if(likely(node->right)) {
						node= node->right;
					} else {
						node->right= newNode;
						
						break;
					}
				}
			} else {
				newNode->left= (struct avlDebugNode_t *)1;
				newNode->right= (struct avlDebugNode_t *)1;
				
				return startNode;
			}
			
			level++;
		}
		
		while(likely(level >= 0)) {
			node= levelNode[level];
			
			if(levelDirection[level]) {
				if(node->balance == -1) {
					if(node->left->balance == 1)
						node= avlRotateLeftRight(node);
					else
						node= avlRotateRight(node);
				} else {
					node->balance--;
					
					if(!node->balance)
						return startNode;
				}
			} else {
				if(node->balance == 1) {
					if(node->right->balance == -1)
						node= avlRotateRightLeft(node);
					else
						node= avlRotateLeft(node);
				} else {
					node->balance++;
					
					if(!node->balance)
						return startNode;
				}
			}
			
			level--;
		}
		
		return node;
	} else {
		return newNode;
	}
}

struct avlDebugNode_t *avlRotateLeft(struct avlDebugNode_t *node) {
	struct avlDebugNode_t *newNode= node->right;
	
	node->right= newNode->left;
	newNode->left= node;
	
	node->balance--;
	newNode->balance--;
	
	return newNode;
}

struct avlDebugNode_t *avlRotateLeftRight(struct avlDebugNode_t *node) {
	node->left= avlRotateLeft(node->left);
	
	return avlRotateRight(node);
}

struct avlDebugNode_t *avlRotateRight(struct avlDebugNode_t *node) {
	struct avlDebugNode_t *newNode= node->left;
	
	node->left= newNode->right;
	newNode->right= node;
	
	node->balance++;
	newNode->balance++;
	
	return newNode;
}

struct avlDebugNode_t *avlRotateRightLeft(struct avlDebugNode_t *node) {
	node->right= avlRotateRight(node->right);
	
	return avlRotateLeft(node);
}

[Combuster]

How about walking the tree twice after each update, and printf-ing the result? It usually helps in pinpointing the problem.

[FlashBurn]

Yeah, I already did this and know that it happens that the node number decreases and I think it maybe could be my rotation code, but this should be working. If I could use the keyboard so that I need to press a key to go into the next loop, but as I use this code in my loader where I can´t use the bios it is not so easy to debug the code.

I also tried to debug the code on paper And there my rotation code worked

So maybe a hint?

[Combuster]

So maybe a hint?

To be honest, too long, no time to debug every opcode, so no detailed hints.

The covert suggestion was to get and post details, like the tree structure before an insertion, the arguments of the insertion, the expected tree after the insertion, and the returned tree after the insertion. Given that you already did the printf debugging, it should be copy-paste from your console .

[Kevin]

If I could use the keyboard so that I need to press a key to go into the next loop, but as I use this code in my loader where I can´t use the bios it is not so easy to debug the code.

OS independent things like this are usually easiest to develop outside of your OS if the features of your OS restrict your testing. Write a small test program, compile it for Linux (or $YOUR_FAVOURITE_OS) and run it there. Only when it works on Linux put it into your OS.

[FlashBurn]

Ok, I found the problem. It came to me as I were just about to fall to sleep

The problem is that I do the rotations right, but forgot to update the parent with the new successor. Here is the code

Code: Select all

struct avlDebugNode_t *avlInsert(struct avlDebugNode_t *startNode, struct avlDebugNode_t *newNode) {
	struct avlDebugNode_t *node= startNode, *levelNode[AVL_MAX_LEVEL], *new= newNode;
	int level= 0, res;
	uint8t levelDirection[AVL_MAX_LEVEL];
	
	newNode->left= 0;
	newNode->right= 0;
	newNode->balance= 0;
	
	if(likely(node)) {
		while(1) {
			levelNode[level]= node;
			res= (int)(node->val - newNode->val);
			
			if(likely(res)) {
				if(res > 0) {
					levelDirection[level]= 1;
					
					if(likely(node->left))
						node= node->left;
					else
						break;
				} else {
					levelDirection[level]= 0;
					
					if(likely(node->right))
						node= node->right;
					else
						break;
				}
			} else {
				newNode->left= (struct avlDebugNode_t *)1;
				newNode->right= (struct avlDebugNode_t *)1;
				
				return startNode;
			}
			
			level++;
		}
		
		while(likely(level >= 0)) {
			node= levelNode[level];
			
			if(levelDirection[level]) {
				node->left= new;
				
				if(node->balance == -1) {
					if(node->left->balance == 1)
						node= avlRotateLeftRight(node);
					else
						node= avlRotateRight(node);
				} else {
					node->balance--;
					
					if(!node->balance)
						return startNode;
				}
			} else {
				node->right= new;
				
				if(node->balance == 1) {
					if(node->right->balance == -1)
						node= avlRotateRightLeft(node);
					else
						node= avlRotateLeft(node);
				} else {
					node->balance++;
					
					if(!node->balance)
						return startNode;
				}
			}
			
			new= node;
			level--;
		}
		
		return node;
	} else {
		return newNode;
	}
}

[js]

Performance hint :

Storing the balance or the height takes 4 bytes for each node. If you have a large number of nodes, you shouldn't neglect this.

If you're constantly inserting / deleting nodes, then it still can be a good compromise (but you should still check if the cost of computing the height on-the-fly wouldn't just be incrementing a counter).

But if insertion and deletions are done only at a specific moment, then you should consider either storing your balance or height information in a separate chunk of memory that you can free once you're finished with it, or you could copy the whole tree to a balance/height-pruned one.

Just for curiosity, what are you using that AVL tree for ?

My two cents.

[FlashBurn]

Yeah I know this with storing the balance. I choose this one because it is a good compromise between memory overhead and speed. For performance it isn´t a good idea to calculate the height/balance of every node whenever you need it, but I found one thing where I maybe will do it (it´s a tree which is only created once and then it is only used for lookup).

It´s used e.g. for a symbol lookup (the address) for debugging. And I use it everywhere in my kernel. I wrote an interface with some ideas I got from java and so everyone who wants to use it in my kernel can use it and needed to provide his own code.

[js]

It´s used e.g. for a symbol lookup (the address) for debugging.

Mmmh... I think you could get away with a simple sorting and lookup using dichotomy. You could either sort the symbols themselves if you have a symbol table with fixed-size entries (and it won't wreck anything to move them arround), or you could sort a table of pointers towards those symbols.

For a similar issue, I personnaly used in-place heap sorting (complexity : O(n log(n)), you can't get better). It has the main advantage that you don't need any dynamic allocation (which is problematic in early stages).

And, using the in-place variant, you don't need any extra memory to store the result if you sort the symbol table itself (otherwise it's only one extra pointer per entry if you sort a table of pointers to symbols), whereas to store a tree like this you might need to keep the left-child right-child pointers (actually you could skip them when compacting the result if storing only full rows one after the other).

http://en.wikipedia.org/wiki/Heap_sort

I can send you my in-place heap sort code if you want (function takes an array, array size, getter function, element exchange function, comparison function). The three functions are one-liners.

But I guess since you already wrote an avl-tree algorithm you won't want to change it .

[FlashBurn]

As its only for debugging I don´t know if I keep it forever, at the moment it´s useful when I get an exception that I know in which function my kernel crashed and which function did call that function. I maybe rewrite this special case avl tree implementation so that I don´t have to save the balance value.