레드블랙 트리

1. 개요

- BST는 최악의 경우 삽입/삭제/탐색에 O(n)의 시간이 걸리는 단점이 있어 여러 균형 BST가 제시되었다. 예를 들어 AVL 트리의 경우 이를 구성하는 모든 노드의 좌우 서브트리 높이차가 1 이하가 되도록 해 이러한 BST의 단점을 극복했는데, AVL 트리의 경우 삽입/삭제 때마다 ‘회전 연산’을 수행해야 하고 이 회전 연산의 수행 횟수가 (선형시간은 아니지만) 꽤 있을 수 있다는 단점이 있다.

- 레드블랙 트리는 균형 BST의 하나로, AVL 트리와 유사하게 삽입/삭제 때마다 회전 연산 등의 연산을 하여 트리의 균형을 유지한다. 단, 여러 장치를 두어 회전 연산의 횟수가 최소화 될 수 있게 해 두었다. 따라서 평균적으로 레드블랙 트리가 AVL 트리보다 수행 시간이 적은 편이다.

2. 레드블랙 트리의 정의

1) 모든 노드는 블랙 또는 레드 컬러를 갖고, 루트, 외부노드는 블랙 컬러다.

2) 블랙 노드끼리는 서로 부모자식 관계일 수 있으나, 레드 노드끼리는 부모자식 관계일 수 없다.

- 즉, 어떤 노드가 레드 컬러라면 그 노드의 부모와 그 노드의 자식은 반드시 모두 블랙 컬러다.

3) 루트에서 외부노드로 이동하는 모든 경로에서, 블랙 노드의 개수는 모두 동일하다.

- 레드 노드끼리는 부모자식 관계일 수 없다고 했으므로, 루트에서 외부노드로 이동하는 경로 중 레드 노드가 최대로 많은 경로라 해도 그 경로의 레드 노드 수는 블랙 노드 수와 같다. 따라서 레드블랙 트리의 외부노드들의 최대 깊이 차이는 전체 트리 높이의 절반이다.

3. 레드블랙 트리의 탐색시간의 상한

- 레드블랙 트리의 노드 수 \(n\)인 어떤 레드블랙 트리가 있을 때, 이 레드블랙 트리가 갖는 루트에서 외부노드까지의 블랙 노드 수를 \(r\)이라고 하자. 그렇다면 이 레드블랙 트리의 탐색시간의 상한은 \(2r\)이 된다. 즉, \(r\)의 상한을 알 수 있다면 레드블랙 트리의 탐색시간의 상한을 알 수 있다.

- 여기서 잠시 거꾸로 생각해서, 어떤 레드블랙 트리의 \(r\)이 주어질 때 이 레드블랙 트리가 가질 수 있는 노드 수 \(n\)의 하한에 대해 생각할 수 있다. 만약 이 문제로부터 \(r\)과 \(n\) 사이의 부등식을 구할 수 있다면, 이 부등식은 곧 \(r\)의 상한에 대한 부등식도 되므로 이 문제에 대해 생각하는 것은 레드블랙 트리의 탐색시간의 상한을 구하는 데 있어 굉장히 중요한 일이 된다.

- 그런데 레드블랙 트리가 가질 수 있는 노드수 \(n\)의 하한은 쉽게 생각할 수 있다. 루트부터 깊이가 \(r\)인 노드까지 모두 노드로 빽빽히 채워진 포화이진트리가 바로 \(r\)이 주어지는 레드블랙 트리의 \(n\)의 하한이다. 그리고 이를 구하는 부등식은 \(r \leq log(n+1)\) 이다.

- 따라서 레드블랙 트리의 탐색시간의 상한은 \(2log(n+1)\)임을 알 수 있다. O 표기법으로 O(logn)으로 쓸 수 있다.

4. 레드블랙 트리의 삽입

1) 새로 삽입되는 노드(\(u\))의 위치는 일단 일반적인 BST의 삽입 위치와 동일하게 찾는다. 그리고 \(u\)의 컬러는 레드로 한다.

2) 이때 만약 \(u\)가 삽입된 위치의 부모노드(\(pu\))의 컬러 또한 레드라면, \(pu\)의 부모노드(\(gu\))의 \(pu\) 반대쪽 자식노드 (\(pu\)가 \(gu\)의 왼쪽 자식이면 \(gu_R\), 오른쪽 자식이면 \(gu_L\) ) 의 컬러에 따라 다음 연산을 선택적으로 수행한다.

(a) \(gu_R\) / \(gu_L\) 이 레드노드인 경우

- 이 경우 \(gu\)의 두 자식이 모두 레드노드다. 이 경우에는 각 노드들의 연결관계는 변경하지 않고, \(gu\)의 두 자식의 컬러를 블랙으로 \(gu\)의 컬러를 레드로 바꾼다.

- \(gu\)가 레드노드가 되었는데 만약 그 부모노드가 레드노드인 경우, 위 2)번으로 돌아가 다시 루프를 수행한다.

(b) \(gu_R\) / \(gu_L\) 이 블랙노드인 경우

- 레드블랙 트리라면 루트에서 외부노드까지 모든 경로의 블랙노드수가 모두 동일데, 이 경우에도 위 경우처럼 \(gu\)를 레드로 변경할 경우 몇몇 경로에서 블랙노드수가 감소되는 일이 일어나게 된다. 따라서 이 경우에는 컬러를 변경하지 않고, AVL 트리에서 한 것과 유사한 회전 연산을 수행한다.

