OSDev.org

Hey people,
yes, I know, Im always posting about AVL.
Or something.

In any case, It is a component of something I will release soon called Kanet.

It is completely portable, ANSI C89 compliant.
It does not rely on the standard C library.
It can be used in a hosted or freestanding environment...

It provides a base structure for the AVL structure. You can base your structures upon it.
All functions within the implementation will function perfectly on your structures, under the condition that the avl_hdr_t base structure is the FIRST member.

It is fully commented.
It is for the most part, optimized.

The makefile provided is specific to UNIX environments.
Under Windows, You will be able to build the test program easily with MSYS or CYGWIN. If you wish to the run the tests, You can use DevC++ or something similar. Ensure you define _test_avl with some number, as it will decide how many nodes to insert in the test.

This implementation is part of the Zenobit Core Library and as such, is licensed under the CC-by ND 3.0 license (http://creativecommons.org/licenses/by-nd/3.0/).

Feedback, bugs, interesting results, Let me know.
~Z

zeii wrote:Hey people,
yes, I know, Im always posting about AVL.
Or something.

So. What is AVL anyway?


JAL

An AVL tree is a type of binary search tree. It uses an algorithm to keep the tree balanced and prevents it from turning into a glorified linked list. C.f. red-black trees. See also the wiki page (clicky).

A height balanced binary search tree provides guaranteed O(log n) (base 2) in the average and worst cases, whereas a nonbalanced binary search tree provides O(log n) (base 2) for the average case and O(n) for the worst case.

JamesM wrote:An AVL tree is a type of binary search tree. It uses an algorithm to keep the tree balanced and prevents it from turning into a glorified linked list.

Thanks for the info, might come in handy some day.


JAL

Any feedback?

~Z