Как устроено красно-черное дерево в TreeMap?

Задали вопрос на собеседовании: как устроено красно-черное дерево в TreeMap? Я не знал ответа, поэтому сказал, что раньше не задавался этим вопросом, и это совершенно не мешало мне использовать TreeMap, когда нужна определенная сортировка элементов. На работу меня не взяли в итоге - нужно было лучше знать теорию. Устроился на работу в другое место.

Прошло время, стало интересно: как же оно всё-таки устроено? Или может быть, достаточно знания того, что для операций containsKey, get, put и remove время выполнения стабильно равно log(n)?