[ C언어 ]Red-Black Tree 구현하기

[ Wiki 이미지 ]

BST(Binary Search Tree)의 종류로 BST의 알고리즘을 수정한 알고리즘이다.

 

[ 📌 그렇다면 왜? ]

• 극단적으로 치우쳐 Balance가 무너지는 것을 방지하기 위해서
  • BST의 경우 Search, Insert, Delete 연산이 모두 O(Tree Height) 만큼의 시간 복잡도를 갖는다. 하지만 극단적인 케이스에는 Tree Height가 최악의 케이스가 나올 수 있기 때문이다.
  • Balance가 무너진 트리에서 연산을 계속 하게 될 경우를 피하기 위해서

[ BST 의 극단적인 치우친 트리 ]

[ RB Tree의 균형 잡힌 트리(NIL 노드 포함) ]

두 그림의 트리는 Depth가 확연히 다름을 알 수 있다.

예를 들어서 3을 찾으려면 BST 같은 경우에는 10 ~ 3까지 가야 하는데, RBtree는 7 -> 5 -> 3 으로 3을 찾을 수 있다.

• 최악의 경우에도 트리의 높이에 비례해 O(log N)의 수행능력을 갖게된다.
• BST의 특성은 유지한채 Rotation 시에도 O(1)의 시간 복잡도를 갖는다.

 

[ 📌 노드의 구성 ]

• 색 (Color): 노드의 색상 (Red & Black)
• 키 (Key): 값
• 부모 (Parent): 부모 노드
• 왼쪽 (Left): 왼쪽 자식 노드
• 오른쪽 (Right): 오른쪽 자식 노드
• NIL(NULL)
  • 모든 Leaf Node는 NIL 노드이다.
  • Root노드의 Parent 노드는 NIL 노드이다.
  • 노드는 내부 노드와 NIL 노드로 구성된다.

 

[ 📌 RBtree의 조건 ]

이 규칙들 때문에 발생하는 예외 케이스들 때문에 나는 RBtree가 뭔가 정리는 되어있지만 정형화되어 있는 알고리즘은 아닌거 같다는 생각이 많이 들었다. (물론 모든 케이스에 대한 대처가 되어 있으니 생각과 다르지만)

1. 각 노드는 Red 혹은 Black의 색을 갖는다.
2. 루트(Root)노드는 Black이다.
3. 리프(Leaf)노드는 Black이다.
4. Red노드의 자식은 Black이다. (= Red 노드는 연속해서 나올 수 없다.)
5. Root노드 부터 혹은 임의의 노드로 부터 Leaf노드 까지의 모든 경로에서 나오는 Black의 개수는 모든 경로에서 동일하게 나와야 한다.
   • 높이(Height): 임의의 노드로부터 Leaf 노드까지 가장 긴 경로에 포함된 Edge의 개수
   • 블랙 높이(Black Height): 리프노드까지의 경로상 Black노드의 개수 (BH >= H / 2: Red가 연속될 수 없기에 나오는 공식)
    

[ Height와 Black Height ]

위 그림을 보면 위에서 서술한 RB Tree의 규칙이 적용되어 있음을 알 수 있다.

 

[ 📌 ROTATION ]

• 그림 처럼 노드를 회전 시키는 건데 두 번째 파라미터로 넘어가는 노드를 베이스로 회전한다.
• O(1) 시간 복잡도를 갖는다.
  • 복잡해 보이지만 사실 노드 사이의 관계를 끊고 맺는 작업이기 때문에 시간 복잡도가 O(1) 밖에 나오지 않는다.

[ Left & Right Rotation ]

⚙︎ Left - Rotate Sudo Code

