阅读3.0版本以后的内核源代码就会发现,新版本内核中的红黑树的实现与之前有所不同。新的实现提供了增强特性,用户可以在红黑树结点中符加一些数据结构来提供更多的功能。区间树就是一种增强型的红黑树。《算法导论》中有关于区间树详细的介绍。下图是取自《算法导论》的一棵区间树:

区间树

Linux内核中红黑树的实现中提到了这种特性,但没有详细介绍。下面就利用这种特性实现区间树。

按照《算法导论》中的讲解,区间树需要提供三种基本操作:查找、插入和删除。这里定义区间树的结构是:

先实现查找操作,因为它不需要修改结点信息:

插入删除操作需要修改结点的信息,可以使用三个回调函数实现,它们通常被封装在struct rb_augment_callbacks 结构中:

propagate 是传播回调函数。它的工作就是更新node到它的祖先stop结点之间的每一个结点的附加信息。

copy 是拷贝回调函数。它的工作是将new结点的附加信息设置成old的附加信息。

rotate 是旋转回调函数。它的工作是将new结点的附加信息设置成old的附加信息,并重新计算old的附加信息。

Linux内核中红黑树的实现中分析普通红黑树的实现时已经看到,红黑树的实现操作会在合适时间会调用这三个回调函数更新结点信息,现在要做的只是实现这三个回调函数。

对区间树执行插入删除操作时需要修改结点的信息只有子树的最大边界值,所以先创建一个辅助函数来获得子树的最大边界值。

propagate 函数的两个参数分别是起始结点和终止结点,在它们之间的所有结点都会被重新计算子树最大边界值:

copy函数只是简单地复制:

类似的写出 rotate 函数:

将这三个回调函数封装到 rb_augment_callbacks 结构中:

接下来就可以实现插入删除操作了:

删除操作很简单,只需要提供回调函数,红黑树的删除操作就可以做所有工作。

插入结点时,需要找到待插入结点的位置,Linux内核中红黑树的实现中说过,新插入的结点总是叶子结点。所以在while循环中不断向下遍历,同时更新经过的结点的子树最大边界值。

rb_link_node 函数的作用是将结点连接到红黑树中,它有三个参数,第一个是待插入的结点,第二个是待插入结点的父结点,第三个参数是一个二维指针,它指向的是父结点的左孩子或者右孩子,也就是在while循环中找到的位置。该函数定义在<rbtree.h>中:

最后调用 rb_insert_augmented 函数调整红黑树使之符合红黑树的特性。