레드블랙트리란?
레드-블랙 트리(Red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 레드-블랙 트리는 이진 트리의 특수한 형태로서, 컴퓨터 공학 분야에서 숫자 등의 비교 가능한 자료를 정리하는 데 쓰이는 자료구조이다.
레드블랙 트리의 특성
- 모든 노드는 빨간색 혹은 검은색이다.
- 루트 노드는 검은색이다.
- 모든 리프 노드(NIL)들은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
- 빨간색 노드의 자식은 검은색이다.
== No Double Red(빨간색 노드가 연속으로 나올 수 없다) - 모든 리프 노드에서 Black Height는 같다.
== 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.
4번 속성과 5번 속성이 회전과 색변환을 통해 노드를 재배치하게 만드는 이유이다.
레드블랙 트리를 사용하는 이유
이진 탐색 트리의 단점을 보완하기 위해서 쓰는 자료구조.
정렬된 데이터를 이진 탐색 트리로 구현한다면 아래와 같은 모습일 것이다.
시간복잡도를 따진다면 O(n)이 나와, 이미 정렬된 데이터에 대해서는 비효율적인 자료구조이다.
그러나 레드 블랙 트리의 경우, 최악의 경우에도 O(log n)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.
이는 루트 노드부터 가장 먼 리프 노드까지의 거리가, 가장 가까운 노드 경로까지의 거리의 두 배 보다 항상 작다는 특성 때문에 성립한다.
sentinel node
레드블랙트리 코드에서 한계 조건을 다루기 편리하도록 NIL을 표현하기 위해 사용하는 경계 노드이다. 레드블랙 트리에서 경계노드 T.nil은 트리의 다른 보통의 노드와 마찬가지로 동일한 필드를 가진다. 이 노드의 color는 black이지만, 다른 필드 값은 의미를 갖지 않는다.
경계노드를 이용함으로써 노드 x의 NIL자식을 x의 정상적인 자식 노드와 동일하게 다룰 수 있게 된다.
실제 구현할 때는 트리 내 각각의 NIL을 위해 개별적인 경계노드를 사용하는 것보단 저장 공간을 아끼기 위해 하나의 경계 노드 T.nil을 두어서 모든 NIL, 즉, 모든 리프와 루트의 부모를 표현하게 된다.
(모든 NULL 리프에 대한 포인터들이 하나의 NULL 값을 가리키게 설계하는 것이 바람직하다)
Sources
https://code-lab1.tistory.com/62 [코드 연구소]
https://jwdeveloper.tistory.com/280
https://velog.io/@shinhojung814/WEEK-05-C-레드-블랙-트리
https://dad-rock.tistory.com/355
