开源 C 语言库 Melon：红黑树

[monkeyNik]

本文对 Melon 库中的红黑树进行介绍，关于 Melon 库，这是一个开源的 C 语言库，它具有：开箱即用、无第三方依赖、安装部署简单、中英文文档齐全等优势。

Github repo

简介

红黑树是一种被应用的非常广泛的数据结构，用于快速搜索指定数据集中的数据。

这里我们不对红黑树的原理进行展开，仅给出其时间复杂度和使用场景介绍。

时间复杂度

• 插入：O(logN)
• 删除：O(logN)
• 搜索：O(logN)

使用场景

• 实现字典查询，即 kv 查询
• 文件描述符索引，例如维护 socket fd

使用

Melon 库中的红黑树经历了若干次迭代，最终形成了当前的使用形态。我们先给出代码，再进而说明为何会演变至此。

红黑树

#include <stdio.h>
#include <stdlib.h>
#include "mln_core.h"
#include "mln_log.h"
#include "mln_rbtree.h"

static int cmp_handler(const void *data1, const void *data2)
{
    return *(int *)data1 - *(int *)data2;
}

int main(int argc, char *argv[])
{
    int n = 10;
    mln_rbtree_t *t;
    mln_rbtree_node_t *rn;
    struct mln_rbtree_attr rbattr;
    struct mln_core_attr cattr;

    cattr.argc = argc;
    cattr.argv = argv;
    cattr.global_init = NULL;
    cattr.master_process = NULL;
    cattr.worker_process = NULL;
    if (mln_core_init(&cattr) < 0) {
        fprintf(stderr, "init failed\n");
        return -1;
    }

    rbattr.pool = NULL;
    rbattr.pool_alloc = NULL;
    rbattr.pool_free = NULL;
    rbattr.cmp = cmp_handler;
    rbattr.data_free = NULL;
    rbattr.cache = 0;

    if ((t = mln_rbtree_new(&rbattr)) == NULL) {
        mln_log(error, "rbtree init failed.\n");
        return -1;
    }

    rn = mln_rbtree_node_new(t, &n);
    if (rn == NULL) {
        mln_log(error, "rbtree node init failed.\n");
        return -1;
    }
    mln_rbtree_insert(t, rn);

    rn = mln_rbtree_root_search(t, &n);
    if (mln_rbtree_null(rn, t)) {
        mln_log(error, "node not found\n");
        return -1;
    }
    mln_log(debug, "%d\n", *((int *)mln_rbtree_node_data(rn)));

    mln_rbtree_delete(t, rn);
    mln_rbtree_node_free(t, rn);

    mln_rbtree_free(t);

    return 0;
}

main函数大致流程如下：

1. 定义变量
2. 初始化 Melon 库
3. 设置红黑树初始化属性
4. 创建红黑树
5. 创建红黑树结点
6. 插入结点
7. 搜索结点
8. 删除结点
9. 销毁结点
10. 销毁红黑树结构

Melon 中，使用红黑树需要引入mln_rbtree.h头文件。

这里我们需要对红黑树初始化属性进行一番说明，这也是演变至今逐渐变复杂的地方。

struct mln_rbtree_attr {
    void                      *pool;
    rbtree_pool_alloc_handler  pool_alloc;
    rbtree_pool_free_handler   pool_free;
    rbtree_cmp                 cmp;
    rbtree_free_data           data_free;
};
typedef void *(*rbtree_pool_alloc_handler)(void *, mln_size_t);
typedef void (*rbtree_pool_free_handler)(void *);
typedef int (*rbtree_cmp)(const void *, const void *);
typedef void (*rbtree_free_data)(void *);

其中：

• pool是用于支持用户自定义内存池之用的，该指针将于pool_alloc和pool_free配合使用。
• pool_alloc是用于支持用户自定义分配内存之用，该函数指针第一个参数为pool，第二个参数是要分配的内存大小。
• pool_free是用于支持用户自定义释放内存之用，该函数指针第一个参数为要释放的内存起始地址。
• cmp是用于对两个树结点所关联的用户自定义数据进行比较大小之用的。
• data_free是用于对红黑树结点所关联的用户自定义数据进行释放之用的。

这些指针，若无需要可以置NULL。

内存池和分配释放函数主要是用于树结点的分配和释放之用。之所以不直接给出一个 Melon 实现的内存池结构指针，是因为不希望红黑树代码与内存池类型强关联，这样允许红黑树可以接入使用者自己定义的内存管理功能。

演化

早期，红黑树只有cmp和data_free。后来加入了pool、pool_alloc和pool_free来增加内存分配来源。

从 14 年至今的使用中，会不断遇到新的使用场景，因此对红黑树内部结构做各种调整，例如：

• 遍历红黑树所有结点
• 遍历红黑树所有结点的同时删除其中的结点
• 增加结点计数

因此，如果读者阅读源码，会发现树结构中还有一个双向链表结构用来辅助结点遍历。

可能有的读者会提出，为什么树结点不能与关联的自定义数据结构一同分配，类似如下代码：

struct some_struct {
    int val;
    ...
    mln_rbtree_node_t node;
}

