이진탐색트리 - https://velog.io/@ddosang/자료구조-7-이진탐색트리

9. Red-Black Tree

높이가 h 인 이진 탐색 트리에서 시간 복잡도는 O(h) 가 되는데,
최악의 경우, 경사 이진트리 이므로 O(h) = O(n) 이 된다.

-> 이런 최악의 경우를 막고 log n 을 유지하기 위해, 레드블랙트리를 사용한다.

1. 레드블랙 트리의 조건

1. Root : 내 루트의 색깔은 Black
2. External Node : 외부노드는 모두 Black (NULL 인 자식을 두개 갖고 있는 걸로 치기 때문에 해당 노드가 블랙)
3. Internal Node : 내부노드 Red 의 자식은 Black ( 빨간 노드가 연속으로 나올 수 없음 )
4. Depth Property : 모든 단말 노드에서 검정색의 높이는 같다. ( 단말에서 루트까지 가는 길에 만나는 검정 노드의 개수는 같다. )

( 빈 노드는 블랙 )

2. 삽입

1. 루트는 블랙

2. 일단 삽입할 때 전부 레드.

3. Double Red 해결

레드의 자식이 레드이므로 3번 조건에 위배되기 때문에 해결해주는 것

해결방법 1. Restructuring
해결방법 2. Recoloring

만약 같은 부모와 같은 레벨에 블랙이 있으면, Restructuring (재구조)
없으면, Recoloring (색을 바꿈)

3-1. Restructuring

1. 현재 insert 된 노드(z) 와 그 부모 (v), 그 부모의 부모 (grand parent) 를 오름차순으로 정렬
2. 정렬된 값의 가운데 값을 부모로 만들고,
3. 나머지 두 값을 그 부모의 자식으로 만든다.

1, 2. 25가 부모가 되고, 20, 30이 왼쪽 오른쪽 자식이 되는 것.

3. 그리고 20의 원래 자식인 10을 추가.

-> 이 과정이 다른 서브트리에 대해서는 영향을 미치지 않는다. (4-2)

Double Red 를 해결하기 전과 해결한 후의 Black 노드 개수가 같으므로 4번 Depth Property 도 만족.
-> 그렇다면.. 리컬러링은...??

3-2. Recoloring

1. 현재 insert 된 노드 (z) 의 그 부모 (v) 그리고 부모의 형제 (w) 검정으로 하고, (v, w 를 블랙)
2. z 의 부모의 부모를 빨강으로 한다.
3. z 가 루트가 아니면..? 또 더블 레드가 발생할 수 있음..

1, 2. 조부모까지 색상 변경

z 가 루트라면, 1번 조건(루트는 항상 블랙) 에 의해 이렇게 마무리 되지만..

아니라면..? 2번까지 마친 상태가 됨. 근데 4의 부모가 또 레드였다면...으악... 위에를 다 바꿔야 됨... 결국 루트까지 싹 다 바꿀 수 있음...

2. 삭제

1. 빨간색 노드를 삭제한 경우 : 4번 조건(루트로부터 리프로까지의 모든 블랙 노드 개수는 같다)에 상관 없으므로 그냥 삭제하면 됨.
2. 검은색 노드를 삭제한 경우 : 문제가 생김
   -> 이중 흑색 이라는 개념으로 해결한다.
   

3. 구현

구조체

#define BLACK 0
#define RED 1

// restructring, recoloring 을 편하게 하기 위해 parent 까지 저장한다.
typedef struct Node {
    int data;
    int color;
    struct Node *left, *right, *parent;
} Node;

typdef struct RBTree {
    Node *root;
} RBTree;

void create(RBTree tree) {
    tree->root = NULL;
}

ADT

// 탐색
Node search(RBTree *tree, Element key)


// 회전 (AVL 트리의 회전과 같음.)
void rotateLeft(RBTree *tree, Node *parent) // node 기준 왼쪽 회전. node 없으면 반환.
void rotateRight(RBTree *tree, Node *parent)

// 삽입
Node* insert(RBTree *tree, Element key)
Node* insert_fixup(RBTree tree, Node node)

// 삭제
void delete(RBTree *tree, Element key)
void transplant(RBTree *tree, Node *u, Node *v) // 삭제할 노드와 중순위 후계자를 바꿔주는 역할.
void delete_fixup(RBTree *tree, Node node)

탐색

