Join GitHub today
GitHub is home to over 31 million developers working together to host and review code, manage projects, and build software together.Sign up
A C implementation of a self-balancing order statistic AVL tree
Fetching latest commit…
Cannot retrieve the latest commit at this time.
|Type||Name||Latest commit message||Commit time|
|Failed to load latest commit information.|
BOSTree -- An order statistic, self-balancing AVL tree implementation in C An order statistic tree is a tree structure with two additional methods, rank(node) and select(index), which allow array-like access in O(log n) time. The idea is to simply store, for each node, the number of child-nodes. Self-balancing search trees maintain a minimal height by rebalancing their sub-trees. I did not find a C reference implementation for such a tree, so I wrote one myself. This implementation uses map semantics, that is, stores key and value as separate pointers. It stores some not strictly necessary numbers, such as the number of sub-nodes of the right child of a node. This allows to calculate the overall count quickly, but can be removed to make the structure's overhead smaller. The code has been extensively tested, is apparently AFL-proof, and leaks no memory whatsoever according to valgrind. BOSTree has been in use in pqiv for some time now. ALTERNATIVES: · In GNU/C++, Policy-Based Data Structures can be used according to http://stackoverflow.com/questions/11230734/c-stl-order-statistic-tree That code probably is much more mature. Use it if this is an option! · If you do not need the order statistic part, there are plenty of balanced tree implementations which suit your use case better. They are better tested and much faster because they do not have the overhead of order statistics. For example, see glib: https://developer.gnome.org/glib/stable/glib-Balanced-Binary-Trees.html · glib appears to have a concealed order statistic balanced binary tree implementation, only they name this sequences: https://developer.gnome.org/glib/stable/glib-Sequences.html Licensed under the terms of the GPLv3.