This is a red black tree implementation.

Duncan G. Smith got it working as a sorted list.

Dan Stromberg adapted it to work as a sorted list, sorted set, sorted dictionary and sorted duplicate-capable dictionary, using m4.