Red-Black Tree

Red-Black Tree는 이진 탐색 트리의 한 종류로서, 스스로 균형을 잡는 트리를 의미한다. 즉, 이진 탐색 트리의 worst case의 단점을 개선하였으며, 모든 노드는 red 혹은 black이라는 특징을 가지고 있다.

 

또한 RB tree는 nil 노드라는 독특한 특징을 가지고있다. 이는 존재하지 않음을 의미하는 노드로, 자녀가 없을 때 자녀를 nil 노드로 표기한다. 그럼에도 불구하고 값이 있는 노드와 동등하게 취급을 해주기 때문에, RB tree에서 leaf 노드는 nil 노드인 것이다.

 

RB Tree의 특성에는 다음과 같은 규칙이 있다.

1. 모든 노드는 RED or BLACK이다.
2. 루트 노드는 BLACK이다.
3. 모든 NIL 노드는 BLACK이다.
4. 노드가 RED이면, 그 노드의 자녀는 BLACK이다. 즉, RED는 연속적으로 존재할 수 없다.
5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black의 수는 같다. 단, 자기 자신은 카운트하지 않는다.

 

5번에서 노드 x의 black height라는 개념이 나오는데, 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black수를 의미한다.

또한 다음과 같이 RB tree가 5번 속성을 만족하고 있고, 두 자녀가 같은 색을 가질 때, 부모와 두 자녀의 색을 바꿔줘도 5번 속성은 여전히 만족한다.

 

그리고 RB 트리는 삽입 혹은 삭제시 2, 4, 5번 속성을 위반하는데, 이들을 해결하기 위해서 구조를 바꾸다보면 자연스럽게 균형이 잡히게 된다.

 

Red-Black Tree의 기본적인 삽입, 삭제 방식은 BST와 동일하다.

 

RB tree는 어떻게 균형을 잡는가?

삽입/삭제 시 주로 4, 5번 규칙을 위반하며, 이들을 해결하려고 구조를 바꾸다 보면 자연스럽게 트리의 균형이 잡히게 된다.

 

삽입

삽입 방식은 일반적인 이진 탐색 트리와 동일하다. 이때, 삽입 노드의 색깔은 항상 RED이다. 왜냐하면, 삽입후에도 #5 속성을 만족하기 위해서이다. 그리고 삽입 후 RB 속성 위반 여부를 확인하는데, 만약 RB 트리 속성을 위반했다면 재조정한다. (insert-fixup). 여기서 중요한 개념이 회전인데, 구조를 바꾸면서도 이진 탐색 트리의 특징을 유지시키는 방법이 이 회전이다. 그러면 다시 RB 트리 속성을 만족하게 된다.

그리고 위에서 말했던 insert-fixup. 즉, 삽입 후에 속성위반시에 재조정 과정은 다음과 같은 알고리즘을 수행해서 속성 위반을 해결할 수 있다.

 

case3

case3의 경우, 삽입된 red 노드가 부모의 왼쪽 자녀이고, 할아버지의 왼쪽 자녀인 부모도 red이고, 삼촌은 black이라면, 부모와 할아버지의 색을 바꾼 후에 할아버지 기준으로 오른쪽으로 회전한다.

 

case2

case2의 경우, 삽입된 red 노드가 부모의 오른쪽 자녀이고, 할아버지의 왼쪽 자녀인 부모도 red이고, 삼촌은 black이라면, 부모를 기준으로 왼쪽으로 회전한 뒤에 case3방식으로 해결한다.

 

case1

삽입된 red 노드의 부모도 red이고, 삼촌도 red이면, 부모와 삼촌을 black으로 바꾸고, 할아버지를 red로 바꾼 뒤 할아버지에서 다시 확인을 시작한다.

 

그럼 위 개념을 바탕으로 삽입 예제를 한번 살펴보자.

 

