OSDev.org

Posted: **Tue Mar 13, 2007 10:29 am**

Some quick questions here.

a) Is there a handy dandy equation to work out how many nodes, for a complete binary search tree of a given height?

b) and something to reverse that equation, given X nodes, what would be the height?

c) Any good references on AVL Trees would be appreciated. (My textbook is freaking horrible!)

d) Is it forgivable to use some recursive functions in Kernel code?

e) Any advice on how to make recursive calls as... friendly to the stack as possible would be appreciated, as Zenobit currently only has a 4KiB Stack and I dont particularly want to increase it drastically!

Much thanks!
~Zeii.

Posted: **Tue Mar 13, 2007 10:52 am**

a: nodes = (2 ^ height) - 1
b: use 2log (nodes+1) and round up, or a bit scan to find the highest set bit
c: wikipedia?
d: if you are SURE not to overflow the stack

e: assembly, register calling convention, tail recursion

Posted: **Tue Mar 13, 2007 3:09 pm**

Aye.
Still, Decent resources on AVL tree... is increasingly difficult to find.

Particularly, It is updating the balances correctly that is the major issue.

*sigh* I need a cigarette and a nice warm tummy full of coffee....

~Z

Posted: **Sat Mar 17, 2007 7:03 pm**

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.

Posted: **Sun Mar 18, 2007 7:22 am**

Hey guys, Thank you for the information.

I've been tinkering away for the past few days, constantly trying to get an AVL tree working in a variety of crazy ways.

And, I think I finally got it. The only part I have to do now is :

- Removal (Shouldn't be too hectic)
- Left-Right cases (Left right left, left right right)
- Right-Left cases (Right left right, right left left).
( Fixing the balances after rotation).

So far, It seems to work okay.
I would really appreciate it if someone would take a look at my current code.

It is my attempt at an Iterative AVL tree, completely in C.
If anyone is interested in checking / helping me understand AVL better, PM me and I will email my code.

If you aren't into looking at other people's code, No problem - Add me on MSN or ICQ

. Contact details are in my profile.

~Zeii

OSDev.org

Binary Tree + Insanity.

Binary Tree + Insanity.