left_rotate(T, x)         // T: tree, z: new node
    y = right[x]          // y를 x의 right node로 만든다.
    right[x] = left[y]    // y의 left node를 x의 right node로 만든다.
    p[left[y]] = x        // y의 left node의 부모를 x로 설정한다.
    p[y] = p[x]           // y의 parent node를 x의 parent node로 설정한다.

    // 1. x의 부모가 nil node인 경우 y를 root node로 설정한다.
    // 2. x가 x부모의 left node면 y가 x 부모의 left node가 되고,
    // 3. x가 x부모의 right node면 y가 x 부모의 right node가 된다.
    if p[x] == nil[T]
        then root[T] = y
    else if x == left[p[x]]
        then left[p[x]] = y
    else
        right[p[x]] = y

    left[y] = x    // y의 left node는 x가 된다.
    p[x] = y       // x의 paernt node는 y가 된다.

⚙︎ Sudo Code 기반으로 작성한 C코드 (Left - Rotate)

void rotate_left(rbtree *t, node_t *x){
    node_t *y = x -> right;
    node_t *nil = get_nil_node(t);
    x -> right = y -> left;
    y -> parent = x -> parent;

    if (y -> left != nil){
        y -> left -> parent = x;
    }

    if(x -> parent == nil){
        t -> root = y;
    } else if(x == x -> parent -> left){
        x -> parent -> left = y;
    } else {
        x -> parent -> right = y;
    }

    y -> left = x;
    x -> parent = y;
}

Right Rotate의 과정은 Left와 대칭되기 때문에 코드가 다르지 않다.

 

[ 📌 INSERT ]

• 노드의 삽입은 BST와 같이 연산한다.
• 노드 삽입이 끝난 후 트리의 균형을 잡기 위한 함수 Fixup()을 호출하게 된다.
  • Root 노드는 Black 이다. ===> 삽입하는 노드는 항상 Red이기에 위반이 가능한 사항이다.
  • Red 노드는 연속해서는 안된다. ===> 항상 Red만 삽입하기 때문에 나올 수 있는 케이스

 

⚙︎ Insert & Fixup Sudo Code

insert(T, z)       // T: tree, z: new node
    y = nil[T]     // y는 node를 타고 내려면서 이전 node를 저장 (insert 위치)
    x = root[T]    // x를 root node로 설정

    while x != nil[T]    // leaf node 까지 반복
        do y = x         
            // 새로운 node key와 x node의 키 비교 후 적절한 위치
            // left, right 판단
            if key[z] < key[x]
                then x = left[x]
            else
                x = right[x]

    p[z] = y    // 새로운 node의 parent는 y node

    // 1. y가 leaf node 인 경우 새로운 node가 root node가 된다.
    // 2. z의 값이 y의 값보다 작다면 y의 left node는 z가 된다.
    // 3. 위 조건이 아니라면 y의 right node는 z가 된다.
    if y == nil[T]
        then root[T] = z
    else if key[z] < key[y]
        then left[y] = z
    else
        right[y] = z

    // new noded의 leaf node 설정 및 RED로 색 배정
    left[z] = nil[T]
    right[z] = nil[T]
    color[z] = RED
    
    RB_Fixup()

fixup(T, z)                             // T: tree, z: new node
    while color[p[z]] == RED            // z의 parent node가 RED 라면
        if p[z] == left[p[p[z]]]        // case: 1, 2, 3
            then y = right[p[p[z]]]     // y: uncle node

             if color[y] == RED             // case1: parent & uncle node가 RED, grand parent node가 BLACK
                then color[p[z]] = BLACK    // parent node를 BLACK으로
                color[y] = BLACK            // uncle node를 BLACK으로 변경
                color[p[p[z]]] = RED        // grand parent node를 RED로 변경
                z = p[p[z]]                 // z를 다시 갱신 후 while 시작
            else if z == right[p[z]]        // case: 2, 3
                then z = p[z]               // z의 부모를 z로 설정 (case 2)
                left_rotate(T, z)           // z를 기준으로 left_rotate (case 2)
                color[p[z]] = BLACK         // z의 parent node를 BLACK으로 설정(case 3)
                color[p[p[z]]] = RED        // z의 grand parent node를 BLACK으로 설정(case 3)
                right_rotate(T, p[p[z]])    // grand parent 기준으로 right_rotate
            else case 4, 5, 6

    color[root[T]] = BLACK  // case1의 상태에서 탈출 시 root가 RED로 끝날 수 있음