void some_function(...)
{
    struct some_struct *s;
    mln_rbtree_t *tree;
    
    s = malloc(...);//allocate struct some_struct
    mln_rbtree_node_init(&s->node, s);
    ...
    mln_rbtree_insert(tree, &s->node);
    ...
}

这段代码不能真实执行。

之所以不这样设计，并非没有设想和尝试过。但是发现如此设计存在一下优劣势：

• 优势：少了一次树结点内存分配动作
• 劣势：如果结点要加入多个树结构，则需要在结构体中给出多个 node 成员，若并不一定每一个树结构都加入，则会造成一定的内存浪费。且后续功能扩展时引入了红黑树结构，也有可能要给很多结构体中引入 node 结点，才能完成红黑树的功能，这增加了二开的成本。

结语

Melon 中的红黑树目前演化至此，相信也不会是其最终形态。也希望广大开发者朋友提出宝贵意见和建议。

另外对于 Melon 库感兴趣的读者，可以访问Github 仓库。

感谢阅读！

[Or2]

哈哈，我也刚学着写了一个，正好学习下你的

[duke807]

我直接拿 linux 内核的 红黑树 代码来用，不依赖内存 malloc ，MCU 也可以用

https://www.amobbs.com/thread-5716767-1-1.html

https://github.com/dukelec/cdnet/tree/master/utils 目录下的 rbtree.c 和 rbtree.h 文件

[duke807]

> 之所以不这样设计，并非没有设想和尝试过。但是发现如此设计存在一下优劣势

你例出来的优势少了最重要的一点：性能

譬如你遍历整个树，比较用户数据大小，每次要通过指针取用户数据

而 linux 式的做法，node 本身一般放在开头，和用户 struct 数据地址是一样的（即使不放开头也是一个固定偏移），编译器会直接优化，节省一次取指针变量数据的操作

同时，linux 式的做法更优雅

至于 op 说的同时挂多个树，实际极少有这样的需求，需要的时候加一层 wrapper 也很方便

[learningman]

@duke807 #3 树套树搞算法竞赛的可能见的多

[monkeyNik]

@duke807 感谢阅读。
事实上，
“而 linux 式的做法，node 本身一般放在开头，和用户 struct 数据地址是一样的（即使不放开头也是一个固定偏移），编译器会直接优化，节省一次取指针变量数据的操作”
你说的这段我在实际项目经历中确实有这么用过。因此我也想过将我的红黑树代码进行这样的重构。然而失败了，原因正如我给出的：“同时挂多个树”，这个场景出现在我的脚本解释器中。在脚本解释器中实现了一些内置函数和库函数用来打印一些变量的值和详细的信息。对于复杂数据类型（如数组、对象等）一般是使用红黑树实现的。因此可以想见，有多少变量可能会加入树中，又有多少种数据结构需要增加树结点成员。这会使得整个解释器的结构体定义非常难看，且每引入一棵树，就有可能对很多结构体增加一个 node 成员，这样的维护量会越来越难以承受的。

[dcoder]

支持一下. 我看这个 repo 从 2014 年就开始了，还挺久了啊

[Or2]

我在每个 node 都加入了 min, max, 来指向 subtree 的最小 node,和最大的 node ，每次插入和删除的时候，也更新这两个属性。
请问：
1. 这样做是不是有什么不好的地方？
2. 为什么大家都再用红黑树，而不是 AVL 树，这个在实际中的考量是什么？

[monkeyNik]

@dcoder 感谢感谢～
@Or2 不用 avl 是因为构建成本（插入和删除要保证严格二叉平衡树特性而带来的转枝开销）比红黑树要高，虽然他的查询最优，所以如果你的场景是查询远大于插入删除，甚至一次构建其余时间都是查询，那可以考虑 avl 。至于说加 min 和 max ，这样做的代价就是会有额外对部分树结点的遍历，一方面来自于结点增加或移除后向上回溯，另一方面来自转枝后结点关系改变因此 max 和 min 要重新取值再回溯。总之改造越多性能肯定会受到一些影响，但也要取决于你想要实现什么功能。或者你也可以考虑将多种数据结构施加给同一个结构体来实现自己的需求，例如红黑树加链表实现快速插入删除搜索和 LRU 。

[Or2]

@monkeyNik 我确实实现了 avl-tree+linkedlist, 或者 rb-tree+ linkedlist, 是不是如果考虑快速插入删除搜索，rb-tree+linkedlist 性能优于 avl-tree+linkedlist.
还有一个问题，就是看到 https://zhuanlan.zhihu.com/p/462750015 这个帖子，如果用 bp-tree+linkedlist 是不是性能会更好？

[monkeyNik]

@Or2 第一个问题，常规频繁插入删除查找的动态数据场景下，rbtree 会优于 avl 。第二个问题，我没有对比过不敢妄下定论，而且也要考虑一些特定场景，就好像一般的字符串匹配算法和 kmp 算法一样。理论上的优劣有时候和实际实现是相悖的。例如整数大数计算中的乘法，理论上 FFT 优于朴素算法（两层循环嵌套），但实际的软件层面实现和测试结果上，朴素算法远优于其他算法。