This library is based on the Libtree library which contains C implementation of several kinds of tree-like structures.
In addition to this, Anytree offers an abstraction level which allows to choose the type of underlying tree when it’s created run-time.
Also it adds some simple, but useful functionality like requesting a tree size, checking whether a tree is empty, cleaning tree and calling a function for each element.
From the technical perspective the build system changed from pure Makefile to CMake.
This is yet another implementation of some famous (balanced) binary search trees. As of writing this, BST, AVL, Red-Black and Splay trees are implemented.
Here’s a list of the major points:
- Nodes of the tree aims to be embedded inside your own
structure. This removes the need to do some malloc/free during
insertion/removal operations and saves some space since
allocation infrastructure (such as object descriptors or
object alignment) is not required.
The idea is borrowed from the Linux kernel.
- Traversals in both direction are efficient for all type of trees. When needed, some implementations use threaded trees making the traversal algorithm much simpler.
- The trees don’t store duplicate keys. It’s fairly easy to implement duplicate from the user point of view (by having a list at the node for instance) and this allows to have a simple but efficient API (see below).
You should never actually need to play with the internal members of either tree or node structures.
Nodes are embedded inside your own structure, for example:
struct my_struct {
int key;
struct avltree_node node;
};
A tree needs to be initialized before being used. For example, in order to initialize an AVL tree:
struct avltree tree; /* ... */ avltree_init(&tree, cmp_fn, 0);
The user must provide a comparison function. This function will be called by the library with two arguments that point to the node structures embedded in the user structures being compared.
For instance, the user must provide a function whose prototype is:
int my_cmp(const struct avltree_node *, const struct avltree_node *);
To be usefull, the user must be able to retrieve the pointers on his two structures which embed the 2 nodes pointed by the 2 parameters. For that, the library provides a couple of helpers.
bstree_container_of(node, type, member) rbtree_container_of(node, type, member) avltree_container_of(node, type, member) splaytree_container_of(node, type, member)
Below gives a definition of the comparison function:
int my_cmp(const struct avltree_node *a, const struct avltree_node *b)
{
struct my_struct *p = avltree_container_of(a, my_struct, node);
struct my_struct *q = avltree_container_of(b, my_struct, node);
:
return p->key - q->key; }
Basically the comparison function should return zero if keys match, any negative value if the node A should be earlier in a tree or any positive non-zero value otherwise.
A set of functions is provided to manipulate trees. All of them take only pointers to tree and node structures. They have no idea about the user’s structures which contain them.
If you need to search for the node having a specific key then you need to fill up a dummy structure with the key initialized to the value so your compare function will successfully compare the passed dummy structure with the ones inside the tree.
The lookup operation returns the node with the same key if inserted previously otherwise NULL.
Trees don’t store duplicate keys, since rotations don’t preserve the binary search tree property in this case. If the user needs to do so, then he can keep a separate list of all records having the same key.
This is the reason why the insertion functions do insert a key only if the key hasn’t been already inserted. Otherwise it’s equivalent to a lookup operation and the insertion operation just returns the node with the same key already inserted, and no insertion happened. At this point the user can use a list and append the new node to the list given by the returned node.
Indeed tree implementations using parent pointers don’t need to do any lookups to retrieve the node’s parent needed during the remove operation.
Therefore you must use the remove operation with an already inserted node.
Since trees don’t store duplicate keys, the library provides an operation to replace a node with another one whose key is equal to the replaced node.
It is up to a user to make sure that the new key is equal to the replaced one. Here `equal` means that if you would use remove & insert sequence the new node would have the same previous and next nodes. For example, if a tree keys are integers and the tree content is: [ -2 1 5 9 ] we can safely replace key [ 5 ] with anything between [ 2 ] and [ 8 ].
This operation is however faster than remove/insert operations for balanced trees since it doesn’t need to rebalance the tree.
The API allows you to walk through the tree in sorted order.
For that, you can retrieve the next or the previous of any inserted nodes. You can also get the first (leftmost) and the last (rightmost) node of a tree.
You also can use *tree_foreach() and *tree_foreach_backward() for this purpose.
To compile and install the library, just do something like, assuming current directory is named ‘anytree’ and contains source code:
$ mkdir ../anytree-build $ cmake ../anytree $ make $ sudo make install
You can adjust target installation directory using CMAKE_INSTALL_PREFIX on step 2: on Linux:
$ cmake -DCMAKE_INSTALL_PREFIX=/opt ../anytree
on Windows:
$ cmake -DCMAKE_INSTALL_PREFIX=C:/packages ../anytree
On the same step you also can set kind of library you want to compile: shared or static:
$ cmake -DBUILD_SHARED_LIBS=1 $ cmake -DBUILD_SHARED_LIBS=0
It was tested on:
- Windows 8 with Cmake 2.8 and GCC 4.4.0
- Windows 8 with Cmake 2.8 and GCC 4.7.2
- Linux Ubuntu 12.10 with CMake 2.8 and GCC 4.7.2
- Linux Ubuntu 12.10 with CMake 2.8 and Clang 3.1.0