while 부모가 RED이면 {
	if 부모,삼촌 == RED이면,
    	부모,삼촌 모두 BLACK으로 바꾸고, 할아버지를 RED로 변경한다.
        그리고 할아버지에서 다시 시작한다.
    
    else { // 삼촌 == BLACK이면
    	if 할아버지, 부모, 자신이 꺽인상태이면,
        	회전해서 부모,자신을 펴준다.
        
        // 할아버지, 부모, 자신이 펴진상태이면,
        부모, 할아버지 서로 색을 바꾼다.
        그리고 할아버지를 기준으로 회전한다.
    }
}

종료전에 루트를 BLACK으로 변경한다.

 

삭제

삭제도 방식은 일반적인 BST와 동일한데, 삭제 후 RB트리 속성 위반 여부를 확인하고, RB 트리 속성을 위반했다면 재조정해주면 된다. (delete-fixup). 그러면 RB 트리 속성을 다시 만족하게 된다.

 

그리고 삭제될 색을 결정하는 법은 다음과 같이 나눠서 생각해볼 수 있다.

• 삭제 노드의 자녀가 없거나 한개이면, 삭제되는 색은 삭제되는 노드의 색이다.
• 삭제 노드의 자녀가 둘 다 있으면, 삭제되는 색은 삭제되는 노드의 successor의 색이다.

 

그러면 이번에 delete-fixup. 즉, 삭제시 속성 위반했을 때 재조정해주는 방법을 살펴보자. 우선 두 가지 케이스로 나눌 수 있는데, 삭제색이 RED이면 어떠한 속성도 위반하지 않는다. 그런데 삭제색이 BLACK이면 #2, #4, #5 속성을 위반할 수 있다. 왜냐하면, 블랙이 지워지면 블랙 높이가 -1이 되어서 5번 속성이 깨질 수 있기 때문이다. 그래서 해당 위치에서 5번 조건을 만족시키도록 조정해야 하는 것이다.

// 삭제색이 BLACK이면
while (타겟이 루트가 아니고 && 타켓이 BLACK)이면 {
	if 형제의 색이 RED이면 {
    	형제, 부모 서로 색을 바꾸고, 타켓이 내려가도록 부모 기준으로 회전한다.
    }
    
    if 형제의 색이 BLACK이고, 형제의 자식 둘다 BLACK이면 {
    	형제, 자신의 BLACK을 부모로 올려서 형제를 RED로 변경하고, 부모에서 다시 fixup한다.
    }
    
    else {
    	if 형제의 색이 BLACK이고, 형제의 꺽인 자식이 RED이면,
        	자식 RED와 형제 서로 색을 바꾸고, RED가 바깥쪽으로 오도록 펴지게 회전한다.
        
        부모와 형제 서로 색을 바꾸고, 형제(펴진 자식)의 색을 BLACK으로 바꾼다.
        그리고 타켓이 내려가도록 부모기준 회전하여 타켓을 루트로 설정한다. -> while 종료
    }
}

종료전에 타켓을 BLACK으로 변경한다.

 

 

RB tree와 AVL tree 비교

일단 둘 다 이진 탐색 트리이다. 그리고 삽입/ 삭제/ 검색 시간복잡도 측면에서 worst case에서도 O(logN)이라는 공통점을 가지고 있다. 하지만 삽입/ 삭제 성능에서 RB tree가 AVL 트리에 더 빠르고, 검색 성능에서 AVL tree가 더 빠른 성능을 가진다. 왜냐하면 AVL tree는 균형을 엄격하게 지키기 때문에 삽입/삭제에서 느리지만, 검색 성능에서는 더 빠른 측면을 가지고 있다. 이렇게 균형을 잡는 방식은 RB tree의 경우에는 RB Tree는 트리 속성을 만족시키도록 균형을 잡고, AVL 트리는 balance factor가 -1, 0 ,1 이 되도록 한다. 마지막으로 응용 사례를 살펴보면 RB tree의 경우에는 linux kernel 내부에서도 사용되고, Java TreeMap이나 TreeSet 구현 등에서 사용된다. 반면에 AVL tree는 그 특성으로 인해 한번 만들어 놓으면 삽입/ 삭제가 거의 없고, 검색이 대부분인 상황에서 사용된다. 그래서 그 대표적인 사례가에는 dictionary가 있다.