- 구체적으로, \(u\), \(pu\), \(gu\) 세 노드 중 가운데 값을 갖는 노드를 부모노드로 나머지를 그 노드의 왼쪽/오른쪽 자식노드로 붙인 후 각 세 노드가 갖고 있던 서브트리들을 BST의 규칙에 맞게 재배치하는 것이 회전 연산의 핵심 개념이다.

- 이때 회전연산 후 새로 부모가 된 노드가 블랙 컬러고 나머지 노드가 레드 컬러를 갖게 한다. 이렇게 하면 더 이상 레드 노드끼리 연속돼서 부모-자식을 이루고 있는 경우가 더 이상 없어지므로, 이보다 더 상위 노드로 루프를 계속할 일 없이 삽입 연산이 여기서 바로 종료된다.

5. 레드블랙 트리의 삭제

- 일단 레드블랙 트리도 BST의 일종이므로, 일반적인 BST에서 노드를 삭제하는 경우와 마찬가지 방법으로 삭제 연산을 수행한다. 일반적인 BST에서 노드를 삭제할 때에는 그 노드를 삭제한 후 그 노드의 왼쪽 서브트리의 가장 큰 값 또는 오른쪽 서브트리의 가장 작은 값을 그 위치로 가져온다. (편의상 삭제되는 노드의 inorder successor인 오른쪽 서브트리의 가장 작은 값을 가져오는 경우를 기준으로 설명한다.) 레드블랙 트리의 삭제 또한 먼저 이 작업을 수행한다.

- 이때, (1)successor가 레드노드인 경우에는 이 노드를 기존 위치에서 삭제하더라도 아무 문제가 발생하지 않는다. (2)successor가 블랙노드인 경우에도, successor의 오른쪽 자식이 레드노드라면 successor를 삭제한 후 그 레드노드를 블랙노드로 바꾼 후 기존 successor의 위치에 붙이면 되므로 역시 아무 문제가 발생하지 않는다.

- 그러나 (3)successor가 블랙노드고 successor의 오른쪽 자식이 없다면, successor를 삭제했을 때 이로 인해 루트에서 외부노드까지의 경로 중 일부에서 블랙노드의 수가 감소되는 일이 발생한다. (successor의 부모노드에 블랙노드인 successor의 외부노드를 붙이게 되는데, 이때 붙는 외부노드가 레드노드였다면 블랙 컬러가 칠해지는 거였는데 이미 블랙노드인 외부노드가 붙어서 또 블랙을 칠하는 셈이 돼버렸다며 이를 double black이라 부른다.) 이 경우에는, successor의 형제노드(=successor(이하 \(u\))의 부모노드(이하 \(p\))의 오른쪽 자식노드(이하 \(s\)))의 컬러와 그 자식노드들의 컬러에 따라 처리 방법이 달라진다.

a) \(s\)가 레드노드인 경우

- \(p\)와 double black을 트리에서 떼어내고 \(s\)와 \(s\)의 오른쪽 서브트리를 \(p\) 위치에 붙인다. 그리고는 \(s\)의 왼쪽 자식으로 \(p\)와 double black을 붙인 후 \(s\)의 왼쪽 자식으로 있던 서브트리를 \(p\)의 오른쪽 자식으로 붙인다. 그리고는 \(s\)의 컬러를 블랙으로, \(p\)의 컬러를 레드로 바꾼다.

- 이렇게 해도 \(p\)의 왼쪽 자식에는 여전히 double black이 붙어있어 여전히 레드블랙 트리의 정의에 어긋난 상태가 유지된다. 다만 이 상황에선 double black 노드의 형제노드가 블랙노드가 되었으므로, 아래 세 케이스 중 어느 하나에 부합하는 케이스를 선택해 연산을 계속 수행할 수 있다.

b) \(s\)가 블랙노드이고, \(s\)의 자식노드들이 모두 블랙노드인 경우

- 이 경우 \(s\)를 레드노드로 바꾸고, \(p\)를 블랙노드로 바꾼다. \(p\)가 원래 레드노드였다면 여기서 종료하나, 원래도 블랙노드였다면 \(p\)를 double black으로 바꾼 후 위 a)부터 다시 루프를 수행한다. (루트가 double black이 되었다면 루프를 종료해도 된다.)

c) \(s\)가 블랙노드이고, \(s\)의 오른쪽 자식(\(r\))이 레드노드인 경우

- a) 케이스에서와 같이 \(p\)와 double black을 트리에서 떼어내고 \(s\)와 \(s\)의 오른쪽 서브트리를 \(p\) 위치에 붙인다. 그리고는 \(s\)의 왼쪽 자식으로 \(p\)와 double black을 붙인 후 \(s\)의 왼쪽 자식으로 있던 서브트리를 \(p\)의 오른쪽 자식으로 붙인다. 그리고는 \(p\)와 \(s\)의 컬러를 서로 맞바꾸고 \(r\)의 컬러를 블랙으로 바꾼다.

d) \(s\)가 블랙노드이고, \(s\)의 오른쪽 자식(\(r\))이 블랙노드, \(s\)의 왼쪽 자식(\(l\))이 레드노드인 경우

- \(s\)와 \(s\)의 오른쪽 서브트리를 떼어내고 \(l\)과 \(l\)의 왼쪽 서브트리를 \(s\) 위치에 붙인다. \(l\)의 오른쪽 자식으로는 \(s\)와 \(s\)의 오른쪽 서브트리를 붙이고, \(l\)의 오른쪽 자식으로 있던 서브트리를 \(s\)의 왼쪽 자식으로 붙인다. 그리고는 \(l\)의 컬러를 블랙으로, \(s\)의 컬러를 레드로 바꾼다.

- 이 상태는 위 c) 케이스를 적용하기 적합한 상태다. 이 다음으로 c) 케이스를 수행한다.