«Красно-черное дерево»

Случай 1: N — новый корень. В этом случае, все сделано. Мы удалили один черный узел из каждого пути и новый корень является черным узлом, так что свойства сохранены.
void
delete_case1(struct node *n)
{
if (n->parent != NULL)
delete_case2(n);
}
Примечание: В случаях 2, 5, и 6 мы предполагаем, что N является левым потомком своего предка P. Если он — правый потомок, left и right нужно поменять местами во всех трех случаях. Опять-таки, примеры кода принимают это во внимание.

Случай 2: S — красный.

6. Сравнение с идеально сбалансированным АВЛ-деревом

6.1. Высота дерева

Пускай высота дерева h, минимальное количество листьев N. Тогда:

• 
  для АВЛ-дерева N(h) = N(h − 1) + N(h − 2). Поскольку N(0) = 1, N(1) = 1, N(h) растёт как последовательность Фибоначчи, следовательно N(h) = Θ(λ^h), где 
  
• 
  для красно-чёрного дерева 
  

Следовательно, при том же количестве листьев красно-чёрное дерево может быть выше АВЛ-дерева, но не более чем в  раз.^[3]
6.2. Поиск
Поскольку красно-чёрное дерево, в худшем случае, выше, поиск в нём медленнее, но проигрыш по времени не превышает 39 %.

6.3. Вставка

Вставка требует до 2 поворотов в обоих видах деревьев. Однако из-за большей высоты красно-чёрного дерева вставка может занимать больше времени.

6.4. Удаление

Удаление из красно-черного дерева требует до 3 поворотов, в АВЛ-дереве оно может потребовать числа поворотов до глубины дерева (до корня). Поэтому удаление из красно-чёрного дерева быстрее, чем из АВЛ-дерева.

6.5. Память

АВЛ-дерево в каждом узле хранит высоту (целое число). Красно-чёрное дерево в каждом узле хранит цвет (1 бит). Таким образом, красно-чёрное дерево может быть экономичнее.
Однако, на практике в обоих типах деревьев используются целые числа, т.к. работа с битами требует дополнительных процессорных вычислений.