一个区间树的C语言实现？

Question

我在这里找到了一个C++的实现 （链接），但是没有纯C的实现。有什么建议吗？

- Dervin Thunk

---

只是出于好奇，你最终是使用下面的红黑树实现了区间树，还是找到了另一种实现方式？ - juniper-

Linux内核有一个很好的增强红黑树实现，作为增强的例子使用了区间树。简而言之，在本文档的末尾，您会找到C语言中区间树的实现：https://www.kernel.org/doc/Documentation/rbtree.txt - zakk

Answer 1

红黑树的C代码，使用非常慷慨的MIT许可证授权。

_{（备份在archive.org上。）}

- Prof. Falken

---

以上链接似乎已经失效。镜像地址：http://web.mit.edu/~emin/www.old/source_code/red_black_tree/index.html - JanX2

@JanX2，你需要等几秒钟，但链接对我有效。™ 更新的答案。 - Prof. Falken

使用红黑树来实现区间树的解释在 http://www.bowdoin.edu/~ltoma/teaching/cs231/fall07/Lectures/augtrees.pdf中。在这个解释中，对于每个节点，存储了关于该节点所代表区间的一些信息，例如最大右端点和最小左端点。通过利用红黑树的性质，可以保证在O(log n)时间内完成基本操作，如插入、删除和查找区间。 - Paul Beusterien

Answer 2

如果您将数据限制为非重叠段，就可以使用<search.h>中的tsearch/tfind等二叉树函数，其中您使用整数区间元组作为键。提供一个比较函数很容易在段上放置一个全序。要查找包含给定点的段，请为宽度为0的合成区间使用。

- fche