레드 블랙 트리 (RED-Black Tree)

레드블랙트리 (RED-Black Tree)

자가균형 이진탐색트리로써, 대표적으로 연관배열 등을 구현하는데 쓰이는 자료구조

- 레드-블랙 트리는 복잡한 자료구조이지만, 실 사용에서 효율적이고 최악의 경우에도 우수한 실행시간을 보장
- 이진트리의 구조를 그대로 채용하되, 딱 하나 색상(Color)라는 속성을 노드에 추가함으로서 자동으로 균형을 유지
- 이진 검색트리의 모든 노드에 성질에 따라 레드 또는 블랙의 색상

특성

- 노드는 레드 또는 블랙의 색을 가짐
- 루트노드는 빨간노드일 수 없음 (검정으로 변환)
- 모든 리프노드는 블랙 (NIL 노드는 모두 블랙)
- 빨간노드는 두 개의 검정 노드를 가짐 (자식이 없을 경우 블랙 NIL 노드를 가짐)
- 루트에서 리프로 가는 경로의 검정 노드의 수는 모두 같음
- 부모 노드는 왼쪽 서브트리보다 크고 오른쪽 서브 트리보다 작음 (이진탐색 트리와 동일한 구조)
- 경로상에 연이어 두개의 빨간 노드가 있을수 없음 (회전 필요)
- 부모의 두 자식 노드가 모두 빨간 노드이면 부모를 빨간노드로 하고 자식은 검정 노드로 바뀔 수 있음(색상 변환)
- 새로 입력되는 노드의 색은 빨간색 (특성이 맞지 않으면 색상, 회전 작업)
- 하나의 검정노드만를 자식으로 가질 수 없음

레드-블랙 트리는 개략적(roughly)으로 균형이 잡혀 있음
따라서, 삽입, 삭제, 검색시 최악의 경우(worst-case)에서의 시간복잡도가
트리의 높이(또는 깊이)에 따라 결정되기 때문에 보통의 이진 탐색 트리에 비해 효율적

특징

- BST(Binary Search Tree)의 모든 특징을 가짐
- 노드의 자식이 없는 경우 자식을 가리키는 포인터는 NULL값을 저장 ( NULL을 leaf node로 간주)
- 루트 노드 부터 단말 노드(leaf node)까지 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않음
- AVL Tree 에 비해 덜 깐깐하기에 탐색속도는 느릴 수 있으나, 삽입 / 삭제 속도는 더 빠름

시간 복잡도

삽입, 삭제, 탐색의 시간복잡도는 O(log n)

기본동작
1. 색 변경 (Recoloring)
2. 회전 (Rotation)

색 변경, 회전 두 가지 방법을 이용해서 균형을 맞춤
우선 색 변경을 한 후, 색 변경이 불가능해지면, 회전을 진행

회전

레드블랙트리는 연산 과정중 회전이 발생

우회전 : 루트였던 13이 10으로 변경되고 13이 10의 오른쪽 자식으로 들어가게 됨
           이때 10의 오른쪽 자식 12가 13의 왼쪽자식으로 옮겨짐
           즉, 우회전을 할때 왼쪽 자식의 오른쪽 자식이 부모 노드의 왼쪽 자식으로 옮겨짐

좌회전 : 13이 루트가 되고 10이 13의 왼쪽 자식이 됨
           13의 왼족 자식으로 12가 있었으므로 12는 떼어내서 10의 오른쪽 자식에 위치시킴
           즉, 좌회전을 할때는 오른쪽 자식의 왼쪽 자식이 부모 노드의 오른쪽 자식으로 옮겨진다는것

삽입

1. 이진 탐색트리와 동일하게 삽입 (빨간색 노드, 양쪽 자식 노드에 검정색 NIL노드 연결)
2. 삽입 이후에 균형을 확인 한 후 맞지 않을 경우 색 변경, 회전을 통해 균형을 맞춤


처음에 루트로 삽입 되는 경우

- 이진 탐색트리와 동일하게 삽입 (빨간색 노드, 양쪽 자식 노드에 검정색 NIL노드 연결)
- 루트는 블랙 이라는 조건을 성립 시키기 위해 삽입 된 노드를 검정색으로 변환

부모 노드가 블랙일 경우

- 이진 탐색트리와 동일하게 삽입 (빨간색 노드, 양쪽 자식 노드에 검정색 NIL노드 연결)

부모 노드가 레드이고 삼촌 노드가 레드일 경우

- 이진 탐색트리와 동일하게 삽입 (빨간색 노드, 양쪽 자식 노드에 검정색 NIL노드 연결)
- 부모와 삼촌의 색을 모두 블랙으로 바꿔준 뒤 조부모 노드를 레드로 변경 (recoloring)
- 조부모 노드를 레드로 변경했으므로 그 위로 루트노드까지 규칙 위반이 되는게 없는지 재귀적으로 확인

부모 노드가 레드이고 삼촌 노드가 블랙일 경우
입력노드가 오른쪽자식, 부모 노드가 왼쪽 자식일 때

- 부모를 기준으로 좌회전

- 부모노드를 블랙으로 변경
- 할아버지 노드를 레드로 변경
- 할아버지 노드를 우회전

부모 노드가 레드이고 삼촌 노드가 블랙일 경우
입력노드가 왼쪽자식, 부모노드가 오른쪽 자식인 경우

- 부모노드를 기준으로 우회전
- 부모노드를 블랙으로 변경
- 할아버지 노드를 레드로 변경
- 할아버지 노드를 좌회전
(위의 과정을 반대로)

삭제

- 레드블랙트리의 삭제는 기본적으로 이진탐색트리의 삭제에 기반
- 노드를 삭제하고 나면 무너진 레드블랙트리의 규칙을 복원하는 것에 초점을 둠

디폴트 케이스

- 디폴트 케이스는 삭제가 일어나면 무조건 실행되는 케이스
- 삭제된 노드가 검은색인 경우 그 자리를 대체하는 노드를 검은색으로 칠함

만약 그 자리를 대체하는 노드가 검은색이라면 문제가 됨
이 경우 원래 검은색 노드를 다시 검은색으로 칠하는 경우로, 이런 노드를 이중 흑색노드라 부름

이중 흑색노드를 해결하려면 케이스별로 처리 방식이 다름
(이중 흑색 노드가 부모의 왼쪽 자식일 경우를 기준으로 설명, 반대 경우도 고려 해야 함)

이중 흑색노드 처리

이중흑색노드의 형제가 레드일 경우

- 형제를검은색, 부모를 빨간색으로 칠함
- 부모노드를 기준으로 좌회전

이중 흑색 노드의 형제가 블랙이고 형제의 양쪽 자식 모두 블랙일 경우

- 형제노드를 레드로 칠함
- 이중 흑색노드의 검은색 1개를 부모에게 전달

부모가 이중 흑생 노드가 된 경우

이중흑색노드의 형제가 블랙이고 형제의 왼쪽 자식이 레드, 오른쪽 자식이 블랙인경우

- 형제노드를 레드로 칠함
- 형제노드의 왼쪽자식을 블랙으로 칠함
- 형제노드 기준으로 우회전

이중흑색노드의 형제가 블랙이고 형제의 오른쪽 자식이 레드인 경우

부모 노드의 색을 형제 노드에 칠함
부모노드와 형제노드의 오른쪽 자식을 검은색으로 칠함
부모노드 기준으로 좌회전