生活在BSD的树上

FreeBSD、OpenBSD系统都自带了一个很好用的红黑树和splay树实现。

这个实现只有头文件，无需外部依赖，而且是泛型的。所以想在Linux下面用起来也很简单。

获取头文件

运行：

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

这个头文件里面包含了sys/_null.h，这个文件在Linux里面是没有的。不过，tree.h用这个文件只是为了定义NULL，所以改成stdlib.h就行了。

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

声明

头文件tree.h中的树实际上全是宏，所以用之前需要先展开。举个例子，如果希望树中的值类型是double，那么新建一个头文件double_tree.h，在文件中这样声明：

#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

定义

然后创建源文件double_tree.h，补充需要的函数定义：

#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)

使用

接下来介绍如何使用这个double_tree。

初始化

创建树并初始化：

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

初始化也可以一行完成：

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

插入

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

查找和删除

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

遍历

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

其实，RB_FOREACH(iter, double_tree, &head)本质上是：

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

用RB_MIN可以取得树中的最小节点；用RB_NEXT可以获取iter的下一个元素；RB_MAX则是最大节点。

如果想用其他的顺序遍历树的话，可以用RB_LEFT和RB_RIGHT。比如说，用前序遍历打印树：

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(")");
    }
}

其他

有个很怪的事情，Arch Linux里面有tree.h的man文档，执行man 3 tree就能看到，但是这个头文件本体却找不到。

这篇文章里面只写了红黑树，但是splay树其实也大同小异，就不再赘述了，可以直接去翻文档。

勘误

感谢@w3cing的提醒。FreeBSD所提供的tree.h中的RB_TREE实际上并非红黑树，RB指的是rank-balanced tree，而具体的实现是weak AVL。FreeBSD在2020年8月对tree.h进行过一次修改。