4

I could find a C++ one here, but no pure C one. Any pointers?

Community
  • 1
  • 1
Dervin Thunk
  • 19,515
  • 28
  • 127
  • 217
  • 1
    Just out of curiosity, did you end up implementing an interval tree with the red-black tree below or did you find another implementation? – juniper- May 06 '13 at 17:59
  • The Linux kernel has a nice implementation of augmented RB trees, and as an example of augmentation the use interval trees. Long story short, at the end of this document you find an implementation of interval trees in C: https://www.kernel.org/doc/Documentation/rbtree.txt – zakk Dec 01 '17 at 16:29

2 Answers2

4

C code for a red and black tree, licensed with the very generous MIT license.

(Backup at archive.org.)

Prof. Falken
  • 24,226
  • 19
  • 100
  • 173
  • The links above appear to be broken. Mirror: http://web.mit.edu/~emin/www.old/source_code/red_black_tree/index.html – JanX2 Nov 13 '12 at 16:59
  • @JanX2, you have to wait a few seconds, but the links works for me. ™ Updated answer. – Prof. Falken Nov 14 '12 at 06:15
  • 4
    Explanation of using a red and black tree for interval tree at http://www.bowdoin.edu/~ltoma/teaching/cs231/fall07/Lectures/augtrees.pdf – Paul Beusterien Sep 20 '13 at 18:42
0

If you limit the data to nonoverlapping segments, you can use the <search.h> tsearch/tfind etc. binary-tree functions, whereby you use the integer interval tuples as keys. A supplied comparison function would easily put a total-order on segments. To find a segment that includes a given point, tfind for a synthetic interval of width 0.

fche
  • 2,641
  • 20
  • 28