Libtree Description

Design

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.

• On most architectures (at least the ones I’m using), pointers have some unused bits which can be used to store node’s meta-data. This allows to reduce the size of the node structure, and make them as small as possible on a vast majority of architectures.

  If the hardware you’re working on doesn’t allow such optimisation, the library still provides an implementation which is fully portable (C99), at the cost of an increasing node structure size.

  For now, the optimised (but non portable) version is used if ‘uintptr_t’ is defined on your platform.

• 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).

API

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;
}

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.

Lookup

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.

Insertion

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.

Removal

For speed reasons, the remove operation assumes that the node was already inserted into the tree.

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.

Replace

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.

This operation is faster than remove/insert operations for balanced trees since it doesn’t need to rebalance the tree.

Traversal

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.

Installation

The current Makefile has been tested only on Linux system.

To compile and install the library, just do:

$ make
$ make install

By default the library will be installed in ‘/usr/local/lib’ directory.

As usual you change this path by passing ‘prefix=’ option.

You can also change the installation root directory by passing ‘DESTDIR=’ option.