레드-블랙 트리
동작 > 삭제(Removal)

이진검색트리에서 두 개의 non-leaf 자식 노드를 가진 노드 X를 삭제할 때, X의 왼쪽 서브트리에서 최댓값 또는 오른쪽 서브트리에서 최솟값을 갖는 노드 Y를 찾고, X에 Y의 값을 복사한다(여기에서처럼). 그리고 Y를 지운다.
이때 Y가 가진 non-leaf 자식 노드는 1개 이하이다. Y의 non-leaf 자식 노드가 2개라면, Y의 값은 최댓값/최솟값이 아닐 것이기 때문이다. ('non-leaf 자식 노드'라고 표현한 이유는, 레드-블랙 트리에는 leaf 노드가 어디든 붙을 수 있기 때문이다.) 따라서 삭제는 최대 한 개의 non-leaf 자식을 갖고 있는 노드를 삭제하는 문제로 치환할 수 있다. 그러므로, 본 문단에서는 한 개 이하의 non-leaf 자식 노드를 가진 노드를 삭제하는 방법만 다룬다.
M은 삭제하고자 하는 노드이고, C는 M의 선택된 자식 노드이다. 만약 M이 non-leaf 자식을 가질 경우, 해당 자식 노드가 C가 되고, 그렇지 않은 경우 두 leaf 노드 중 아무 노드가 C가 된다.
만약 M이 붉은 노드라면, C를 M대신 치환하면 된다. 이 상황은 M이 두 개의 leaf 자식을 갖고 있을 때에만 발생하는데, 왜냐하면 만약 M이 non-leaf 자식 노드와 leaf 자식 노드를 모두 가지는 경우 양쪽의 검은 노드 개수가 달라지기 때문이다. 삭제된 노드를 지나는 모든 path는 단순히 붉은 노드 하나만 없어지게 되고, 삭제된 노드의 부모와 자식 모두 검은 노드이므로, 특성 3(모든 leaf들은 검은 노드)과 특성 4(모든 붉은 노드는 두 개의 검은 자식 노드를 갖는다)는 여전히 유효하다.
또 다른 상황은 M이 검은 노드이고 C가 붉은 노드일 때이다. 검은 노드를 삭제해버릴 경우 특성 4에 위반될 수 있으므로, C를 검은 노드로 바꿔주면 된다.
복잡한 상황은 M과 C가 모두 검은색 노드일 때이다. 이 상황은 두 개의 leaf 자식을 갖고 있는 검은 노드를 지우는 상황에서만 발생하는데, 왜냐하면 M이 non-leaf 자식과 leaf 자식을 모두 가지는 경우, 양 쪽의 검은 노드 개수가 달라지기 때문이다. 이러한 경우 M을 자식 노드 C로 치환한다. 이후 설명부터는 C를 N, C의 형제 노드를 S, N의 새로운 부모를 P, S의 왼쪽/오른쪽 자식을 각각 SL, SR이라고 하겠다.
다음의 함수를 사용하여 형제 노드를 찾을 수 있다.
struct node *sibling(struct node *n)
{
    if (n == n->parent->left)
        return n->parent->right;
    else
        return n->parent->left;
}
우리는 다음의 코드를 통해 위에서 소개한 단계를 밟아나갈 수 있다. 여기서 replace_node함수는 child를 n의 자리에 대입하는 함수이다. 편의를 위해서, 이 섹션의 코드들은 null leaf들은 NULL 대신 실제 노드 객체로 표현할 것이라는 가정을 바탕에 두고 있다. 따라서 검은색 노드가 리프 노드를 표현한 것일 수 있다.(삽입섹션에서 사용된 코드들은 양쪽 표현을 다 사용했었다.)
int is_leaf(struct node* n)
{
    /*
    * '''LEAF'''라는 노드를 struct node* 형식으로 하나 만들어주고 사용하면 된다.
        이 노드는 색깔이 검은색이고, 자식은 가질 수 없고 오직 부모만 가질 수 있다.
    */
    return (n == LEAF) ? 1 : 0;
}
void replace_node(struct node* n, struct node* child)
{
    /*
     *앞에서 n의 부모가 NULL이 되는 경우를 delete_case에 오지 않게 미리 처리해주면 된다.
    */
    child->parent = n->parent;
    if (n->parent->left == n)
        n->parent->left = child;
    else if (n->parent->right == n)
        n->parent->right = child;
}
void delete_one_child(struct node *n)
{
    /*
     * 선제조건: n이 최대 하나의 non-null 자식을 갖고 있음.
    */
    struct node *child = is_leaf(n->right) ? n->left: n->right;

    replace_node(n, child);
    if (n->color == BLACK) {
        if (child->color == RED)
            child->color = BLACK;
        else
            delete_case1(child);
    }
    free(n);
}
만약 N과 N의 원래 부모가 둘 다 검정이었다면, 부모를 삭제하는 것은 N을 지나는 path가 검은 노드 한 개를 덜 갖게 되므로 해서는 안된다. 이는 특성 5(특정 노드에서부터 leaf로 가는 모든 경로에서 같은 수의 검은 노드를 지난다.)를 위반하기 때문에, 트리는 재균형을 맞춰주어야 한다. 고려해보아야 할 몇몇 상황들이 있다:
Case 1: N 이 새로운 루트가 될때. 이 경우에는 더 할게 없다. 우리는 모든 경로에서 하나의 검은 노드를 삭제했고, 새로운 루트 노드는 검은색이므로 모든 특성이 보존된다.
void delete_case1(struct node *n)
{
    if (n->parent != NULL)
        delete_case2(n);
}
void delete_case2(struct node *n)
{
    struct node *s = sibling(n);

    if (s->color == RED) {
        n->parent->color = RED;
        s->color = BLACK;
        if (n == n->parent->left)
            rotate_left(n->parent);
        else
            rotate_right(n->parent);
    }
    delete_case3(n);
}
void delete_case3(struct node *n)
{
    struct node *s = sibling(n);

    if ((n->parent->color == BLACK) &&
        (s->color == BLACK) &&
        (s->left->color == BLACK) &&
        (s->right->color == BLACK)) {
        s->color = RED;
        delete_case1(n->parent);
    } else
        delete_case4(n);
}
void delete_case4(struct node *n)
{
    struct node *s = sibling(n);

    if ((n->parent->color == RED) &&
        (s->color == BLACK) &&
        (s->left->color == BLACK) &&
        (s->right->color == BLACK)) {
        s->color = RED;
        n->parent->color = BLACK;
    } else
        delete_case5(n);
}
void delete_case5(struct node *n)
{
    struct node *s = sibling(n);

    if  (s->color == BLACK) {
        /* 이 문은 자명하다,
            case 2로 인해서(case 2에서 '''N'''의 형제 노드를 원래 형제 노드 '''S'''의 자식노드로 바꾸지만,
            빨강 부모노드는 빨강 자식 노드를 가질 수 없기 때문에 '''N'''의 새로운 형제노드는 빨강일 수 없다). */
        /* 다음의 문은 빨강을 '''N'''의 부모노드의 오른쪽 자식의 오른쪽 자식으로 두기 위함이다.
            혹은 '''N'''의 부모노드의 왼쪽 자식의 왼쪽 자식으로 두기 위함. case 6에 넘기기 위해 */
        if ((n == n->parent->left) &&
            (s->right->color == BLACK) &&
            (s->left->color == RED)) { /* this last test is trivial too due to cases 2-4. */
            s->color = RED;
            s->left->color = BLACK;
            rotate_right(s);
        } else if ((n == n->parent->right) &&
            (s->left->color == BLACK) &&
            (s->right->color == RED)) {/* this last test is trivial too due to cases 2-4. */
            s->color = RED;
            s->right->color = BLACK;
            rotate_left(s);
        }
    }
    delete_case6(n);
}
void delete_case6(struct node *n)
{
    struct node *s = sibling(n);

    s->color = n->parent->color;
    n->parent->color = BLACK;

    if (n == n->parent->left) {
        s->right->color = BLACK;
        rotate_left(n->parent);
    } else {
        s->left->color = BLACK;
        rotate_right(n->parent);
    }
}
case 2를 통과하면 N과 S는 반드시 검은색 노드가 된다. case 2를 통과한 후에 남는 경우의 수는 아래와 같은데, 아래의 경우 모두 각각의 case에서 해결된다.
(P, SL, SR) = (검,검,검) - case 3에서 해결, (빨,검,검) - case 4에서 해결, (검,빨,검) - case 5에서 해결, (빨,빨,검) - case 5에서 해결, (검,검,빨) - case 6에서 해결, (빨,검,빨) - case 6에서 해결, (검,빨,빨) - case 6에서 해결, (빨,빨,빨) - case 6에서 해결. case 1-6까지의 경우를 다 지나면 위와 같이 모든 경우의 수에 대해 커버됨을 확인할 수 있다. (역자 주)
다시 이야기하지만, 함수 콜은 모두 tail recursion 을 이용하므로, 알고리즘은 in-place이다.
위의 알고리즘에서, 부모 노드에 대해 case 1으로 재귀하는 delete case 3을 제외하고는 모든 case에 대해 순서대로 chained되어 있다: 이 경우가 in-place 구현에서 유일하게 효과적으로 루프를 도는 case이다.(case 3에서 한 번의 회전 이후)
추가적으로, 자식 노드에 대해서는 tail recursion이 일어나지 않으므로, tail recursion 루프는 자식 노드에서부터 연결된 조상 노드들로 거꾸로 올라간다. case 1로 돌아가는 루프는 O(log n)번을 넘지 않는다.(n은 삭제 전에 트리에 존재하는 모든 노드의 개수) 만약 case 2에서 회전이 일어나면(case 1-3 루프 중에 유일한 회전), N의 부모노드는 회전 후 빨강으로 변하고, 루프에서 빠져나온다. 그러므로 이 루프 내에서는 회전은 기껏해야 한 번 있다. 루프를 빠져나오고 나서는 두 번 보다 많은 횟수의 추가적인 회전은 일어나지 않기 때문에 모두 합쳐서 3번보다 많은 수의 회전은 일어나지 않는다.