24 November 2004, 16:33 UTCA final word on AVL trees
One thing bothered me about the AVl code I developed in the preceeding two articles. That is that there were two versions of each of avl_rotate_2 and avl_rotate_3, one for each of insert and delete. I don't like code duplication and the two versions were very similar despite not being identical. This just wouldn't do.
The differences between the rotation routines were two fold. Firstly the rotation went in opposite directions, and secondly the final setting of ->longer was quite different.
The first is easily fixed by passing 1-dir in place of dir for one of the call. There other took a little bit more work, but was achievable by moving some of the setting of ->longer out of the rotate function and into the call site.
The result is a smaller set of code with no significant code duplication. I made a few other minor changes and rearrangements and the result is available, free of charge or any other restrictions, as avl3.c
24 November 2004, 14:18 UTCNon-recursive algorithm for AVL tree deletion
I suggested in my other article on AVL insertion that deletion would probably be fairly symetric to insertion. It isn't, though there are similarities.
Deletion is somewhat more complicated than insertion, but not greatly so. Like insertion, it can be done neatly without recursion and using constant storage (no stack necessary). The cost of constant storage is that some comparisons need to be done twice (though on average, it is less than one per deletion).
These extra comparisons can be avoided by using one bit of storage for each level of the tree, which is less than twice the base-2 logarithm of the number of elements in the tree. If the tree is stored in memory, then the storage equivalent of two pointers will provide enough bits. This is small enough to be considered constant.
I have found other descriptions of non-recursive AVL deletion elsewhere on the web, specifically at http://benpfaff.org/avl/algorithm.ps and http://www.stanford.edu/~blp/avl/libavl.html/Deleting-from-an-AVL-Tree.html.
I don't find either of these treatments particularly easy to read, but that might be my problem, not their's. If you don't like what I have written, please try one of those.
Enough introduction - on to the code.
24 November 2004, 10:18 UTCNon-recursive algorithm for AVL tree insertion
I recently wanted to write code for insertion into an AVL tree. Because this
code will eventually (hopefully) live inside the Linux kernel, I wanted it to
be non-recursive (as recursive code doesn't sit will in the context of the kernel).
I found that taking a non-recursive approach leads to code that is (arguably) cleaner and more transparent than the traditional recursive approach. In fact, I liked what I came up with so much that I thought I would share it.