각 노드가 레드 혹은 블랙
노드에 저장하는 데이터가 아님
1 비트의 추가 정보 정도 (굳이 빨강/검정이 아닌 구분할 수 있으면 된다는 말)
스스로 균형(self-balancing, 레드와 블랙 노드 사이의 균형) 을 잡는 트리
트리 높이를 최소로 보장
삽입과 삭제 시 균형을 잡음
중요
레드-블랙 트리의 삽입, 삭제의 개념을 완벽히 이해하려고 파고드는 것 보다
레드-블랙 트리 구현 코드를 사용할 때 복잡한 패턴과 전략을 재귀적으로 작성하였고
위 전략으로 인해 삽입, 삭제가 진행되는구나 정도로 파악하고 사용하는 것이 중요
삭제의 경우 정말 복잡한 문제는 이해할 수 없을 정도인 경우도 있다고 함
특성
노드는 레드 또는 블랙
루트 노드는 블랙
모든 리프 노드(NIL = NULL) 는 블랙
레드 노드의 자식은 모두 블랙 (레드가 될 수 없다는 말)
어떤 노드와 리프 사이에 있는 노드 수는 동일
삽입 방법
BST 와 똑같이 삽입
새로 삽입하는 노드는 언제나 레드
레드 블랙 트리의 조건을 만족하는 트리 구조로 재귀적으로 고침
재귀 방향 : 리프 -> 루트
고칠 때 사용하는 두가지 트리 회전, 색 변경
레드-블랙 트리 삽입 전략
Case 1
상황 : 현재 노드 N 이 트리의 루트인 경우
전략 : N 을 블랙으로 변경
Case 2
상황 : N의 부모 P가 블랙인 경우
전략 : 아무것도 하지 않음
Case 3
상황 : N의 부모 P 레드, 삼촌 U 레드, 조부모 G 블랙인 경우
전략 : 나를 제외한 3개의 색상을 모두 바꾸고 G부터 재귀적으로 다시 실행
Case 4 - 1
상황 : P 레드, U 블랙
전략 : N 이 하위 트리의 안쪽에 있지 않도록 회전 N 이 한칸 올라가고 부모 P 가 한칸 내려가는 구조
Case 4 - 2
상황 : 4 - 1 을 통해 N 이 하위 트리의 바깥쪽에 있게 되면
전략 : 부모 P 와 조부모 G 를 우회전(트리 회전) 한 후 부모 P, 조부모 G 색을 바꾼다
레드-블랙 트리 삭제 전략
Case 1
상황 : N 이 새로운 루트
전략 : 루트는 모든 하위트리에 영향을 주므로 그냥 종료
Case 2
상황 : 형제자매 S 가 레드
전략 : P 와 S 의 색상을 변경, P 를 좌회전하여 S 가 N의 조부모가 되도록
Case 3
상황 : P, S, SL, SR 이 모두 블랙
전략 : S 를 레드 색상으로 변경하고 Case 1로 돌아가 다시 시작
Case 4
상황 : P 레드, SL, SR 블랙
전략 : S, P 색상 교환 후 종료
Case 5
상황 : S, SR 블랙 SL 레드
전략 : S 를 우회전, SL 이 S 의 부모이자 N 의 형제가 됨, SL, S 색상 교환
Case 6
상황 : Case 5 비슷, SL, SR 색상만 다름
전략 : P 를 왼쪽으로 회전, P, S 색상 교환, SR 블랙으로 변경
시간 복잡도 (삽입, 삭제 같음)
(삽입) 노드를 리프에 삽입 O(log n)
(삽입) 새 노드 색을 레드로 칠함 O(1)
(삭제) BST 방식으로 노드 제거 O(log n)
(공통) 망가진 레드 - 블랙 트리의 특성을 고침 O(log n), 색상 바꾸기(1), 트리 회전(1)
(최종) O(log n)
