RB_ROOT(3) on FreeBSD
The text 65a0c20dbd25, as FreeBSD 6.3-RELEASE, FreeBSD 6.2-RELEASE, FreeBSD 6.1-RELEASE, FreeBSD 6.0-RELEASE, FreeBSD 5.5-RELEASE, FreeBSD 5.4-RELEASE, FreeBSD 5.3-RELEASE shipped it.
implementations of splay and red-black trees