Case 1 ~ 3: 부모의 왼쪽 자식인 케이스

Case 4 ~ 6: 부모의 오른쪽 자식인 케이스

 

⚙︎ Case 1: 부모의 형제가 Red인 케이스

[ Case 1 ]

• z (나)                    : Red
• p[z] (나의 부모)    : Red
• y (삼촌)                 : Red
• p[p[z]] (할아버지): Black 
  자식이 Red이기 때문에 기존까지 트리가 정상적으로 유지 되었다면 당연하게 Black이다. (Red - Red Violation)
• 나의 부모가 할아버지의 왼쪽 자식인 케이스

 

❖ Case 1 해결법

1. 부모와 삼촌 그리고 할어버지의 색을 반전(Red -> Black & Black -> Red)
2. 할어버지 노드를 새로운 z(나)로 설정
3. 새로운 z가 Red로 바뀌면서 그 부모의 노드와 관계에서 위반 사항이 생겼을 수 있기 때문에 Loop를 1, 2번을 Root까지 반복한다.
   (위반 사항이 없다면 반복하지 않아도 된다.)
4. 반복중 최악의 케이스를 마주해 Root 노드까지 올라가게 된다면 Root 노드를 Black으로 변경 하면서 종료한다.

 

⚙︎ Case 2, 3: 삼촌이 Black인 케이스 (NIL 노드일 수 있음)

[ Case 2, 3 ]

• z (나) 와 p[z] (부모): Red
• y (삼촌)                   : Black (NIL 가능성 있음)

 

❖ Case 2 , 3 해결법

1. z가 부모의 오른쪽 노드일 경우  p[z]의 부모를 기준으로 Left-Rotate를 실행한다. (Case 2)
2. Red - Red가 선형으로 만들어지면 Case3에 해당하게 되는데 새로운 z를 기준으로 p[p[z]] 기준으로 Right-Rotate를 실행한다. 

물론 노드의 색도 바꿔줘야 하는데 그림처럼 바꿔주면 된다.

Case2 의 경우에는 Case2 -> Case3으로 만들어서 해결해야 하며, Case3의 경우에는 Right-Rotate 한 번에 해결할 수 있다.

Case 4, 5, 6은 대칭적인 문제기 때문에 크게 다를거 없다.

 

⚙︎ Sudo Code 기반으로 작성한 C코드 (Insert & Fixup)

node_t *rbtree_insert(rbtree *t, const key_t key) {
    node_t *nil = get_nil_node(t);
    node_t *new_node = get_new_node(t, key);
    node_t *insert_point = nil;    // 삽입할 위치를 기억하기 위해서 탐색중인 노드의 이전 노드에 위치함
    node_t *cur_node = get_root_node(t);

    // 삽입 위치 탐색 반복문 key 값에 따라서 트리를 타고 내려감
    while(cur_node != nil){
        insert_point = cur_node;
    
       if(key < cur_node -> key){
           cur_node = cur_node -> left;
       } else {
           cur_node = cur_node -> right;
       }
    }

    new_node -> parent = insert_point;

    if(insert_point == nil){    // 첫 노드인 경우 루트 노드로 설정
       t -> root = new_node;
    } else if(key < insert_point -> key){    // 삽입 위치에서 오른쪽, 왼쪽 자식이 될지 구분
       insert_point -> left = new_node;
    } else {
       insert_point -> right = new_node;
    }

    rebuild_after_insert(t, new_node);
    return t -> root;
}

