이진트리 중 Binary Search Tree인 경우에는 한쪽에만 노드들이 치우쳐 있어 균형잡힌 트리가 만들어지지 않을 수 있다. 그렇다면 탐색을 하기 위한 시간이 늘어나게 되는 단점이 있는데, 이를 보완하여 균형잡힌 트리를 만들고자 만들어진 자료구조가 Red-Black Tree라는 것이다.
Red-Black Tree는 각 노드의 색깔을 red, black 중에 선택하여, 주어진 조건을 만족시켰을 때 성립하는 Tree이다.
Red-Black Tree의 성립조건은 다음과 같다.
- 루트 노드는 언제나 Black이다.
- Leaf 노드 (말단 노드) 또한 언제나 Black이다.
- 만약 노드가 Red라면, 그 노드의 자식들은 언제나 Black이다. 즉, red node가 연속으로 올 수 없다.
- 루트에서 말단 노드까지의 Black node의 개수는 언제나 동일하다.
위 그림이 Red-Black tree의 예시라고 할 수 있다. 여기서 NIL은 말단 노드를 뜻하고 위의 그림을 보면 red black tree의 property를 모두 만족시켰다는 것을 잘 알 수 있다. 그러면 이제 Red-Black Tree에서의 검색, 삽입, 삭제를 어떻게 구현하는지 살펴보자.
1. 검색
Red-Black Tree에서의 검색은 일반 Binary Search Tree에서의 검색과 동일하다. 만약 parent node보다 찾으려는 숫자가 작다면 왼쪽 child node로 이동해주고, 숫자가 크다면 오른쪽 child node로 이동해주면 된다.
검색의 경우는 Red-Black Property가 존재한다고 해서 달라지는 부분이 없기 때문에 삽입과 삭제에 집중해보자.
2. 삽입 (Insertion)
먼저 노드를 삽입하려고 하면 그 노드의 색깔을 정해주어야 한다. 우리는 Red-Black Tree에서 삽입할 노드는 무조건 Red라고 가정하고 시작한다.
여기서 아무 문제없이 삽입이 잘 되는 경우는 삽입하려고 하는 노드의 부모 노드의 색깔이 black일 경우이다. 왜냐하면 Red-Black property 3번에 의해 Red 위에 Red가 나올 수 없기 때문에 Red 위의 부모 노드가 Black일 경우에는 아무런 추가 조치 없이 삽입이 가능해진다.
즉 위와 같은 그림에서는 전혀 문제가 되지 않는다. 여기서 하얀색으로 표현한 것은 상황에 따라 Red/Black이 되는 경우인데 Red/Black으로 칠해진 노드만 집중해서 보기 위해서 다른 노드는 하얀색으로 표현해놓았다.
하지만 문제가 되는 경우는 삽입하려는 부모의 노드가 빨간색일 경우이다.
위 그림처럼 Red node가 연속으로 오게 된다면 Red-Black Property 3번을 충족시키지 못한다. 따라서 이 경우에는 추가적인 조치가 필요하다.
이를 위해 우리는 경우를 몇 가지로 나누어볼 수 있다.
위와 같은 기본 구조에서 p와 대칭점에 있는 노드를 우리는 s라고 부를 것이다. sibiling, 형제노드의 약자이다. s 노드가 Red냐 Black이냐에 따라서 삽입의 조정 방법이 달라진다.
-
s가 Red일 경우
먼저 s가 Red일 경우부터 살펴보겠다.
위 그림처럼 생각해볼 수 있는데 이 경우에는 아래처럼 바꾸어주면 된다.
즉 p와 s 노드를 둘 다 Black으로 바꾸어 주고 P의 parent node를 red로 바꾸어주는 것이다. 하지만 만약 p^2의 parent node 또한 red 였다면 추가적으로 문제가 생긴다. 이 경우에는 p^2 노드를 recursive하게 하여 추가적인 조정을 해주어야 한다.
-
다음으로 만약 s 노드는 Black이고 추가하려는 x 노드가 p의 left child일 경우를 살펴보자
즉, 위와 같은 경우라고 볼 수 있다. 이런 경우에는 아래의 그림처럼 조정해주면 된다.
즉 p 노드를 중심으로 right rotate를 시키고 p 노드의 색깔을 red 에서 black으로 바꾸어주면 되는 것이다.
-
마지막으로 s 노드가 black이면서 x는 p의 right child인 경우를 살펴보자
위 그림과 같은 경우를 의미한다. 이 경우에는 아래와 같이 변경해주면 된다.
하지만 이런 식으로 변경해도 x과 p가 연속적으로 red가 나타났기 때문에 문제가 된다. 하지만 이 경우는 위에서 s 노드가 black이고 새로운 노드가 left child 인 경우에 해당되기 때문에 두번째 경우로 이동해서 추가적으로 처리해주면 된다.
3. 삭제
다음으로는 조금 더 까다로운 Red-Black Tree에서의 삭제를 알아보겠다.
만약 삭제하려는 노드가 Red면 그 노드만 삭제해주면 되고, Black이더라도 child node가 Red라면 해당 노드를 삭제해주고 child의 색깔을 Black으로 바꿔주면 아무 문제가 없다.
문제가 되는 경우는 삭제하려는 노드와 그 자식 노드의 색깔이 모두 다 Black일 경우이다. 왜냐하면 Red-Black tree property 4번에 의해 leaf 노드까지의 black node의 개수는 모두 일정해야 하기 때문이다. 하지만 Black 노드를 하나 삭제해 버린다면 그러한 property가 깨지기 때문에 문제가 생기는 것이다. 그래서 삭제의 경우에도 몇 가지 경우를 나누어보겠다.
아래 그림에서 x 노드는 Black인 노드 m을 삭제하고 난 이후의 child node를 의미하게 된다. 하지만 Black node의 개수가 하나 모자라기 때문에 옆에 -1로 표시하겠다.
Case 1.
삭제한 이후의 검정색 노드가 하나 모자라는 노드를 x로 표시했을 때 위와 같은 그림이 case 1이다. s 는 Black이고 s의 left child와 right child 노드가 모두 Black인 경우다. 이 경우는 가장 간단한 경우로 아래와 같이 조정해주면 된다.
위와 같이 조정해주면 p 노드가 Black으로 바뀌면서 x 노드까지의 경로에 모자랐던 black 노드의 개수를 하나 늘려줌으로써 문제가 해결된다.
case 2.
case1과 유사하지만 이번에는 p 노드까지 모두 다 Black이다.
이번에도 s 노드를 Red로 바꾸어주지만 Black 노드가 하나 부족한 것이 p node로 전이되었다고 할 수 있다. 그러므로 여기서는 p 노드를 문제 노드로 놓고 재귀적으로 또 문제를 해결해주어야 한다.
case 3.
s 노드는 black이고 r node가 red인 경우를 뜻한다. 여기서도 마찬가지로 하얀색 노드는 red/black이 와도 괜찮다는 뜻이며 red/black 각각의 경우에 대해 대입해보면 된다. 여기서는 묶어서 한 가지 상황으로 처리한 것이다. 이 경우에는 아래의 그림과 같이 left rotate를 시켜주면 된다.
여기서 하얀색 노드는 이전의 색깔을 그대로 따라간다는 의미이다.
case 4.
이번에는 위와 반대로 r이 Black이고 L이 red인 경우이다. 이 경우에는 아래와 같이 rotate를 시켜준다. (s를 기준으로 하고 rotate를 시켜주는 것임)
하지만 위와 같이 변경하여도 x에 여전히 -1이 있는 것을 볼 수 있을 것이다. 하지만 이 경우에는 이제 rotate를 시켰으므로 case 3으로 이동할 수 있다는 것을 알 수 있다. case 3으로 가서 똑같이 한번 더 조정을 해주어야 한다.
case 5.
마지막 케이스다. 마지막 케이스는 s node가 red 인 경우이다. 이 경우에는 아래와 같이 조정하며 위의 케이스들 중의 하나로 다시 이동하게 된다.
4. 시간복잡도
검색의 시간복잡도: O(logn) 균형잡힌 트리이기 때문
삽입의 시간복잡도: O(logn) 계속 재귀적으로 호출하면서 루트까지 올라갈 수 있기 때문
삭제의 시간복잡도: O(logn) 계속 재귀적으로 호출하면서 루트까지 올라갈 수 있기 때문
'알고리즘' 카테고리의 다른 글
| Quicksort를 stable sorting이 되게 하는 법 (0) | 2021.04.27 |
|---|---|
| [백준] 17141번 연구소2 문제 BFS로 풀어보기 (0) | 2021.04.24 |
| Union-Find의 시간복잡도 (0) | 2021.04.20 |
| [백준] 1600번 말이 되고픈 원숭이 문제 BFS로 풀어보기 (0) | 2021.03.25 |
| [백준] 2251번 물통문제 BFS로 풀어보기 (0) | 2021.03.24 |
최근댓글