레드/블랙 트리(Red/Black Tree)
레드/블랙 트리는 균형을 유지하기 위해 일련의 규칙을 사용하는 자가 균형 이진 탐색 트리의 유형으로 트리의 초기 모양에 관계없이 삽입, 삭제, 검색과 같은 작업에 대한 O(log n) 시간 복잡도를 보장한다.
레드/블랙 트리는 각 수정 후 트리를 조정하기 위해 간단한 색상 코딩 체계를 사용하여 자체 균형을 유지한다.
레드/블랙 트리는 각 노드가 빨간색 또는 검은색일 수 있는 색상이라는 추가 속성을 갖는 자체 균형 이진 탐색 트리이다.
삽입 및 삭제 중에 균형을 유지하여 효율적인 데이터 검색 및 조작을 보장한다.
레드 블랙 트리의 속성
레드/블랙 트리에는 여러 가지 속성들이 있는데 이러한 속성들을 알아야 동작 과정을 이해할 수 있다.
어떤 속성들이 있는지 하나씩 살펴보자.
1. 각 노드는 빨간색 또는 검은색이다.
2. 트리의 루트 노드는 항상 검은색이다.
3. 레드 노드는 레드 자식을 가질 수 없다. 즉, 어떤 경로에서든 두 개의 연속된 레드 노드는 불가하다.(Double Red가 나올 수 없음)
4. 블랙 노드는 노드에서 그 하위 null 노드(리프 노드)까지의 모든 경로에는 동일한 수의 블랙 노드가 있다.
5. 모든 리프 노드는 검은색이다. 하위 리프 노드는 NIL(Null Leaf)라고 불리는데 자료를 갖지 않고 트리의 끝을 나타내는 노드를 의미한다.
6. 레드/블랙 트리에서 새로운 노드를 삽입할 때 항상 빨간색으로 삽입한다.
레드/블랙 트리는 위의 속성을 통해서 루트에서 리프 노드까지의 가장 긴 경로가 최단 경로의 두 배를 넘지 않도록 하여 트리의 균형과 효율적인 성능을 유지한다.
n 노드가 있는 레드 블랙 트리의 높이는 h <= 2 log 2(n + 1)이다.
레드/블랙 트리의 블랙 높이는 루트 노드에서 리프 노드까지의 경로에 있는 블랙 노드의 수이다. 따라서 높이가 h인 레드 /블랙 트리는 "블랙 높이 >= h/2"를 가지게 된다.
레드/블랙 트리의 동작 과정
하지만 레드/블랙 트리의 속성으로 인해 3번 조건이 위배되는 상황이 발생한다.
만약 위의 그림과 같이 레드/블랙 트리가 있다고 가정하고 새로운 노드로 6을 추가해 보자.
6번 노드를 추가하면 5번 노드의 오른쪽으로 추가되는데 이렇게 되면 레드/블랙 트리의 3번째 속성인 레드 노드는 레드 자식을 가질 수 없다는 조건이 위배된다. 이러한 문제를 Double Red라고 하며 Restructuring, Recoloring 2가지 전략을 활용하여 해결할 수 있다.
전략을 살펴보기 전에 노드의 위치가 변경되는 것을 확인할 수 있게 간단히 표시를 해줘야 한다.
조상 노드와 부모 노드, 삼촌 노드, 새로운 노드를 간단히 표시해 줬다. 삼촌 노드는 부모의 형제 노드라고 생각하면 된다.
Double Red 문제를 해결하기 위해서 중요한 부분이 바로 삼촌 노드이다. 삼촌 노드가 어떤 색상을 가지고 있냐에 따라 2가지 전략 중 어떤 전략을 선택할지 나뉘게 된다.
삼촌 노드가 블랙이면 Restructuring을 진행하고, 레드면 Recoloring을 진행한다.
Restructuring
Restructuring은 말 그대로 현재 트리의 구조를 변경하는 것이다.
어떻게 Restructuring이 이뤄지는지 살펴보면
1. 새로운 노드, 부모 노드, 조상 노드를 오름차순으로 정렬한다.
2. 세 가지 노드 중 중간 값을 부모로 만들고 나머지 둘을 자식으로 만든다.
3. 새로 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만든다.
그림과 같이 Double Red가 발생했다고 가정해 보자.
먼저 1번 과정을 진행해 보면 아래의 그림과 같이 그릴 수 있다.
새로운 노드와 부모 노드, 조상 노드를 오름차순으로 정렬을 진행했다.
그다음으로 2번 과정을 그림으로 그려보면
오름 차순으로 정렬된 3가지 노드 중에서 중간 값인 6 노드가 새로운 부모가 되고 5 노드와 10 노드는 새로운 자식 노드가 된다.
여기서 주의할 점은 기존의 삼촌 노드였던 17 노드는 원래 조상 노드였던 10 노드의 자식이기 때문에 10 노드가 이동하면서 같이 이동하게 된다.
2번 과정이 끝난 뒤에 마지막으로 3번 과정을 그림으로 그려보면 아래와 같은 그림이 나온다.
3번 과정까지 끝나면 기존의 Double Red 문제가 해결된다.
새롭게 구성된 레드/블랙 트리를 보면 5번 노드가 리프 노드라서 블랙이 되어야 하지 않나? 라고 생각할 수 있지만 앞서 살펴봤던 레드/블랙 트리의 속성들 중에서 5번 속성을 보면 리프 노드가 없더라도 null 노드인 NIL을 가지고 있기 때문에 리프 노드가 존재한다고 생각하면 된다.
Recoloring
Recoloring은 말 그대로 노드가 가지고 있는 색상을 변경하는 전략이다.
어떻게 Recoloring이 되는지 살펴보고 그림을 그려보며 이해를 해보자.
1. 새로운 노드의 부모 노드와 삼촌 노드를 검은색으로 바꾸고 조상 노드를 빨간색으로 바꾼다.
2. 만약 조상 노드가 루트 노드라면 검은색으로 바꾼다.
3. 조상 노드를 빨간색으로 바꿨을 때 다시 Double Red가 발생한다면 Restructuring이나 Recoloring을 통해서 Double Red가 발생하지 않을 때까지 반복해 준다.
먼저 1번 과정을 그림으로 그려보면 아래의 그림과 같이 그릴 수 있다.
1번 과정을 거쳐 부모 노드와 삼촌 노드의 색깔을 블랙으로 변경해 주고 조상 노드를 레드로 바꿔주면서 Double Red 문제를 간단하게 해결할 수 있다.
하지만 여기서 고려해야 되는 부분이 생기는데 조상 노드가 루트인 경우다.
레드/블랙 트리의 속성을 확인해 보면 루트 노드는 항상 블랙 색깔을 가지고 있는데 그럼 만약 조상 노드가 루트일 경우는 어떻게 Recoloring을 해야 될지 의문이 생긴다.
조상 노드가 루트일 경우 기존의 Recoloring 과정을 거쳐 부모 노드와 삼촌 노드의 색깔을 블랙으로 바꾸고 조상 노드는 블랙 색깔을 그대로 유지시켜 주면 된다.
이렇게 하는 것이 가능한 이유는 블랙 색깔의 노드가 연속적으로 들어와도 큰 문제가 없기 때문이다.
2번 과정까지 완료되면 그다음부터는 상황에 따라서 Restructuring과 Recoloring을 사용하면서 Double Red 문제를 해결해 주면 된다.
레드 블랙 트리의 장단점
레드/블랙 트리의 장점
균형 잡힌 트리
레드/블랙 트리는 자체 균형을 유지한다. 즉, 왼쪽 하위 트리와 오른쪽 하위 트리 높이 간의 균형을 자동으로 유지한다. 이는 최악의 경우 검색, 삽입 및 삭제 작업에 O(logn) 시간이 걸리는 것을 보장한다.
효율적인 검색, 삽입 및 삭제
앞서 설명한 레드/블랙 트리는 균형 잡힌 구조로 인해 효율적인 삽입, 삭제, 검색 작업을 제공한다. 특히 삽입과 삭제 작업에서는 AVL 트리보다 더 효율적인 편으로 AVL트리는 노드의 이동을 무조건 수반하게 되지만 레드/블랙 트리는 노드를 움직이는 Restructuring과 색깔만 변경해 주는 Recoloring으로 균형을 유지하기 때문에 AVL트리보다 삽입과 삭제 작업에 있어서는 효율적인 편이다.
널리 사용되는 자료구조
맵, 세트 같은 다양한 데이터 구조를 구현하는 데 널리 사용된다.
TreeMap (Java Platform SE 8 )
A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used. This implementation provides guaranteed log(n) ti
docs.oracle.com
TreeSet (Java Platform SE 8 )
docs.oracle.com
자바에서 제공하는 TreeMap과 TreeSet도 레드/블랙 트리 구조로 이루어져 있다.
레드 블랙 트리의 단점
다른 균형 트리보다 복잡함
AVL 트리와 같은 단순한 균형 트리에 비해 레드 블랙 트리는 삽입 및 삭제 규칙이 더 복잡하다. 장점에서 설명했던 것처럼 2가지 전략을 활용하여 균형을 유지하게 되는데 AVL 트리와 같이 단순히 노드를 왼쪽 혹은 오른쪽으로 이동시키는 것과 다르게 색깔도 고려해야 되는 부분이 복잡함을 증가시키게 된다.
지속적인 오버헤드
레드/블랙 트리 속성을 유지하려면 모든 삽입 및 삭제 작업에 약간의 오버헤드가 추가된다.
모든 사용 사례에 최적이 아님
레드 블랙 트리는 대부분의 작업에 효율적이지만 지속적인 오버헤드가 커질 수 있으므로 자주 삽입하고 삭제해야 하는 애플리케이션에는 최선의 선택이 아닐 수 있다.
레드 블랙 트리를 사용하는 이유
이진 탐색 트리는 평균적으로 O(h) 시간 복잡도를 가지지만 최악의 경우 O(n)이 될 수 있다. 이러한 이진트리를 편향 이진트리라고 하는데 해당 문제를 해결하기 위해서 AVL 트리나 레드/블랙 트리와 같은 자체 균형 이진 탐색 트리를 사용한다.
AVL 트리는 레드 블랙 트리에 비해 균형이 더 잘 잡혀있지만 삽입 및 삭제 작업을 할 때 더 많은 회전이 발생한다. 따라서 삽입과 삭제 작업이 자주 발생하는 경우 레드 블랙 트리가 선호된다.
레드 블랙 트리의 사용 사례
맵 및 세트 구현: 레드 블랙 트리는 효율적인 검색, 삽입 및 삭제가 중요한 맵 및 세트를 구현하는 데 자주 사용된다.
파일 시스템: 레드 블랙 트리는 일부 파일 시스템에서 파일 및 디렉터리 구조를 관리하는 데 사용된다.
인메모리 데이터베이스: 레드 블랙 트리는 때때로 데이터를 효율적으로 저장하고 검색하기 위해 인메모리 데이터베이스에서 사용된다.
그래픽 및 게임 개발: 레드 블랙 트리는 충돌 감지 및 경로 찾기와 같은 작업을 위한 그래픽 및 게임 개발에 사용될 수 있다.
'CS > 자료구조' 카테고리의 다른 글
| 자료구조 - 해시(Hash) (0) | 2024.06.20 |
|---|---|
| 자료구조 - 힙 (0) | 2024.06.17 |
| 자료구조 - AVL 트리 (0) | 2023.12.10 |
| 자료구조 - 이진 트리(Binary Tree) (0) | 2023.08.16 |
| 자료구조 - 트리(Tree) (0) | 2023.08.16 |