void rebuild_after_insert(rbtree *t, node_t *z){
    node_t *y = t -> nil;

    while(z -> parent -> color == RBTREE_RED){
        if(z -> parent == z -> parent -> parent -> left){
            y = z -> parent -> parent -> right;

            if(y -> color == RBTREE_RED){
                z -> parent -> color = RBTREE_BLACK;
                y -> color = RBTREE_BLACK;
                z -> parent -> parent -> color = RBTREE_RED;

                z = z -> parent -> parent;
            } else {
                if(z == z -> parent -> right){
                    z = z -> parent;
                    rotate_left(t, z);
                }

                z -> parent -> color = RBTREE_BLACK;
                z -> parent -> parent -> color = RBTREE_RED;
                rotate_right(t, z -> parent -> parent);
            }
        } else {
            y = z -> parent -> parent -> left;

            if(y -> color == RBTREE_RED){
                z -> parent -> color = RBTREE_BLACK;
                y -> color = RBTREE_BLACK;
                z -> parent -> parent -> color = RBTREE_RED;

                z = z -> parent -> parent;
            } else {
                if(z == z -> parent -> left){
                    z = z -> parent;
                    rotate_right(t, z);
                }

                z -> parent -> color = RBTREE_BLACK;
                z -> parent -> parent -> color = RBTREE_RED;
                rotate_left(t, z -> parent -> parent);
            }
        }
    }

    t -> root -> color = RBTREE_BLACK;
}

각 Case들은 해결 하는 방법이 있지만 단 1번의 과정으로 해결되지 않고 다른 케이스를 유발하는 형태로 되어있다.

물론 다른 위반사항이 파생되지 않을 수 있음 (Case 4 ~ 6도 동일하다.)

[ 순환 과정 ]

가장 Worst Case는 Case1이 해결되지 않아 Root 노드까지 가서 Root 노드를 Red로 만들고 다시 Black으로 만드는 케이스지만 크게 문제되지 않는다고 생각된다.

 

[ 📌 TRANSPLANT ]

⚙︎ Transplant Sudo Code

[ Transplant Sudo Code ]

삭제를 구현하기 앞서서 먼저 알아야할 함수가 있다.

노드를 삭제할 때 해당 노드를 대체하는 노드가 들어오는 케이스가 생기는데 기존에 있던 노드의 연결관계를 새로 대체되는 노드가 갖게 연결해주는 함수이다.

 

⚙︎ Sudo Code 기반으로 작성한 C코드 (Transplant)

void rbtree_transplant(rbtree *t, node_t * u, node_t * v) {
    if(u -> parent == t -> nil) {
        t -> root = v;
    } else if(u == u -> parent -> left) {
        u -> parent -> left = v;
    } else {
        u -> parent -> right = v;
    }
  
    v -> parent = u -> parent;
}

 

[ 📌 DELETE ]

• 노드를 삭제하는 것 자체는 BST와 같다.
• 삭제시 Red노드를 삭제하는건 문제를 만들지 않는다.
• 삭제시 Black을 삭제시 문제를 야기한다. (Red - Red or Black Height 위반 사항) 

⚙︎ Delete & Fixup Sudo Code

delete(T, z)                                // T: tree, z: new node
    if left[z] == nil[T] or right[z] == nil // child node가 없거나 1개일 경우
        y = z                               // 삭제될 타겟이 z
    else                                    // child node가 2개일 경우
        y = tree-successor(z)               // 삭제될 타겟이 successor

    // successor의 최대 자식은 1명임
    if left[y] != nil[T]    // x: y의 자식으로 y삭제시 x가 y자리를 대체해야함
        x = left[y]
    else
        x = right[y]

    p[x] = p[y]    // y 삭제 준비: x를 y자리 대체하기 위해 부모연결

    // y가 root node인 경우
    // y의 부모에서 left, right 판단 후 연결 (x가 y의 위치를 대체하는 코드)
    if p[y] == nil[T]
        root[T] = x
    else if y == left[p[y]]
        left[p[y]] = x
    else
        right[p[y]] = x

    if y != z    // 삭제한 y가 원래 삭제하려던 z와 다른 경우
        key[z] = key[y]    // data copy into z

    if color[y] = BLACK    // 이진검색 트리의 조건을 만족하기 때문에 RED노드를 삭제하는건 문제가 되지 않음 
        RB-Delete-Fixup(T, x)
    
    return y