Node search(RBTree tree, Element key) {
    Node *node = tree->root;
    
    while (node != NULL && node->key != key) {
        node = (node->key < key) ? node->left : node->right;
    }
    
    if (node == NULL) {
        printf("찾는 키가 없습니다.");
        return;
    }
    return node;
}

회전

void rotateLeft(RBTree tree, Node *parent) {
    Node *child = parent->right;
    parent->right = child->left;
    if (child->left != NULL)
    	child->left->parent = parent;
    
    child->parent = parent->parent;
    
    if (child->parent == NULL)
        tree->root = child;
    else if (child == child->parent->left)
        child->parent->left = child;
    else
        child->parent->right = child;
    
    
    child->left = parent;
    parent->parent = child;
    return child;
}

void rotateRight(RBTree tree, Node *parent) {
    Node *child = parent->left;
    parent->left = child->right;
    
    if (child->left != NULL)
        child->right->parent = parent;
    
    child->parent = parent->parent;
    
    if (child->parent == NULL)
        tree->root = child;
    else if (child == child->parent->left)
        child->parent->left = child;
    else
        child->parent->right = child;
    
    
    child->right = parent;
    parent->parent = child;
    return child;
}

삽입

Node* insert(RBTree tree, Element key) {
    Node *p = NULL;
    Node *t = tree->root;
    Node *new = (Node *)malloc(sizeof(Node));

    while (t != NULL && t->key != key) {
        p = t;
        t = (t->key < key) ? t->left : t->right;
    }
    
    if (t != NULL) {
        printf("키가 이미 트리에 있음.");
        return;
    }
    
    new->key = key;
    new->left = NULL;
    new->right= NULL;
    new->parent = p;
    new->color = RED;
    
    tree->root = new;
    if (t->key < key) {
        t->left = new;
    } else {
        t->right = new;
    }
    
    insert_fixup(t, new);
    
    return new;
}

1. 노드의 삼촌이 빨강 -> recoloring
   

2. 노드의 삼촌이 블랙이면서, -> restructuring
   2-1. 노드가 오른쪽 자식임 -> 왼쪽 회전
   2-2. 노드가 왼쪽 자식임 -> 오른쪽 회전

void insert_fixup(RBTree tree, Node node) {
    Node *uncle; // 부모의 형제
    
    // 부모가 레드면 fix-up
    while(node->parent->color == RED) {
        uncle = (node->parent == node->parent->parent->right) ? node->parent->parent->left : node->parent->parent->right
        
        if (uncle->color == RED) {
            node->parent->color = BLACK;
            uncle->color = BLACK;
            node->parent->parent->color = RED;
            node = node->parent->parent; // 위로 올라가면서 계속 수행.
        }
        
        else if (node == node->parent->left) {
            rotate_right(tree, node->parent);
        } else {
            node->parent->color = BLACK;
            node->parent->parent->color = RED;
            rotate_left(tree, node->parent->parent);
        }
    }
    
    tree->root->color = BLACK;
}

삭제

• 중순위 후계자를 찾아서 삭제할
• 노드와 교체하고 리프를 삭제하는 방식 대신,
• 자식과 노드 위치를 교환하는 방법 사용.

void delete(RBTree tree, Element key) {
    Node *target, *child, *succ; // 삭제할 노드, 그 자식 (중순위 후계자의 자식일수도), 중순위 후계자
    int succ_original_color;
    
    target = tree->root;
    
    while (target != NULL && t->key != key) {
        target = (target->key < key) ? target->left : target->right;
    }
    
    if (target == NULL) {
        printf("키가 트리 안에 없음.");
        return;
    }
    
    succ = target;
    succ_original_color = p->color;
    
    // 1. 오른쪽 자식만 있음.
    if (target->left == NULL) {
        child = target->right;
        transplant(tree, target, child);
    }
    
    // 2. 왼쪽 자식만 있음.
    else if (target->right == NULL) {
        child = target->left;
        transplant(tree, target, child);
    }
    
    // 3. 양쪽 자식 다 있어서 중순위 후계자 찾아야하는 경우
    else {
        succ = target->right;
        while (succ->left != NULL) {
            succ = succ->left;
        }
        
        succ_original_color = succ->color;
        child = succ->right;
        
        // 3-1. 삭제할 노드의 자식의 자식이 오른쪽 자식만 있었던 경우
        if (succ->parent == target) {
            succ->parent = target; // 사실 이 라인 왜 있는건지 모르겠음.
        }
        
        else {
            // succ 이 target 대체할거니까, succ 을 먼저 succ->right 으로 대체.
            transplant(tree, succ, succ->right);
            succ->right = target->right;
            succ->right->parent = succ;   
        }
        
        transplant(tree, target, succ); // succ 이 target 대체.
        succ->left = target->left;
        succ->left->parent = succ;
        succ->color = target->color; // 컬러는 삭제하는 노드의 컬러 유지.
    }
    
    // 삭제한 (target 말고 진짜 삭제된 succ 자리) 노드가 블랙이라면..
    if (succ_origin_color == BLACK) {
        delete_fixup(tree, succ); // 색깔 재배치 필요.
    }
    
    free(target);
    
    return 0;
}

