로그 시간을 보장하는 Red-Black Tree의 Search, Insert 연산

https://2jinishappy.tistory.com/318

Color를 이용해서 Self-Balancing을 구현하는 Red-Black Tree

이전 글에서 소개한 것 처럼 레드블랙트리는 BST의 탐색/삽입/삭제 시간을 로그 시간에 수행하기 위해 등장했다

 

삽입 및 삭제 연산은 red-black property를 해칠 수 있기 때문에 balance를 유지하기 위한 Rotation 연산이 필요하다

이 글에서는 탐색/삽입 연산에 대해 설명한다

 

Search Node in RBT

레드블랙트리에서의 탐색 연산은 BST(Binary Search Tree)에서의 탐색 연산과 완전히 동일하다.

 

Insert Node in RBT

레드블랙트리에서 노드를 삽입하는 것은 트리의 모양에 따라 다양한 케이스가 존재할 수 있다. 모양에 따른 케이스를 분류하는 것은 노드를 추가했을 때 Red-Black Property가 깨지는 것을 포착하고 이를 바로잡기 위함이다.

 

그 전에 알아두어야 할 것으로 tree rotation 연산이 있다.

Rotation 연산

https://2jinishappy.tistory.com/341

Binary Tree에서 Height를 조절하기 위한 Tree Rotation

Rotation 연산이란 BST의 성질을 해치지 않고 Subtree의 구조를 조정하는 연산을 의미한다. 레드블랙트리에서는 트리의 전체 height를 줄이기 위해 사용한다.

 

Insert Strategy

레드블랙트리에 노드를 추가할 때는 특별한 규칙이 두 가지 있다.

1️⃣ 처음 Node를 Insert할 때는 Red 속성으로 초기화한다. (삽입 시 property의 2, 3번 성질이 깨지기 쉽지만 Black-Height는 건드리지 않기 때문에 고치기도 쉽다)

2️⃣ Node의 색을 다시 칠하고, Node를 Rotation하는 과정을 통해 Red-Black Property를 유지한다.

 

이 규칙들을 유의해서 다음의 예시를 보자

Insert Case

삽입하려는 새로운 노드를 N이라 할 때, 

1️⃣ N이 Root일 때
2️⃣ N의 parent(P)가 Black일 때
3️⃣ N의 uncle(U)이 Red일 때
4️⃣ N의 uncle(U)이 Black이면서 (N-P-G가) 삼각형 형태일 때
5️⃣ N의 uncle(U)이 Black이면서 (N-P-G가) 직선 형태일 때

위에서 언급한 것 처럼 레드블랙트리의 삽입에는 다섯가지 케이스가 존재한다.

 

1️⃣ N이 Root일 때

새로운 노드를 추가했을 때 Root 노드이려면 기존 트리에 아무 노드도 존재하지 않아야 한다. 즉, 새로운 노드 N이 루트 노드가 된다.

이 때 1번 속성(Root Node는 Black이다)을 만족해야 하므로 N을 Black Node로 추가한다 (사실은 Red로 추가한 뒤 Black으로 바꾸는 거라고 봐도 무방하다)

 

2️⃣ N의 parent(P)가 Black일 때

두 번째로, N의 부모 노드가 Black일 경우다. 이 때는 Red Child로 N을 추가해도 전체 경로 상의 Black-Height에 영향을 끼치지 않기 때문에 삽입 후 추가 연산이 필요 없다.

3️⃣ N의 uncle(U)이 Red일 때

세 번째 케이스를 포함한 이후 부터는 모두 부모 노드가 Red일 때를 가정한다.

부모 노드와 같은 Level의 노드를 Uncle Node(삼촌 노드)라고 하는데, 위 그림은 부모 노드와 삼촌 노드가 모두 Red인 케이스다. Property의 3번인 Red의 Child는 Black이어야 한다는 성질을 위배하고 있다.

이 때는 부모 노드와 삼촌 노드를 모두 Black으로 바꾸고, 조상 노드(G)를 Red로 바꾼다. 그러면 G를 루트로 가지는 Subtree 상의 Black-Height는 영향이 없는 동시에, Red의 Child는 무조건 Black이어야 한다는 성질을 만족할 수 있다.

하지만 G의 컬러가 바뀌면서 G의 조상 노드들에서는 Property가 깨질 수 있기 때문에 G에 대해 재귀적으로 Balancing 연산을 적용해서 해결해야 한다.

4️⃣ N의 uncle(U)이 Black이면서 (N-P-G가) 삼각형 형태일 때

네 번쨰는 삼촌 노드가 Black이면서 새 노드(N) - 부모 노드(P) - 조상 노드(G)가 삼각형 형태를 이루고 있는 케이스다.

이러한 경우는 P를 기준으로 Left-Rotation을 한 뒤에 다음 케이스(5️⃣)의 연산을 적용하면 된다.

5️⃣ N의 uncle(U)이 Black이면서 (N-P-G가) 직선 형태일 때

마지막으로 삼촌 노드가 Black이면서 N-P-G가 직선 형태를 이루고 있는 케이스다.

이 때는 G를 기준으로 Right-Rotation을 적용한 뒤, P를 Black으로 G를 Red로 전환한다.

이 또한 자세히 보면 전체 Black-Height에는 영향이 없음을 알 수 있다.

 

예제

첫 번째(Case 1), 기존 트리가 아무것도 없을 때 👉 이 경우 새로운 노드를 Black으로 추가한다

 

두 번째(Case 2), 부모가 Black일 경우 👉 아무런 추가 연산도 발생하지 않는다

 

세 번째(Case 5), 새로 추가한 30의 부모 노드 20이 Red이고, N-P-G가 직선 형태이다.

👉 10(G)을 기준으로 Left-Rotation을 한 뒤, 20을 Black으로 10을 Red로 칠해준다.

 

네 번째(Case 4), 새로 추가한 15의 부모 노드 20이 Red이고, N-P-G가 삼각형 형태이다.

👉 20(P)을 기준으로 Right-Rotation한 뒤 Case 5가 되었으므로 10을 기준으로 Left-Rotation해서 15를 Black, 10을 Red로 칠해준다.

 

다섯 번째(Case 3), 새로 추가한 40의 부모 노드와 삼촌 노드 모두 Red이다.

👉 10과 30은 Black, 20은 Red로 칠해준다. 이렇게 하고 20을 기준으로 다시 property가 만족되는지 확인했을 때 20은 Root이므로 다시 Black으로 칠해준다.

 

이처럼 레드블랙트리의 탐색, 삽입 연산에 대해서도 정리했다.

가장 중요한 것은 Red-Black Property이고 이것이 언제 어떻게 깨지는지, 어떻게 복구해야 할 지에 초점을 맞추는 것 이다.

언젠가는 제일 어려운 삭제 연산에 대해서도 정리해보도록 .... 😴