delete_fixup(T, x)                           // T: tree, z: delete node
    while x != root[T] and color[x] == BLACK // 루트가 아니고 x의 컬러가 BLACK일 때
        if x == left[p[x]]                   // x가 parent node의 left node인 경우
            w = right[p[x]]                  // 형제 노드 설정

            if color[w] == RED               // w가 RED인 경우(case 1)
                color[w] = BLACK             // (case 1)
                color[p[x]] = Red            // (case 1)
                left_rotate(T, p[x])         // (case 1)
                w = right[p[x]]              // 트리 레벨은 낮아졌으나 x는 Double BLACK, w는 BLACK인 상황 (case 1)

            if color[left[w]] == BLACK and color[right[w]] == BLACK
                color[x] = RED               // (case 2)
                x = p[x]                     // (case 2)
            else if color[right[w]] == BLACK // w의 right child가 BLACK
                color[left[w]] = BLACK       // (case 3)
                color[w] = RED               // (case 3)
                right_rotate(T, w)           // w기준으로 right rotate (case 3)
                w = right[p[x]]              // (case 3)
            color[w] = color[p[x]]           // (case 4)
            color[p[x]] = BLACK              // (case 4)
            color[right[w]] = BLACK          // (case 4)
            left_rotate(T, p[x])             // (case 4)
            x = root[T]                      // while 문 벗어나기 위해 x에 root 대입(case 4)
        else case 5, 6, 7 ,8

    color[x] = Black

이게 내가 맨 처음에 본 수도코드인데..... 

이대로 코드를 제대로 구현하지 못했는지 정상동작 하지 않아서 다른 책에있는 수도코드를 참조하게 되었다.

[ 책에 나와있는 RB Tree Delete 수도코드 ]

[ 책에 나와있는 RB Tree Delete Fixup 수도코드 ]

• Case 1 ~ 4: 부모의 왼쪽 자식 노드인 케이스
• Case 5 ~ 8: 부모의 오른쪽 자식 노드인 케이스

 

⚙︎ Case 1: 부모의 형제가 Red인 케이스

[ Case 1]

• 형제 노드가 Red인 케이스
• 형제 노드의 자식이 Black 인 케이스 (자식 노드가  NIL일 수 없다 -> Black Height 가 맞아야함)
• Double Black은 말 그대로 Black으로 2개 카운트 한다는 말이다.
  • 자식이 둘 인 Black 노드를 삭제 하면서 일어나는 케이스 (Black 노드는 삭제되면 RB Tree의 규칙을 위반하게 만드는데 균형을 잡기 위해서 Double Black 이나 Red & Black(Extra Black) 의 개념이 도입된다.)

 

❖ Case 1 해결법

• p[x] 기준으로 Left-Rotate를 실행한다.
• Case2, 3, 4 중 하나의 케이스로 만든다.

 

⚙︎ Case 2: 형제 노드가 Black, 형제의 두 자식이 Black인 케이스

[ Case 2 ]

• Case2 는 Case1에서 왔는지 삭제시 발생 되었는지에 따라서 해결되는 과정이 다르다.
• 여전히 노드 x는 Double Black 상태를 유지한다.
• 노드 B의 경우 색을 특정할 수 없는 상황이다. (Case1에서 온 경우 Red로 본다.)

 

❖ Case 2 해결법

