生活在BSD的樹上

FreeBSD、OpenBSD系統都自帶了一個很好用的紅黑樹和splay樹實現。這個實現只有頭文件，無需外部依賴，而且是泛型的。所以想在Linux下面用起來也很簡單。

獲取頭文件

運行：

curl https://raw.githubusercontent.com/freebsd/freebsd-src/main/sys/sys/tree.h -o tree.h

這個頭文件裏麪包含了sys/cdefs.h，這個文件在Linux裏面是沒有的。不過，tree.h用這個文件只是爲了定義NULL，所以改成stdlib.h就行了。

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

聲明

頭文件tree.h中的樹實際上全是宏，所以用之前需要先展開。舉個例子，如果希望樹中的值類型是double，那麼就這麼聲明：

#include "tree.h"

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

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_HEAD(double_tree, double_treenode);
RB_PROTOTYPE(double_tree, double_treenode, entry, double_cmp)
RB_GENERATE(double_tree, double_treenode, entry, doubl

操作

初始化

創建樹並初始化：

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

遍歷

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樹其實也大同小異，就不再贅述了，可以直接去翻文檔。