../

生活在BSD的树上
===============

2022-08-17

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进行过一次修改。


--------------------------------------------------------------------
Email: i (at) mistivia (dot) com