• 나와 내 형제 노드에서 Black을 뺏는다.(x 에게서는 Extra Black 제거, w는 Red로 변경)
• p[x] 에 Extra Black을 준다. (여기서 케이스가 나뉜다.)
• From Case1: p[x]의 색을 Red라고 특정할 수 있으며, 이 경우 Red & Black이 되어서 바로 종료
• From Delete: p[x]가 Black 이라면 다시 Double Black 상태가 되어서 루프가 필요하다. (다행인점은 Root 쪽으로 이동)

 

⚙︎ Case 3: 형제 노드가 Black, 형제의 왼쪽 노드가 Red

[ Case 3 ]

• Case 3 -> Case 4로 만드는 과정
• 그림에는 쓰지 못했지만 x는 Double Black 상태

 

❖ Case 3 해결법

• w 기준으로 Right-Rotate 실행
• w와 그 왼쪽 노드의 색 변경

 

⚙︎ Case 4: 형제 노드가 Black, 오른쪽 자식이 Red

[ Case 4 ]

❖ Case 4 해결법

1. p[x]와 w의 right 노드 색 반전
2. p[x] 기준으로 Left-Rotate 시행
3. x의 Extra Black 제거 후 종료

그림들을 보면 Color Change 라고 써두었는데 노드의 색을 두 노드가 교환 하는게 아니라 변경하는 거지만 큰 차이 없다고 생각했다.

 

⚙︎ Sudo Code 기반으로 작성한 C코드 (Delete & Fixup)

int rbtree_erase(rbtree *t, node_t *p) {
    node_t *nil = get_nil_node(t);
    node_t *x = NULL;
    node_t *y = NULL;
    color_t y_org_color;

    y = p;
    y_org_color = y -> color;

    if(p -> left == nil) {          // left child node가 없음
        x = p -> right;
        rbtree_transplant(t, p, p -> right);
    } else if(p -> right == nil) {  // right child node가 없음
        x = p -> left;
        rbtree_transplant(t, p, p -> left);
    } else {                        // child node가 2개일 경우
        y = p -> right;             // successor를 찾기 위해서 해당 node의 right부터 서브트리 탐색
        
        while(y -> left != nil){
            y = y -> left;          // 삭제될 타겟이 successor
        }

        y_org_color = y -> color;
        x = y -> right;             // x: y의 자식으로 y삭제시 x가 y자리를 대체해야함

        if(y -> parent == p) {
            x -> parent = y;
        } else {
            rbtree_transplant(t, y, y -> right);
            y -> right = p -> right;
            y -> right -> parent = y;
        }

        rbtree_transplant(t, p, y);
        y -> left = p -> left;
        y -> left -> parent = y;
        y -> color = p -> color;
    }

    if(y_org_color == RBTREE_BLACK) {   // 이진검색 트리의 조건을 만족하기 때문에 RED노드를 삭제하는건 문제가 되지 않음 
        rebuild_after_erase(t, x);
    }

    free(p);
    return 0;
}

void rebuild_after_erase(rbtree *t, node_t *x) {
    node_t *w = NULL;
    
    while(x != t -> root && x -> color == RBTREE_BLACK) {
        if(x == x -> parent -> left){
            w = x -> parent -> right;
            
            // case 1 ~ 4
            if(w -> color == RBTREE_RED){    // case1: 형제 w가 RED
                w -> color = RBTREE_BLACK;
                x -> parent -> color = RBTREE_RED;
                rotate_left(t, x -> parent);
                w = x -> parent -> right;
            }

            // case2: 형제 w의 두 자식노드가 BLACK
            if(w -> left -> color == RBTREE_BLACK && w -> right -> color == RBTREE_BLACK) {
                w -> color = RBTREE_RED;
                x = x -> parent;
            } else {    // case3: 형제 w는 BLACK, w의 left 자식은 RED, w의 right 자식은 BLACK
                if(w -> right -> color == RBTREE_BLACK) {
                    w -> left -> color = RBTREE_BLACK;
                    w -> color = RBTREE_RED;
                    rotate_right(t, w);
                    w = x -> parent -> right;
                }

                w -> color = x -> parent -> color;
                x -> parent -> color = RBTREE_BLACK;
                w -> right -> color = RBTREE_BLACK;
                rotate_left(t, x -> parent);
                x = t -> root;
            }
        } else {    // case 5 ~8
            w = x -> parent -> left;

            // case5 : 형제 w가 RED
            if(w -> color == RBTREE_RED){
                w -> color = RBTREE_BLACK;
                x -> parent -> color = RBTREE_RED;
                rotate_right(t, x -> parent);
                w = x -> parent -> left;
            }

            // case6 : 형제 w는 BLACK, w의 두 지식노드가 BLACK
            if(w -> right -> color == RBTREE_BLACK && w -> left -> color == RBTREE_BLACK) {
                w -> color = RBTREE_RED;
                x = x -> parent;
            } else { // case7: 형제 w는 BLACK, w의 left 자식은 RED, right 자식은 BLACK
                if (w -> left -> color == RBTREE_BLACK) {
                    w -> right -> color = RBTREE_BLACK;
                    w -> color = RBTREE_RED;
                    rotate_left(t, w);
                    w = x -> parent -> left;
                }

                // case8 : 형제 w는 BLACK, w의 right 자식은 RED
                w -> color = x -> parent -> color;
                x -> parent -> color = RBTREE_BLACK;
                w -> left -> color = RBTREE_BLACK;
                rotate_right(t, x -> parent);
                x = t -> root;
            }
        }
    }

    x -> color = RBTREE_BLACK;
}

Delete의 경우에는 순환 과정이 더 복잡한데, Case2번의 경우 계속해서 문제를 야기 시키는 것도 있지만 자기 다시 Case2로 돌아가는 문제점도 생긴다.

 

특이한 점은 Case1 -> Case2의 경우 부모 노드가 Red라고 확정 지을 수 있어서 바로 끝낼 수 있다.

[ 순환 과정 ]

 

사실 혼자서 진행하다가 문제가 생겼었다.... Rotate 함수에 문제가 있었는데 문제를 식별하지 못해서 많은 시간을 썼었고, 구현에 실패해서책에있는 Sudo Code를 통해서 다시 구현하게 되었는데.... 진짜 멘탈 갈릴뻔했다.(사실 멘탈 터짐)

 

조금 더 사람들이랑 붙어서 많은 시간을 보내야 겠다고 생각했다. 

혼자서 소화 가능한 양이라고 생각했던게 크게 잘못 되었던게 아닌가 싶다.

 

⚠️ 나의 RB Tree가 메모리 누수가 생기고 있었던 이유!!! (2023.09.07 추가 작성)

Tree와 그 노드들을 free 해줄 때 Tree에 있는 NIL 노드를 free 해주지 않아서 생겼었다.

void delete_rbtree(rbtree *t) {
    node_t *root = get_root_node(t);
    node_t *nil = get_nil_node(t);

    if(root != t -> nil){
        delete_all(t, root, nil);
    }

    free(t -> nil);  ===> 요 부분이 메모리 누수의 원인
    free(t);
}

트리 생성시 밑의 코드처럼 메모리 할당을 받아서 사용했는데, 이를 헤제해주지 않아서 생겼던 누수였다.

node_t *nil = (node_t *) malloc(sizeof(node_t));

nil -> color = RBTREE_BLACK;
tree -> nil = tree -> root = nil;

또한 free 해주고 NULL을 넣어주는게 Dangling Pointer 방지를 위한 안전빵 이라는데(?)

void delete_all(rbtree *tree, node_t* node, node_t *nil){
    if(node -> left != nil){
        delete_all(tree, node -> left, nil);
    }

    if(node -> right != nil){
        delete_all(tree, node -> right, nil);
    }

    free(node);
    node = NULL;	===> 새로 추가한 부분
}