I took the Red-Black tree implementation from linux, and tidied it up to work in userspace. The Linux Kernel documentation has a good description of it. To use it, just include this in your project