// BF 개념은 레드블랙트리는 사용하지 않는 개념이다 //
개념
- 이진탐색트리(BST)의 한 종류
- 스스로 균형 잡는 트리
- 이진탐색트리(BST)의 worst case의 단점을 개선
- 모든 노드는 Red 또는 Black
속성
#1. 모든 노드는 Red 또는 Black
#2. 루트 노트는 black
#3. 모든 nil 노드(leaf 노드)는 black
#4. red의 자녀들은 black (= red가 연속적으로 존재할 수 없다)
(nil 노드인 경우도 포함)
#5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다
(자신은 카운트에서 제외)
nil 노드란?
- 존재하지 않음을 의미하는 노드
- 자녀가 없을 때, 자녀를 nil 노드로 표기
- 값이 있는 노드와, 동등하게 취급
- RB 트리의 모든 leaf 노드는 nil 노드
노드 x의 black height
- 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black 수
(자신은 카운트에서 제외)- #5 속성을 만족해야 성립하는 개념
색을 바꾸면서도 #5 속성을 유지하기
RB 트리의 두 자녀가 같은 색을 가질 때,
부모와 두 자녀의 색을 바꿔도 #5 속성은 여전히 만족한다.
-> 색을 바꾼 노드들을 다시 한 번 바꿔도 여전히 성립한다.
(삽입/삭제) 시에 사용하는 특성이기에 중요함
RB 트리는 어떻게 균형을 잡는가?
(삽입/삭제) 시 대체로 #4, #5 를 위반한다.
이를 해결하기 위해 구조를 바꾸다 보면, 자연스럽게 트리의 균형이 잡힌다
삽입 방식
- 삽입 전 RB 트리 속성 만족한 상태
- 삽입 방식은 일반적인 BST와 동일 (단, 삽입 노드는 항상 red)
- 삽입 후 RB 트리 위반 여부 확인
- RB 트리 속성을 위반했다면 재조정
- RB 트리 속성을 다시 만족
왜 새로 삽입하는 노드는 red인가?
: 삽입 후에도 #5 속성을 만족하기 위함
삭제 방식
- 삭제 전 RB 트리 속성 만족한 상태
- 삭제 방식은 일반적인 BST와 동일
- 삭제 후 RB 트리 속성 위반 여부 확인
- RB 트리 속성을 위반했다면 재조정
- RB 트리 속성을 다시 만족
속성 위반 여부 확인
- 삭제되는 color가 red인 경우
: 어떠한 속성도 위반하지 않는다
- 삭제되는 color가 black인 경우
: #2, #4, #5 속성을 위반할 수 있다특수한 상황을 제외하면, #5 속성을 항상 위반한다.
이 문제를 해결하기 위해
삭제된 color의 위치를 대체한 노드에, extra black을 부여한다.extra black의 역할은
경로에서 black 수를 카운트할 때, 1개의 black으로 취급된다.
*red-and-black 란? (extra black이 부여된) red 노드
-> red-and-black을 black 으로 바꾸면 해결*doubly black 란? (extra black이 부여된) black 노드
-> case. 1, 2, 3, 4 중에 하나로 해결
[case 분류 기준]
doubly black의 형제의 color & 그 형제의 자녀들의 color
*(오른쪽) (왼쪽)을 바꿔도 성립
(루트 노드를 기준으로, 좌우 대칭을 바꿔도 성립)
case.1)
doubly black의 (오른쪽) 형제가 red일 때부모와 형제의 색을 바꾸고,
부모를 기준으로 (왼쪽)으로 회전한 뒤,
doubly black을 기준으로 case.2, 3, 4 중에 하나로 해결
case.2)
doubly black의 형제가 black
&
그 형제의 두 자녀 모두 black 인 경우 24:40doubly black과 그 형제의 black을 모아서 부모에게 전달해서,
부모가 extra black을 해결하도록 위임
case.3)
doubly black의 (오른쪽) 형제가 black
&
그 형제의 (왼쪽) 자녀가 red
&
그 형제의 (오른쪽) 자녀는 black 인 경우doubly black의 형제의 (오른쪽) 자녀를 red가 되게 만들어서
이후엔 case.4를 적용하여 해결
case.4)
doubly black의 (오른쪽) 형제가 black
&
그 형제의 (오른쪽) 자녀가 red 인 경우(오른쪽) 형제는 부모의 색으로,
(오른쪽) 형제의 (오른쪽) 자녀는 black으로,
부모는 black으로 바꾼 후에,
부모를 기준으로 (왼쪽)으로 회전하면 해결
삭제되는 노드의 color
- 삭제하려는 노드의 *자녀 가 0개 또는 1개인 경우
: 삭제되는 color = 삭제되는 노드의 color
- 삭제하려는 노드의 *자녀 가 2개인 경우
: 삭제되는 color = 삭제되는 노드의 successor의 color
*자녀
(nil node가 아닌) 유효한 값을 가지는 자녀를 의미
Red-Black 트리의 시간복잡도
*N = 트리의 노드 수
순서: avg / worst
- insert: O(logN) / O(logN)
- delete: O(logN) / O(logN)
- search: O(logN) / O(logN)
Red-Black 트리 vs. AVL 트리
-
둘다 binary search tree
-
삽입/삭제/검색 시간복잡도: 둘다 worst case에서 O(logN)
-
삽입/삭제 성능: (비교적) 빠르다/느리다
-
검색 성능: (비교적) 느리다/빠르다
-
균형 잡는 방식:
RB트리 속성을 만족시키도록 / balance factor ∈ {-1, 0, 1} 되도록- 응용 사례
RB트리:
linux kernel 내부에 사용, Java TreeMap 구현, C++ std::map 구현, 등등
AVL트리:
dictionary,
한번 만들어 놓으면 삽입/삭제가 거의 없고, 검색이 대부분인 상황에서 사용