Monday, December 8, 2014

AVL Tree in C

I ported FreeBSD avl implementation into Linux users pace version.
Code is here(github link).

Practically speaking, we don't need AVL tree these days in high level languages like Python.  There are good alternatives in general.  In algorithm perspective, there is a Red Black Tree, the rival of AVL tree.  They mostly serve for the similar purpose.  RBTree is easier to implement, but size is factor of 2 vs. AVL is 1.4.  Linux uses RBTree internally, and FreeBSD had AVL.  (Linux RBTree article)

Well, in day to day life, modern languages provide their own version of "List".  In Python case, we just stuff data into the list, and later call it by index.  For efficient search, we use bisect module.  If we need sort, Python list takes very "Intelligent" approach to be efficient.  I will discuss this later, but listsort.txt in Python source can be referenced.

But, then, why bother AVL tree?
First, it's mentioned more in different algorithm books probably thanks to BST (Binary Search Tree).  And, AVL is a good subject to introduce concepts of algorithm, "let's cover the weakness of a given algorithm."  Second, it's personal.  I just like it with no reason.

When I searched AVL written in C, I found many pages.  First, GNU libavl is an overkill.  Other small projects are not mature enough.  Either it's "not generic", or data allocation logic is "malloc".  This will cost performance.  Modern days, C is chosen by performance in many cases.  So, too many or individual malloc is a bigger penalty.

Interestingly, FreeBSD has avl implementation and they still include it even today.  Probably, former SunOS used avl for kernel data.  This is small.  This only implements AVL algorithm, but comparator is a function pointer which I can attach.  AVL node does not bother the data, but my data suppose to embed avl_node_t.  And, AVL algorithm doesn't do high-level search.  So, I have to provide the high level search, like searchByName(const char *key).  I liked the design  because it is more flexible.  Unfortunately, it's not directly usable in Linux.  So, I tweaked and made it usable in Linux.  There are two files (avl.h and avl.c).  Enjoy.

No comments: