Red-Black Tree 구현

이번 장에서는 균형 이진 탐색 트리로 많이 사용되는 RB tree를 C언어로 구현해본다. 여기서 구현하는 ADT(Abstract Data Type)은 ordered set, multiset이다.

 

 

구현해야 하는 기능들은 CSLR 13장의 수도 코드를 구현하면 되는데, 구현해야 할 기능들은 다음과 같다.

 

• new_tree() : RB tree 구조체를 생성한다. 이때, 여러 개의 tree를 생성할 수 있어야하며, 각각 다른 내용들을 저장할 수 있어야한다.

Tree를 생성할 때는 여러 개의 tree를 생성할 수 있어야하며, 각각 다른 내용들을 저장할 수 있어야 한다. 이를 tree 구조체의 동적 할당이라고 한다. 또한 RB tree의 leaf 노드는 nil 노드라는 것으로 표시해야 하는데, nil 노드는 일종의 가상 노드로서, 트리에서 실제로는 존재하지 않는 노드이다. 따라서 일반 노드와는 다르게 key, parent, left, right 등의 필드는 nil 노드에서 의미를 가지지 않으며, 색깔은 항상 BLACK이다. 즉, nil 노드를 트리의 leaf 노드들에 대한 포인터로 간주하고, 키를 가지는 정상적인 노드들만을 트리의 내부 노드로 간주하면 된다. SENTINEL이라고 하며, 경계노드. 즉, 트리의 순회를 끝내는 기준점이 된다.

 

그렇다면 왜 nil 노드를 활용해야 할까? 우선 첫번째 이유는 효율적인 메모리 사용에 있다. 보통의 BST에서는 NULL leaf를 사용하여 leaf 노드를 표현하게 된다. 그러나 모든 leaf 노드가 하나의 NULL 값을 가지게되면, 메모리 공간이 낭비된다. 그래서 nil 노드를 사용하여 leaf 노드를 표현하면 모든 leaf 노드가 하나의 nil 노드를 가리키게 되어 메모리 공간을 절약할 수 있게 된다. 이와더불어 nil 노드를 사용하게 되면 leaf 노드를 구별하는데 활용될 수 있으므로, 노드 탐색 작업이 단순화된다.

 

 

• delete_tree(tree) : RB tree 구조체가 차지했던 메모리를 반환한다. 이때, 해당 tree가 사용했던 메모리를 전부 반환해야 한다. 즉, valgrind로 나타나지 않아야 한다.

tree를 삭제한다는 것은 결국 각 노드의 메모리를 반환한다는 의미이다. 즉, 루트 노드부터 시작해서 각 노드의 자식 노드를 순회하면서 모든 노드의 메모리를 반환하는 작업을 해주는 것인데, 노드의 자식 노드가 nil 노드가 아니면 해당 자식 노드를 루트로 하여 재귀적으로 함수를 호출하면 된다. 그리고 모든 노드가 삭제되면, nil 노드와 tree 구조체의 메모리를 반환하면 된다.

---

여기서 valgrind란 메모리 누수를 탐지하는 리눅스용 디버깅 툴이다. 사용법은 'valgrind 실행파일'을 해주면 된다. 좀 더 자세히 설치부터 살펴보면 다음과 같이 정리할 수 있다. 이때, 메모리 누수 검증에는 valgrind가 제공하는 memory cheacker인 memchecker를 이용하고, 스레드 체크에는 valgrind가 제공하는 thread checker인 DRD를 이용한다.

# valrind 설치
$ sudo apt install valgrind

# valgrind 실행 - 메모리 누수 검증
$ valgrind --leak-check=full --show-reachable=yes --track-origins=yes --verbose --log-file=valgrind-out.txt ./executable exampleParam1

# valgrind 실행 - 스레드 체크
$ valgrind --tool=drd --verbose ./executable exampleParam1

• --leak-check=full : 프로그램의 어떤 함수에서 누수가 발생하는지 확인할 수 있다.
• 이때, gcc로 컴파일할 때 -g 옵션을 주게되면 어떤 파일의 몇번째 줄에서 문제가 발생했는지 볼 수 있는데, 왜냐하면 이 옵션 적용시에는 디버거에 제공하는 디버깅 정보(변수 타입, 전역 심볼명, 주소, 소스 라인정보 등)을 바이너리에 삽입해주기 때문이다.
• --track-origins=yes : 초기화되지 않는 value들을 추적해준다. 즉, 메모리 error에 유용한데, valgrind가 너무 느리면 이 옵션은 꺼주자.
• --verbose : verbosity 모드로 프로그램에 대한 비정상적인 동작도 report해준다.
• --log-file : 로그 파일을 작성한다.

---

 

 

• tree_insert(tree, key) : key를 추가한다. 이때, 여기서 구현하는 ADT가 multiset이므로 이미 같은 key의 값이 존재해도 하나 더 추가한다.

key를 추가한다는 것은 우선 새 노드(RED)를 생성해서 새 노드를 삽입할 위치를 탐색하여 검증 후 삽입하는 것이다. 즉, 새 노드를 동적으로 생성하여 노드의 key를 입력받고, 색깔을 RED로 지정해주고, 자식 노드들은 nil 노드로 설정해준다. 그리고 루트 노드부터 탐색을 시작하여 탐색중인 노드보다 key 값이 작은 경우에는 왼쪽 자식으로 이동하고, 큰 경우에는 오른쪽 자식으로 이동한다. 만약 탐색중인 노드의 자식 노드가 nil 노드인 경우에는 새 노드를 해당 자식 노드로 추가하고 반복문을 종료한다. 그리고 반복문 종료후에 새 노드의 부모를 지정한다. 하지만 이렇게 노드 삽입후에는 삽입으로 불균형이 발생한다. 즉, 새로 삽입된 노드는 항상 RED 색상으로 삽입되는데, 새로 삽입된 노드의 부모 노드가 RED인 경우에는 RB tree의 규칙을 위반하게 되어 불균형이 발생한다. 따라서 이 불균형을 해결하기 위해 총 3가지 case로 나누서 처리한다.

1. 삼촌 노드가 RED인 경우
2. 삼촌 노드가 BLACK이고, 부모 노드와 새 노드가 Left/Right 자식인 경우
3. 삼촌 노드가 BLACK이고, 부모 노드가 Left/Right 자식, 새 노드가 Right/Left 자식인 경우

 

 

 

 

• tree_find(tree, key) : RB tree 내에 해당하는 key가 있는지 탐색하여 해당 node pointer를 반환한다. 물론 해당하는 node가 없으면 NULL을 반환한다.

 

• tree_erase(tree, ptr) : RB tree 내부의 ptr로 지정된 node를 삭제하고 메모리를 반환한다.

노드를 삭제할 때는 삭제할 노드를 대체할 노드를 찾는 것이 key point이다. 즉, 삭제할 키를 가진 노드를 삭제하면 해당 노드가 삭제되고, 삭제된 자리에 다른 노드가 채워지게 된다. 이때 삭제할 노드의 delete의 양쪽 자식 노드가 모두 존재하는 경우, 삭제할 노드의 오른쪽 서브트리에서 가장 작은 노드인 successor(후계자) 노드가 제거된다. 그리고 후계자 노드의 자식 노드가 이 없어지는 자리를 대체한다. (후계자 노드는 항상 왼쪽 자식이 없으므로, 오른쪽 자식 노드 하나만 존재한다. 반면에 삭제할 노드의 자식 노드가 없거나 하나만 있는 경우에는 삭제할 노드를 제거하고, 그 자식 노드가 기존 자리를 대체한다. 만약에 자식이 존재하지 않으면 nil 노드가 대체한다.

여기서 successor란 오른쪽 자식이 있으면 오른쪽 자식중에서의 가장 작은 값이다.

case4

 

case4의 경우, doubly black의 형제가 black 그 형제의 같은 방향의 자녀가 red일 때, 형제는 부모의 색으로, 형제의 같은 방향 자녀는 black으로, 부모는 black으로 바꾼 후에 부모를 기준으로 반대 방향으로 회전하면 해결된다.

case3

case3의 경우, doubly black의 형제가 black이고, 그 형제의 왼쪽 자녀가 red이고, 그 형제의 오른쪽 자녀가 black일 때는 doubly black의 형제의 오른쪽 자녀를 red가 되게 만들어서 이후에 case4를 적용하여 해결한다.

 

case2

case2의 경우, doubly black의 형제가 black이고, 그 형제의 두 자녀가 모두 black일 때, doubly black과 그 형제의 black을 모아서 부모에게 전달해서 부모가 extra black을 해결하도록 위임한다.

 

case1

case1의 경우, doubly black의 형제가 red일 때, 부모와 형제의 색을 바꾸고, 부모를 기준으로 회전한 뒤에 doubly black을 기준으로 case 2, 3, 4 중에 하나로 해결한다.

 

즉, 정리하면 삭제되는 색이 black일 때, 삭제되는 색이 있던 위치를 대체한 노드에 extra black을 부여한다. 그리고 대체한 노드가 red-and-black이 됐다면 black으로 바꿔주면 된다. 그 후 대체한 노드가 doubly black이 됐다면 case 1, 2, 3, 4 중에 하나로 해결해야 한다.

 

그럼 삭제되는 과정을 예시를 들어 정리해보면 다음과 같이 정리할 수 있겠다.

• tree_min(tree) : RB tree 중 최소값을 가진 node pointer를 반환한다.

 

• tree_max(tree) : 최대값을 가진 node pointer를 반환한다.

 

• tree_to_array(tree, array, n) : RB tree 내용을 key 순서대로 array로 변환한다. 여기서 array의 크기는 n으로 주어지며, tree의 크기가 n보다 큰 경우에는 순서대로 n까지만 변환한다. 즉, array의 메모리 공간은 이 함수를 부르는 쪽에서 준비하고, 크기를 알려준다.