RB tree
28 Oct 2017 | Binary Search Tree
이번 글에서는 Red-Black(RB) 트리에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concepts
RB 트리는 다음 다섯 가지 속성을 만족하는 이진탐색트리(Binary Search Tree)의 일종입니다.
- 모든 노드는 빨간색, 검은색 둘 중 하나다.
- 루트노드는 검은색이다.
- 모든 잎새노드(NIL)는 검은색이다.
- 어떤 노드가 빨간색이라면 두 개 자식노드는 모두 검은색이다. (따라서 빨간색 노드가 같은 경로상에 연이어 등장하지 않는다)
- ‘각 노드~자손 잎새노드 사이의 모든 경로’에 대해 검은색 노드의 수가 같다.
RB 트리의 예는 다음 그림과 같습니다. 위 다섯가지 속성을 만족하고 있음을 확인할 수 있습니다.
노드의 높이 $h$는 해당 노드로부터 잎새노드에 이르는 가장 긴 경로의 엣지 수를 가리킵니다. 임의의 노드 $x$의 Black-height는 $x$부터 잎새노드에 이르는 경로상에 있는 검은색 노드의 수로 $bh(x)$라고 표기합니다. $x$가 검은색 노드일 경우 1을 빼주며 잎새노드(NIL)의 $bh$는 0입니다. $h$와 $bh$를 계산하는 예시는 다음과 같습니다.
insert
RB 트리의 삽입연산은 이진탐색트리의 삽입과 동일합니다. 그런데 삽입 후에도 RB 트리 다섯 가지 속성을 유지하고 있어야 합니다. 이 속성을 유지하기 위해 몇 가지 작업을 수행해 줍니다. (이진탐색트리의 연산을 기본으로 하되 이후 추가 작업을 수행해준다는 점에서 AVL 트리와 유사합니다)
삽입할 새 요소 $z$는 빨간색으로 둡니다. $z$와 검정색 부모노드를 공유하는 형제노드(sibling node)를 $y$라고 두겠습니다.
case1
(case 1-1) $y$가 빨간색이면서 $z$가 left child인 경우입니다. 아래 그림에서 $z$가 삽입되면서 빨간색 노드가 연이어 등장하게 됐습니다. RB 트리의 네 번째 속성에 위배된다는 이야기죠. 이 경우 노드의 색을 바꿔서 다시 칠해 줍니다.
(case 1-2) $y$가 빨간색이면서 $z$가 right child인 경우에도 색을 바꿔서 다시 칠해 줍니다.
case2, case3
(case2) $y$가 검은색이면서 $z$가 right child인 경우에도 빨간색 노드가 연이어 등장해 RB 트리의 네 번째 속성에 위배됩니다. case2인 경우 double rotation을 수행해 줍니다.
(case3) $y$가 검은색이면서 $z$가 left child인 경우에는 single rotation을 수행해 줍니다. single rotation과 double rotation 관련 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.
정리
시나리오별 rotation 수행은 다음과 같이 합니다. 삽입된 노드가 꺾여 있는 형태면 일단 rotation을 한 번 수행해 이것을 펴주고, 펴진 형태의 노드에 대해 rotation을 한 번 더 수행합니다. 이미 펴져 있는 형태로 노드가 삽입된 경우라면 rotation을 한 번만 수행합니다.
insert example
다음 숫자들을 차례대로 RB 트리에 삽입해 보겠습니다.
10, 85, 15, 70, 20, 60, 30, 50
삽입되는 새 노드의 색깔은 빨간색입니다. 그런데 10은 루트노드이므로 RB 트리의 1번 속성을 맞추기 위해 검정색으로 바꿔 줍니다. 다음과 같습니다.
85, 15를 삽입합니다. 그런데 빨간색 노드가 연이어 등장해 RB 트리의 4번 속성을 위반했네요. 그런데 새로 삽입된 15와 검은색 부모노드를 공유하는 형제노드(그림에는 안그려져 있지만 10의 왼쪽 자식노드는 검은색 NIL 노드입니다)가 검은색이고, 빨간색 두 노드가 꺾여져 있는 형태이므로 double rotation을 수행해 줍니다.
70을 삽입합니다. 빨간색 노드가 연이어 등장했습니다. 그런데 70과 검정색 부모를 공유하는 형제노드 10이 빨간색입니다. case1에 해당하므로 색을 15와 70은 빨간색, 10과 85는 검정색으로 다시 칠해 줍니다. 그런데 15는 루트노드이므로 검정색으로 그대로 놔둡니다.
20을 삽입합니다. 빨간색 노드가 연이어 등장했습니다. 그런데 20과 검정색 부모를 공유하는 형제노드 NIL(85의 right child)이 검정색입니다. 새로 삽입된 20이 노드 모양이 펴져 있는 형태이므로 case3에 해당하며 single rotation을 수행해 줍니다.
60을 삽입합니다. 빨간색 노드가 연이어 등장했습니다. 그런데 60과 검정색 부모를 공유하는 형제노드 85의 색이 빨간색입니다. case1에 해당하므로 70과 60의 색을 빨간색으로, 20과 85의 색을 검정색으로 다시 칠해 줍니다.
30을 삽입합니다. 빨간색 노드가 연이어 등장했습니다. 그런데 30과 검정색 부모를 공유하는 형제노드 NIL(20의 left child)이 검정색입니다. 그리고 꺾여 있는 형태로 case2에 해당합니다. double rotation을 수행합니다.
50을 삽입합니다. 빨간색 노드가 연이어 등장했습니다. 이번엔 조금 복잡하므로 차례대로 살펴보겠습니다.
- 50과 검정색 부모를 공유하는 형제노드 20이 빨간색입니다. case1에 해당합니다. 30과 50을 빨간색, 20과 60을 검정색으로 칠해 둡니다.
- 70, 30을 보니 빨간색 노드가 연이어 등장했습니다. 그런데 30과 검정색 부모를 공유하는 형제노드 10이 검정색입니다. 아울러 15, 70, 30이 꺾여져 있는 형태이므로 case2에 해당합니다. double rotaion을 수행해 줍니다.
delete
RB 트리에서 검정색 노드를 삭제할 때는 삭제 연산으로 RB 트리의 속성이 깨지지 않도록 해야 합니다. 이는 삽입 연산 때 고려했던 것과 유사한 방식으로 rotation을 구현함으로써 해결할 수 있습니다. 다만 빨간색 노드를 삭제할 때는 그냥 삭제를 수행하면 된다고 합니다.
계산복잡성
RB 트리 전체 높이를 $h$라고 할 때 삽입, 삭제, 검색 등 RB 트리의 계산복잡성은 $O(h)$입니다. 그런데 RB 트리의 노드 수가 $n$개라면 높이 상한은 $2\log{n+1}$이라고 합니다. 따라서 RB 트리의 계산복잡성은 $O(\log{n})$이 됩니다.
이번 글에서는 Red-Black(RB) 트리에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concepts
RB 트리는 다음 다섯 가지 속성을 만족하는 이진탐색트리(Binary Search Tree)의 일종입니다.
- 모든 노드는 빨간색, 검은색 둘 중 하나다.
- 루트노드는 검은색이다.
- 모든 잎새노드(NIL)는 검은색이다.
- 어떤 노드가 빨간색이라면 두 개 자식노드는 모두 검은색이다. (따라서 빨간색 노드가 같은 경로상에 연이어 등장하지 않는다)
- ‘각 노드~자손 잎새노드 사이의 모든 경로’에 대해 검은색 노드의 수가 같다.
RB 트리의 예는 다음 그림과 같습니다. 위 다섯가지 속성을 만족하고 있음을 확인할 수 있습니다.
노드의 높이 $h$는 해당 노드로부터 잎새노드에 이르는 가장 긴 경로의 엣지 수를 가리킵니다. 임의의 노드 $x$의 Black-height는 $x$부터 잎새노드에 이르는 경로상에 있는 검은색 노드의 수로 $bh(x)$라고 표기합니다. $x$가 검은색 노드일 경우 1을 빼주며 잎새노드(NIL)의 $bh$는 0입니다. $h$와 $bh$를 계산하는 예시는 다음과 같습니다.
insert
RB 트리의 삽입연산은 이진탐색트리의 삽입과 동일합니다. 그런데 삽입 후에도 RB 트리 다섯 가지 속성을 유지하고 있어야 합니다. 이 속성을 유지하기 위해 몇 가지 작업을 수행해 줍니다. (이진탐색트리의 연산을 기본으로 하되 이후 추가 작업을 수행해준다는 점에서 AVL 트리와 유사합니다)
삽입할 새 요소 $z$는 빨간색으로 둡니다. $z$와 검정색 부모노드를 공유하는 형제노드(sibling node)를 $y$라고 두겠습니다.
case1
(case 1-1) $y$가 빨간색이면서 $z$가 left child인 경우입니다. 아래 그림에서 $z$가 삽입되면서 빨간색 노드가 연이어 등장하게 됐습니다. RB 트리의 네 번째 속성에 위배된다는 이야기죠. 이 경우 노드의 색을 바꿔서 다시 칠해 줍니다.
(case 1-2) $y$가 빨간색이면서 $z$가 right child인 경우에도 색을 바꿔서 다시 칠해 줍니다.
case2, case3
(case2) $y$가 검은색이면서 $z$가 right child인 경우에도 빨간색 노드가 연이어 등장해 RB 트리의 네 번째 속성에 위배됩니다. case2인 경우 double rotation을 수행해 줍니다.
(case3) $y$가 검은색이면서 $z$가 left child인 경우에는 single rotation을 수행해 줍니다. single rotation과 double rotation 관련 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.
정리
시나리오별 rotation 수행은 다음과 같이 합니다. 삽입된 노드가 꺾여 있는 형태면 일단 rotation을 한 번 수행해 이것을 펴주고, 펴진 형태의 노드에 대해 rotation을 한 번 더 수행합니다. 이미 펴져 있는 형태로 노드가 삽입된 경우라면 rotation을 한 번만 수행합니다.
insert example
다음 숫자들을 차례대로 RB 트리에 삽입해 보겠습니다.
10, 85, 15, 70, 20, 60, 30, 50
삽입되는 새 노드의 색깔은 빨간색입니다. 그런데 10은 루트노드이므로 RB 트리의 1번 속성을 맞추기 위해 검정색으로 바꿔 줍니다. 다음과 같습니다.
85, 15를 삽입합니다. 그런데 빨간색 노드가 연이어 등장해 RB 트리의 4번 속성을 위반했네요. 그런데 새로 삽입된 15와 검은색 부모노드를 공유하는 형제노드(그림에는 안그려져 있지만 10의 왼쪽 자식노드는 검은색 NIL 노드입니다)가 검은색이고, 빨간색 두 노드가 꺾여져 있는 형태이므로 double rotation을 수행해 줍니다.
70을 삽입합니다. 빨간색 노드가 연이어 등장했습니다. 그런데 70과 검정색 부모를 공유하는 형제노드 10이 빨간색입니다. case1에 해당하므로 색을 15와 70은 빨간색, 10과 85는 검정색으로 다시 칠해 줍니다. 그런데 15는 루트노드이므로 검정색으로 그대로 놔둡니다.
20을 삽입합니다. 빨간색 노드가 연이어 등장했습니다. 그런데 20과 검정색 부모를 공유하는 형제노드 NIL(85의 right child)이 검정색입니다. 새로 삽입된 20이 노드 모양이 펴져 있는 형태이므로 case3에 해당하며 single rotation을 수행해 줍니다.
60을 삽입합니다. 빨간색 노드가 연이어 등장했습니다. 그런데 60과 검정색 부모를 공유하는 형제노드 85의 색이 빨간색입니다. case1에 해당하므로 70과 60의 색을 빨간색으로, 20과 85의 색을 검정색으로 다시 칠해 줍니다.
30을 삽입합니다. 빨간색 노드가 연이어 등장했습니다. 그런데 30과 검정색 부모를 공유하는 형제노드 NIL(20의 left child)이 검정색입니다. 그리고 꺾여 있는 형태로 case2에 해당합니다. double rotation을 수행합니다.
50을 삽입합니다. 빨간색 노드가 연이어 등장했습니다. 이번엔 조금 복잡하므로 차례대로 살펴보겠습니다.
- 50과 검정색 부모를 공유하는 형제노드 20이 빨간색입니다. case1에 해당합니다. 30과 50을 빨간색, 20과 60을 검정색으로 칠해 둡니다.
- 70, 30을 보니 빨간색 노드가 연이어 등장했습니다. 그런데 30과 검정색 부모를 공유하는 형제노드 10이 검정색입니다. 아울러 15, 70, 30이 꺾여져 있는 형태이므로 case2에 해당합니다. double rotaion을 수행해 줍니다.
delete
RB 트리에서 검정색 노드를 삭제할 때는 삭제 연산으로 RB 트리의 속성이 깨지지 않도록 해야 합니다. 이는 삽입 연산 때 고려했던 것과 유사한 방식으로 rotation을 구현함으로써 해결할 수 있습니다. 다만 빨간색 노드를 삭제할 때는 그냥 삭제를 수행하면 된다고 합니다.
계산복잡성
RB 트리 전체 높이를 $h$라고 할 때 삽입, 삭제, 검색 등 RB 트리의 계산복잡성은 $O(h)$입니다. 그런데 RB 트리의 노드 수가 $n$개라면 높이 상한은 $2\log{n+1}$이라고 합니다. 따라서 RB 트리의 계산복잡성은 $O(\log{n})$이 됩니다.
Comments