Recursion in kernel code is ok, as long as you don't recurse too far, so it really depends a lot on what you expect your maximum tree size to be.
Ofcourse searching a binary tree is easy to do without recursion (well this is the obvious tail-recursive implementation rewritten for explicit iteration):
Code: Select all
// compare should return -1, 0 or 1, depending on <, ==, >
tree * find(tree * root, void * value, int (*compare)(void *, void*)) {
tree * current = root;
while(1) switch(compare(value, current->value)) {
case -1: current = current->left; break;
case 0: return current;
case 1: current = current->right; break;
}
}
Doing inserts / deletes without rebalancing is similarly easy to do without recursion. If you can afford a back-link into parent, then it's pretty easy to walk upwards the tree, which allows rotations for rebalancing.
If you can't, then you can take advantage of the fact that if you know the previous node and the current node, then the pointer from the previous node to the current node is redundant, and you can use it to temporarily store the back-pointer upwards instead.
This will allow you to walk back up without any extra storage, although it will require locking the whole tree for the duration of the operation, because looking down from the root the tree won't make sense before you walk it back up and restore the pointers to how they should be.
....
As for information... mm.... Wikipedia has decent information on both AVLs and Red-Blacks (which I personally found easier to figure out, and which sometimes require a bit less rotations by being not quite so strict about balancing, but can lose in average lookup times for the same reason).
....
Anyway, I would suggest you first implement your tree-routines recursively, test that they actually work, and then convert them to interative versions one operation at a time.
The real problem with goto is not with the control transfer, but with environments. Properly tail-recursive closures get both right.
