A red-black tree is a binary search tree with extra "nil" nodes as leaves of every content node with a child-relationship to spare, and a "color", one of red or black, associated with every node, such that these properties are satisfied:
1. Every nil node is black.
2. No red node has a red node as a child.
3. Any path from the root to a leaf has the same number of black nodes.

A red-black tree can never have a depth more than (maybe plus 1), where is the number of nodes. Therefore, operations like searching will always take time.
The only difficulty is the coding of the algorithms that modify the tree, namely, insert and delete, while preserving the three rules.
Note that we can always set the root to be black if it isn't.

Okay. Insert.

Proceed adding the node like in normal search trees. Search from the root to a "nil" node which could be replaced with the node. Replace it, color it red, and give it two black "nil" nodes. As a result, any path through that node would still get one black node from it or its children, so rule 3 is preserved. Rule 2 may not, unfortunately.

So, let the node in question be x. If x's parent is black, no problem. Of course according to Finagle's, x's parent will turn out to be red. (Note that since rule 2 held before we started, x's grandparent must be black (or not exist, but that case would be too easy (? (left to the reader))).) We look at the color of x's uncle, i.e. x's grandparent's other child.

If x's uncle is red, we can color x's parent and uncle black, x's grandparent red, set x to x's grandparent, and repeat.

If x's uncle is black, we'll do this awkward thing called "rotation", which involves switching a bunch of subtrees around, with the nodes, which goes like this:

Y ---  X
   X  3--- 1  Y
  1 2  ---2 3

"Left-rotation" turns the thing on the right to the thing on the left.
"Right-rotation" turns the thing on the left to the thing on the right.

Anyway, first we rotate x and x's parent if necessary, so that the path from x to x's grandparent is straight (right twice or left twice). Since x and x's parent are both red, no problem with rule 3 occurs. We'd also have to let x's previous-parent-and-now-child be the new x.

Next, remembering that x's uncle was black, we'll rotate-away-from-x x's grandparent and x's parent, and color x's previous-grandparent-and-now-sibling red (this works since x's uncle is black, which I've already stressed too much) and x's previous-parent-and-now-still-parent black. And we're done!

Deletion comes later.