Red-Black Trees: balanced binary search tree의 또 다른 강자
지난 포스팅에서는 (2, 4) 트리에 대해 알아보았는데, 이번에는 (2, 4) 트리를 기반으로 하는 또 다른 balanced search tree인 Red-Black Tree에 대해 자세히 알아보겠다. Red-Black Tree는 (2, 4) 트리의 장점을 그대로 유지하면서 구현 복잡도를 낮춘 효율적인 자료구조다.(multiway를 binary tree 형식으로)
1. Red-Black Tree란?
Red-Black Tree는 각 노드가 빨간색(red) 또는 검은색(black)으로 색칠된 binary search tree다. 이 색깔은 트리의 균형을 유지하는 데 중요한 역할을 한다. Red-Black Tree는 다음과 같은 특징을 갖는다.
- 루트 속성(Root Property): 루트 노드는 검은색
- 외부 노드 속성(External Property): 모든 외부 노드(NIL)는 검은색
- 내부 노드 속성(Internal Property): 빨간색 노드의 자식 노드는 모두 검은색(빨간색 중복 안됨)
- 깊이 속성(Depth Property): 모든 외부 노드까지의 경로에서 만나는 검은색 노드의 개수는 동일 (단, 루트 노드는 제외)
Correct Red-Black tree
2. Red-Black Tree와 (2, 4) 트리의 관계
Red-Black Tree는 (2, 4) 트리를 효율적으로 표현하기 위해 고안된 자료구조다. (2, 4) 트리의 각 노드는 Red-Black Tree에서 다음과 같이 표현될 수 있다.
- 2-노드: 하나의 검은색 노드
- 3-노드: 빨간색 자식 노드를 가진 검은색 노드
- 4-노드: 두 개의 빨간색 자식 노드를 가진 검은색 노드
위 표현 방식으로 Red-Black Tree는 (2, 4) 트리의 균형 속성을 그대로 유지하면서, 이진 트리의 구조를 활용하여 더욱 간단하게 구현할 수 있다.
이때 여러 case의 Red-Black Tree가 존재할 수 있는데, 이들 모두 한 개의 (2-4) tree로 대응된다.
 |
| (2-4) tree <-> Red-Black tree |
3. Red-Black Tree의 삽입 (Insertion)
Red-Black Tree에 새로운 노드를 삽입하는 과정은 다음과 같다.
- 탐색: 먼저 이진 탐색 트리와 동일하게 삽입할 위치를 찾는다.
- 삽입: 새로운 노드를 빨간색으로 삽입한다.
Insert -> Property 위배 - 균형 조정: 삽입된 노드가 Red-Black Tree의 특징을 위배하는 경우 (예: 빨간색 노드가 연속으로 나타나는 경우), 회전(rotation) 및 색 변경(recoloring) 연산을 통해 트리의 균형을 복원한다.
- w(이웃한 node)가 black인 경우 : restructuring
- rotation을 통해 red node를 parent로restructuring
- parent node를 검은색, child node를 빨간색 - w(이웃한 node)가 red인 경우 : recoloring
- parent node를 빨간색, child node를 검은색recoloring
4. Red-Black Tree의 삭제 (Deletion)
Red-Black Tree에서 노드를 삭제하는 과정은 다음과 같다.
- 탐색: 먼저 이진 탐색 트리와 동일하게 삭제할 노드를 찾는다.
- 삭제: 이진 탐색 트리의 삭제 규칙에 따라 노드를 삭제한다.
double black - 균형 조정: 삭제된 노드가 Red-Black Tree의 특징을 위배하는 경우 (예: 검은색 노드의 깊이가 달라지는 경우), 회전 및 색 변경 연산을 통해 트리의 균형을 복원한다.
- w가 black이고, red child를 갖는 경우(3,4-node)
(2-4) tree의 transfer와 같은 연산이다.restructuring
parent의 key 값을 double black이 발생한 node로 옮기고, 형제 node에서 parent의 key 값과 가장 가까운 값을 parent로 옮기도록 reconstruction한다. - w가 black이고, black child를 갖는 경우(2-node)
(2-4) tree의 fusion과 같은 연산이다.recoloring
parent의 key 값과 형제 node의 key 값을 받아 하나의 node로 통합하도록 recoloring한다. 이때 parent가 black이라면 2-node를 의미하므로 propagate한다. - w가 red인 경우
형제 node가 Red-Black tree 상의 다른 층에 있는 상황이다. (y도 parent의 요소)adjustment
adjustment를 통해 층을 맞춘 후 1 or 2를 수행한다.
5. Red-Black Tree의 성능 (Performance)
Red-Black Tree는 삽입, 삭제 연산 시 균형을 조정하기 위한 추가적인 연산이 필요하지만, 탐색, 삽입, 삭제 연산의 시간 복잡도를 O(log n)으로 보장한다. 따라서 데이터의 삽입 및 삭제가 빈번하게 발생하는 동적 데이터 환경에서 효율적인 자료구조다.
마무리하며
이번 포스팅에서는 Red-Black Tree의 개념, (2, 4) 트리와의 관계, 삽입, 삭제 과정, 그리고 성능에 대해 알아보았다. Red-Black Tree는 balanced multi-way search tree인 (2-4)의 응용된 예시로, 균형을 유지하면서 효율적인 연산을 지원한다. 다음 포스팅에서는 또 다른 새로운 주제로 찾아오겠다.
추천글 :[자료구조] (2-4) 트리
(https://hyeonb.blogspot.com/2024/06/2-4.html)
