On: Treaps: A Simple Balanced Binary Tree

Here's an interesting partial implementation (no delete):

https://github.com/yairchu/red-black-tree/blob/master/RedBla...

The AVL has a fuller implementation:

https://github.com/yairchu/red-black-tree/blob/master/AvlTre...

It's significantly more complex, but it gives a type-level/compile-time guarantee that the RB tree invariants are kept, which is nice.