Red Black Tree
자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)의 일종
이진 탐색 트리의 성능을 유지하면서 트리의 균형을 자동으로 조정하는 구조즉 동일한 노드의 개수일 때 깊이를 최소화하여 시간 복잡도를 줄이고자 하는 것이다.
검색, 삽입, 삭제 연산은 O(logN)
구조
- 모든 노드는 빨간색 혹은 검은색
- 루트 노드는 검은색
- 리프 노드(NIL)는 검은색이다.
- NIL : 데이터를 가지지 않는 노드로, 자료의 끝을 의미한다.
- 빨간 노드의 자식은 검은색이다.
- 검은색 노드는 두번 연속 나와도 된다.
- 리프 노드에서 루트 노드까지 경로에서 만나는 검은 색 노드 수는 항상 같다.
삽입
N : 새로 삽입할 노드
P : 부모 노드
G : 조상 노드, 부모의 부모 노드
U : 삼촌 노드, 부모노드의 형제 노드
새로운 노드는 항상 빨간색으로 삽입한다.
이 때, 빨간색 노드가 연속적으로 발생할 수 있다.(Double Red)
아래는 Double Red를 처리하는 2가지 방법이다.
Restructuring : 삽입 노드 기준 삼촌 노드가 검은색인 경우
N, P, G 를 정렬하여 BST 기반으로 재구조화
새로운 부모노드를 검은색으로 변경
자식 노드를 모두 빨간색으로 변경
이때 7은 5 의 자식이므로 딸려간다.
Recoloring : 삼촌 노드가 빨간색인 경우
P, U를 모두 검은색으로 바꾸고 G는 빨간색으로 바꾼다.
만약 G가 루트 노드인 경우 검은색으로 바꾼다.
이때 빨간 색이 된 G로 인해 Double Red가 발생한 경우
G 를 N 으로 변경하고 U(이전 G 기준)의 색깔에 따라
Resturcturing 또는 Recoloring을 수행한다.
삭제
삭제할 대상 노드의 색이 Red 일 경우
삭제해도 아무런 문제가 없다.
삭제할 대상 노드의 색이 Black 일 경우
Default 케이스
삭제된 노드가 검은 색인 경우 그 자리를 대체하는 노드를 검은색으로 칠한다.
만약 대체된 노드가 검은색이고 새로 칠하는 색도 검은 색일 경우
이러한 노드를 이중 흑색 노드라고 한다.
이중 흑색 노드 처리
이중 흑색 노드의 형제가 Red 인경우
형제를 Black으로 칠한다.
부모를 Red로 칠한다.
부모를 기준으로 왼쪽으로 회전한다.
이중 흑색 노드의 형제가 Black 이고 형제의 양쪽 자식 모두 Black 인 경우
형제 노드만 Red로 만들고 이중 흑색 노드의 검은색 1개를 부모에게 전달한다.
이중 흑색 노드의 형제가 Black 이고 형제의 왼쪽 자식이 Red, 오른쪽 자식이 Black 인 경우
형제 노드를 Red로, 형제 노드의 왼쪽 자식을 Black으로 칠한다.
형제 노드를 기준으로 우회전 한다.[이중 흑색 노드 발생]
[처리]
이중 흑색 노드의 형제가 Black 이고 형제의 오른쪽 자식이 Red인 경우
부모 노드와 형제 노드의 오른쪽 자식을 검은색으로 칠한다.
부모의 노드의 색을 형제에게 넘긴다.
부모 노드 기준으로 좌회전한다.[이중 흑색 노드 발생]
[처리]
