The BSD Tree

OpenBSD comes with a handy implementation of red-black trees and splay trees, which are included in the system's header file here.

This implementation only consists of a header file, requiring no external dependencies, and is generic. Therefore, using it in Linux is straightforward.

Obtaining the Header File

Run:

curl https://raw.githubusercontent.com/openbsd/src/master/sys/sys/tree.h -o tree.h

This header file includes sys/_null.h, which is not present in Linux. However, tree.h uses this file only to define NULL, so it can be replaced with stdlib.h:

// #include <sys/_null.h>
#include <stdlib.h>

Declaration

The tree structures in the tree.h header file are implemented as macros, so they need to be expanded before use. For instance, if you wish to have values of type double in the tree, create a new header file double_tree.h, and declare it as follows:

#ifndef DOUBLE_TREE_H_
#define DOUBLE_TREE_H_

#include "tree.h"

struct double_treenode {
    RB_ENTRY(double_treenode) entry;
    double val;
};

int double_cmp(struct double_treenode *e1, struct double_treenode *e2);

RB_HEAD(double_tree, double_treenode);
RB_PROTOTYPE(double_tree, double_treenode, entry, double_cmp)

#endif

Definition

Then, create a source file double_tree.c to provide the necessary function definitions:

#include "double_tree.h"

int double_cmp(struct double_treenode *e1, struct double_treenode *e2); {
    if (e1->val < e2->val) {
        return -1;
    } else if (e1->val > e2->val) {
        return 1;
    }
    return 0;
}

RB_GENERATE(double_tree, double_treenode, entry, double_cmp)

Usage

Next, let's discuss how to use this double_tree.

Initialization

Create and initialize the tree:2

RB_HEAD(double_tree, double_treenode) head;
RB_INIT(&head);

Initialization can also be done in one line:

RB_HEAD(double_tree, double_treenode) head = RB_INITIALIZER(&head);

Insertion

struct double_treenode *n;
double data[5] = {1.0, 2.0, 3.0, 4.0, 5.0};
for (int i = 0; i < 5; i++) {
    n = malloc(sizeof(struct double_treenode));
    n->val = data[i];
    RB_INSERT(double_tree, &head, n);
}

Searching and Deleting

struct double_treenode find;
find.val = 3.0

struct double_treenode *iter;
iter = RB_FIND(double_tree, &head, &find);

if (iter != NULL) {
    printf("Found\n");
    RB_REMOVE(double_tree, &head, iter);
    free(iter);
}

Traversal

RB_FOREACH(iter, double_tree, &head) {
    // Do something on iter->val
    ...
}

In fact, RB_FOREACH(iter, double_tree, &head) is essentially:

for (iter = RB_MIN(double_tree, &head); iter != NULL; iter = RB_NEXT(double_tree, &head, iter))

RB_MIN retrieves the minimum node in the tree; RB_NEXT gets the next element of iter; RB_MAX is for the maximum node.

For traversing the tree in other orders, RB_LEFT and RB_RIGHT can be used. For example, to print the tree in pre-order:

void
print_tree(struct double_treenode *n)
{
    struct double_treenode *left, *right;

    if (n == NULL) {
        printf("nil");
        return;
    }
    left = RB_LEFT(n, entry);
    right = RB_RIGHT(n, entry);
    if (left == NULL && right == NULL)
        printf("%d", n->val);
    else {
        printf("%d(", n->val);
        print_tree(left);
        printf(",");
        print_tree(right);
        printf(")");
    }
}

BTW

It's odd that while the man page for tree.h exists in Arch Linux (you can view it by running 'man 3 tree'), but the actual header file itself cannot be found.

This article only covers red-black trees, but the usage of splay trees are quite similar, so I won't elaborate further. You can directly refer to the documentation.