사진 출처 : introduction to algorithms 3/E

void delete_fixup(RBTree *tree, Node *node) {
    while (node != tree->root && node->color == BLACK) {
        // 1. fixup 할 노드가 왼쪽 자식이고,
        if (node == node->parent->left) {
            Node *sibling = node->parent->right;
            
            // 1-1. 형제가 레드임.
            if (sibling->color == RED) {
                sibling->color = BLACK;
                node->parent->color = RED;
                rotateLeft(tree, node->parent);
                sibling = node->parent->right;
            }
            
            // 1번 케이스를 고치면 2, 3, 4 케이스 중 하나가 되기 때문에 바로 실행.
            // 1-2. 형제와 형제 자식이 모두 블랙
            if (sibling->left->color == BLACK) {
                sibling->color = RED;
                node = node->parent; // 나중에 node 컬러 바꿀거라서.
            }
            
            // 1-3. 형제 블랙, left 레드, right 블랙
            else {
                if (sibling->right->color == BLACK) {
                    sibling->left->color = BLACK;
                    sibling->color = RED;
                    rotateRight(tree, sibling);
                    sibling = node->parent->right;
                }
                
                // 3번을 고치고 나면 4번 케이스가 되기 때문에 그냥 바로 실행하는 것.
                // 1-4. 형제 블랙, left 블랙, right 레드
                sibling->color = node->parent->color;
                node->parent->color = BLACK;
                sibling->right->color = BLACK;
                rotateLeft(tree, node->parent);
                node = tree->root;
            }
        }
        
        // 2. node 가 오른쪽 자식이면 -> 1-1 ~ 1-4 를 반대로 수행한다.
        else {
            Node *sibling = node->parent->left;
            
            if (sibling->color == RED) {
                sibling->color = BLACK;
                node->parent->color = RED;
                rotateRight(tree, node->parent);
                sibling = node->parent->left;
            }
            
            if (sibling->left->color == BLACK) {
                sibling->color = RED;
                node = node->parent;
            }
            
            else {
                if (sibling->right->color == BLACK) {
                    sibling->left->color = BLACK;
                    sibling->color = RED;
                    rotateLeft(tree, sibling);
                    sibling = node->parent->left;
                }
                
                sibling->color = node->parent->color;
                node->parent->color = BLACK;
                sibling->right->color = BLACK;
                rotateRight(tree, node->parent);
                node = tree->root;
            }
        }
    }
}

4. 시간복잡도

어떤 경우에도 O(log n) 이 나온다.

노드 삽입 (탐색 + 삽입) = O(log n)

• restrucuring = O(1)
• recoloring = O(1) * O(log n)

-> O(log n) 어떤 경우에도!!

노드 삭제 (탐색 + 삭제) = O(log n)

높이 균형

4번 조건인 Depth priority 덕분에
블랙 개수가 같으면서 높이가 가장 낮으려면 = 검검검검 = (높이 == 블랙개수)
블랙 개수가 같으면서 높이가 가장 높으려면 = 검빨검빨검빨검빨 = (높이 == 블랙개수 * 2)

하지만, 레드블랙트리도 치우친 이진탐색트리보단 효율적이나,
삽입 삭제에 리스트럭쳐, 리컬러링 오버헤드가 큼.
여기서 더욱 효율성을 따지고 싶다면 B트리를 이용한다.

참고

개념

• https://zeddios.tistory.com/237

코드

• 탐색, 삽입 : https://velog.io/@whddn0221/레드블랙트리-구현하기#구현-범위
• 삭제 : https://leeyongjeon.tistory.com/entry/C언어-레드블랙-트리-삭제-알고리즘RedBlack-Trees-in-C-deleting-or-removing-algorithm?category=585635

사진

• https://www.cs.usfca.edu/~galles/visualization/RedBlack.html