Red-Black Tree 속성/검색/삽입/삭제, 시간복잡도
1. Red-Black Tree
2. Red-Black Tree 정보
Red-Black Tree의 성립조건은 다음과 같다.
- 루트 노드는 언제나 Black이다.
- Leaf 노드 (말단 노드) 또한 언제나 Black이다.
- 만약 노드가 Red라면, 그 노드의 자식들은 언제나 Black이다. 즉, red node가 연속으로 올 수 없다.
- 루트에서 말단 노드까지의 Black node의 개수는 언제나 동일하다.
.png)
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일 경우에는 아무런 추가 조치 없이 삽입이 가능해진다.
.png)
하지만 문제가 되는 경우는 삽입하려는 부모의 노드가 빨간색일 경우이다.
.png)
이를 위해 우리는 경우를 몇 가지로 나누어볼 수 있다.
.png)
s가 Red일 경우
- 먼저 s가 Red일 경우부터 살펴보겠다.
.png)
위 그림처럼 생각해볼 수 있는데 이 경우에는 아래처럼 바꾸어주면 된다.
.png)
즉 p와 s 노드를 둘 다 Black으로 바꾸어 주고 P의 parent node를 red로 바꾸어주는 것이다. 하지만 만약 p^2의 parent node 또한 red 였다면 추가적으로 문제가 생긴다. 이 경우에는 p^2 노드를 recursive하게 하여 추가적인 조정을 해주어야 한다.
-
다음으로 만약 s 노드는 Black이고 추가하려는 x 노드가 p의 left child일 경우를 살펴보자
.png)
즉, 위와 같은 경우라고 볼 수 있다. 이런 경우에는 아래의 그림처럼 조정해주면 된다.
.png)
즉 p 노드를 중심으로 right rotate를 시키고 p 노드의 색깔을 red 에서 black으로 바꾸어주면 되는 것이다.
-
마지막으로 s 노드가 black이면서 x는 p의 right child인 경우를 살펴보자
.png)
위 그림과 같은 경우를 의미한다. 이 경우에는 아래와 같이 변경해주면 된다.
.png)
하지만 이런 식으로 변경해도 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.
.png)
삭제한 이후의 검정색 노드가 하나 모자라는 노드를 x로 표시했을 때 위와 같은 그림이 case 1이다. s 는 Black이고 s의 left child와 right child 노드가 모두 Black인 경우다. 이 경우는 가장 간단한 경우로 아래와 같이 조정해주면 된다.
.png)
위와 같이 조정해주면 p 노드가 Black으로 바뀌면서 x 노드까지의 경로에 모자랐던 black 노드의 개수를 하나 늘려줌으로써 문제가 해결된다.
case 2.
.png)
case1과 유사하지만 이번에는 p 노드까지 모두 다 Black이다.
.png)
이번에도 s 노드를 Red로 바꾸어주지만 Black 노드가 하나 부족한 것이 p node로 전이되었다고 할 수 있다. 그러므로 여기서는 p 노드를 문제 노드로 놓고 재귀적으로 또 문제를 해결해주어야 한다.
case 3.
.png)
s 노드는 black이고 r node가 red인 경우를 뜻한다. 여기서도 마찬가지로 하얀색 노드는 red/black이 와도 괜찮다는 뜻이며 red/black 각각의 경우에 대해 대입해보면 된다. 여기서는 묶어서 한 가지 상황으로 처리한 것이다. 이 경우에는 아래의 그림과 같이 left rotate를 시켜주면 된다.
.png)
여기서 하얀색 노드는 이전의 색깔을 그대로 따라간다는 의미이다.
case 4.
.png)
이번에는 위와 반대로 r이 Black이고 L이 red인 경우이다. 이 경우에는 아래와 같이 rotate를 시켜준다. (s를 기준으로 하고 rotate를 시켜주는 것임)
.png)
하지만 위와 같이 변경하여도 x에 여전히 -1이 있는 것을 볼 수 있을 것이다. 하지만 이 경우에는 이제 rotate를 시켰으므로 case 3으로 이동할 수 있다는 것을 알 수 있다. case 3으로 가서 똑같이 한번 더 조정을 해주어야 한다.
case 5.
.png)
마지막 케이스다. 마지막 케이스는 s node가 red 인 경우이다. 이 경우에는 아래와 같이 조정하며 위의 케이스들 중의 하나로 다시 이동하게 된다.
.png)
3. Red-Black Tree 시간복잡도
검색의 시간복잡도: O(logn) 균형잡힌 트리이기 때문
삽입의 시간복잡도: O(logn) 계속 재귀적으로 호출하면서 루트까지 올라갈 수 있기 때문
삭제의 시간복잡도: O(logn) 계속 재귀적으로 호출하면서 루트까지 올라갈 수 있기 때문
.png)
.png)
.png)
.png)
.png)
.png)
.png)