I started this series of articles on a journey looking to accomplish the task using a binary search tree to speed the lookup of function handlers using a string as the key. My initial implementation worked it was not optimal because the search tree was not balanced. However my method would still have worked if the tree was balanced. Let’s look one of the simplest self-balancing binary search tree: the AVL tree.
While I could go into the inner workings of an AVL tree there better resources for this. I got a fairly basic AVL tree working without too much issues. However, like most implementations the tree insertions work using recursion. For some applications recursive functions are forbidden. This is because they use stack space for each call and determining total stack usage may not be possible at compile time. Thus you cannot prove the stack will not overflow. An easy solution is to simply disallow recursive functions.
Our implementation only implements insertion and search functions, and the only place where recursion is needed is the insertion. This is because we need to re-balance each parent node after inserting the new node, and recursion solves the problem of keeping track of the path to the new node. Let’s examine the reference implementation (originally found here) of the insertion.
The rebalance task can be accomplish without recursion using a stack. Let’s start with the populating the stack during the search for the insert location. This is a fairly textbook example of traversing a binary tree.
Note that the parameter for the base of the tree is now a double-pointer. Why will become apparent latter. The goal is simply to traverse the tree until a insert location is found. At this point, the node will be NULL meaning the end of the tree branch has been reached. This is the location the new record should be placed. The double pointer means that we have the address of the pointer to this location, and thus that address can be changed. So at the end of the loop *nodePointer will be NULL, but nodePointer is either the the left or right that points to NULL. Simply setting *nodePointer will insert the new node at this location.
So at this point, we have the new node inserted in a iterative rather than recursive manner. However, the tree may not be balanced. For that we need to add in the stack so we can traverse back up the tree after the insertion has been made.
Here we add a stack. There isn’t much change except that each step through the tree the node is saved. This provides the path taken from the trunk of the tree to the newly inserted branch. In the recursive version this happens because each recursive step remembers the starting node and simply unrolls as the recursive functions exit. Now for rebalancing the tree.
Note that the first thing we do in the loop is pop an element off the stack. The node pointer starts at the node just inserted, but we know since it is the last node in the list that this node is balanced so it can be skipped.
We measure the balance of the node and rotate if needed, just as in the recursive version. However, we must modify the parent node with the rotated value. Since our list is a point to a node pointer, this is easy, but this is the key step in switching from a recursive to an iterative implementation.
The size of the stack is the maximum depth for any node—the maximum search depth. Balanced binary search trees all have a maximum depth of ⌈ log2 n ⌉ where n is the number total number of elements in the tree. If we are constructing a constant lookup table, this size is easy to calculate at compile time.
Here we have a macro that does the ceiling of the log base 2 for numbers up to 32-bits. It is a brute-force method of calculating a value but one that can be done at compile time. This macro will handle up to 65535 records. The should be more than sufficient for a command lookup table, but the pattern should be fairly obvious and could easily be expanded to 32 or even 64 bits.
Using the macro to define the stack size is simple.
Here the node storage is define as well as the stack needed for insertion.
The downside of using a stack is that if we are also using static allocation this is wasted memory after the tree has been created. Since lookup tables are generally created when the system starts one could recycle other memory. For a communications stack the send/receive buffers can be used because before the lookup table is initialized these buffers are not yet in use. This is one option for a small micro controller.
Overall there are not a lot of benefits to using an AVL tree for a static lookup table. The lookup speed is comparable to a binary search. As outlined already using an iterative heapsort or using a compile-time sorting is a better alternative. However the implementation of a non-recursive AVL tree might have other uses and worth sharing.