[TIL] Red-Black Tree 기본 개념
내용이 다 이해가 가지 않지만, 일단 내용을 정리해 봤다
1부 https://www.youtube.com/watch?v=2MdsebfJOyM
2부 https://youtu.be/6drLl777k-E?si=SwbAbKtcyby9zjji
+ 개인적으로 저 유튜브 강의는 말도 너무 빠르고
Extra Black, Double Black 같은 이상한 개념들이 나오면서 정리가 안 됐다
그런 와중에 ㅁㄱ님이 잘 정리해 주신 내용을 공유해 주셔서 내용을 재정리했다
Red-Black Tree
이진 탐색 트리 BST 의 한 종류,
BST Worst Case 의 단점을 개선하여 스스로 균형 (Balancing) 잡는 트리
+ BST Worst Case - 구조가 한쪽으로 편향되는 경우, O(N)/ RB Tree 편향되지 않도록 한다, O(logN)
Red-Black Tree 속성
1. 모든 노드는 Red or Black
2. 루트 노드는 Black
3. 모든 nil (lead) 노드는 Black
4. Red 의 자녀들은 반드시 Black ! Red 가 연속적으로 존재할 수 없다.
5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 Black 수는 같다 (자기 자신은 카운트에서 제외)
nil 노드
존재하지 않음을 의미하는 노드
자녀가 없을 때 자녀를 nil 노드로 표기
같이 있는 노드와 동등하게 취급
RB 트리에서 leaf 노드는 nil 노드
노드 x 의 Black Height
노드 x 에서 임의의 자손 nil 노드까지 내려가는 경로에서의 Black 수 (5번 속성을 만족해야 성립하는 개념)
+ RB Tree 가 5번 속성을 만족하고 있고 두 자녀가 같은 색을 가질 때 부모와 두 자녀 색을 바꿔줘도 5번 속성은 여전히 만족한다
RB Tree 가 균형을 잡는 방법
삽입/ 삭제 시 주로 #4, #5를 위반하며 이들을 해결하려고 구조를 바꾸다 보면 자연스럽게 트리의 균형이 잡히게 된다
RB Tree 삽입 방법
0. 삽입 전 RB Tree 속성 만족한 상태
1. 삽입 방식은 일반적인 BST 와 동일
2. 삽입 후 RB Tree 위반 여부 확인
3. RB Tree 속성을 위반했다면 재조정
4. RB Tree 속성을 다시 만족
RB Tree 삽입 특징
삽입하는 노드는 항상 Red 이다, 이유는 삽입 후에도 #5 속성을 만족하기 위해서,
Red 삽입 후 #2 속성을 위반했을 때는 루트 노드의 색을 Black 으로 바꿔준다
노드를 삽입할 때 두 nil 노드의 색은 Black 으로 고정한다
(주의) 구조를 바꿔준 뒤에 BST 의 특징 또한 유지되어야 한다
구조를 바꾸면서도 BST 의 특징을 유지시키는 방법은 회전이다
RB Tree 삽입 예시
Case#1. Uncle 이 RED 인 경우
new 의 부모, 삼촌 노드를 BLACK 으로, 조부모 노드를 RED 로 수정한 뒤 조부모부터 반복적으로 조건을 확인한다
Case#2. Uncle 이 BLACK 이고, new 가 오른쪽 자식인 경우
new 의 부모를 기준으로 왼쪽 회전 후 Case #3 로 수정한 뒤 이어서 해결
Case#3. Uncle 이 BLACK 이고, new 가 왼쪽 자식인 경우
new 의 부모를 BLACK 으로, 조부모 노드를 RED 로 수정한 뒤 조부모 노드를 기준으로 오른쪽 회전
RB Tree 삭제 방식
삭제되는 색을 통해 속성 위반 여부를 확인하는 것이 중요하다
삭제하려는 노드의 자녀가 둘이라면 삭제되는 노드의 Successor 가
삭제하려는 노드의 자리로 오면서 색을 물려받게 되고
Successor 의 자리에서 삭제되면서 Successor 의 색이 빠진다
삭제되는 색이 Red 라면 어떠한 속성도 위반하지 않는다
삭제되는 색이 Black 이라면 #2, #4, #5 속성을 위반할 수 있다
삭제되는 색이 Black 일 때
#2를 위반할 경우, 루트 노드를 Black 으로 바꾸면 된다
그리고 특수한 상황을 제외하면 #5 속성을 항상 위반하게 된다
#5 속성을 다시 만족시키기 위해 삭제된 색의 위치를 대체한 노드에 Extra Black 을 부여한다
+ Extra Black 의 역할 - 경로에서 Black 수를 카운트할 때 Extra Black 은 하나의 Black 으로 카운트된다
Extra Black 을 부여받은 노드는 Doubly Black 이 되거나 Red-and-Black 이 된다
Case#1. 형제 노드 w 가 RED 인 경우
부모 노드를 RED 로, 형제 노드 w 를 BLACK 으로 만들고 왼쪽으로 회전
Case#2. 형제 노드 w 와 그 자녀들이 모두 BLACK 인 경우
부모 노드를 RED 로 만들고, x = x.p
Case#3. 형제 노드 w 의 왼쪽 자녀가 RED 인 경우
왼쪽 자식을 BLACK 으로 수정하고, 형제 노드는 RED 로 수정,
형제 노드를 기준으로 오른쪽 회전 후 new 의 형제 노드로 w 를 재설정
Case#4. 형제 노드는 BLACK, 형제 노드의 오른쪽 자녀가 RED 인 경우
형제 노드는 부모 노드 색으로, 부모 노드는 BLACK 으로, 오른쪽 자식은 BLACK 으로 수정 후 왼쪽으로 회전
삭제되는 색이 Black 일 때 위반 해결하기
RB Tree 시간복잡도
일반적인 BST 의 Worst Case 는 O(N) 이지만 RB Tree 는 스스로 균형을 잡기 때문에 Worst Case 도 O(log N) 이다
AVL 트리와의 비교
삽입/ 삭제에서 성능 차이가 나는 이유 - AVL Tree 는 삽입/ 삭제 후에 Root Node 까지 올라가서 Balance Factor 까지 확인하고, Balance Factor 가 조건에 맞지 않으면 구조를 변경한다, 규칙을 엄격하게 잡기 때문에 삽입/ 삭제가 오래 걸린다
검색 성능은 같은 시간 복잡도를 띄지만 조금의 차이가 난다 - AVL Tree 가 규칙이 엄격하기 때문에 검색이 조금 빠른 편
결론 - RB Tree 가 삽입/ 삭제 성능이 더 좋기 때문에 AVL Tree 보다 많이 사용한다
+ RB Tree 는 노드에 색깔을 부여하며 일정한 규칙 안에서 재구조화르 하지만, AVL 트리는 각 노드의 좌우 자식의 높이 차이를 비교하여 2 이상 차이날 때 재구조화를 한다,
AVL Tree 같은 경우 삽입할 때 무조건 Parent Node 를 차례대로 하나씩 비교하여 리밸런싱하는 과정이 포함되기 때문에 평균과 최악의 경우 둘 다 O(logN)의 시간 복잡도를 지니지만
RB Tree 의 경우 Color 가 추가되었기 때문에 무조건 트리를 회전하는 것이 아니라 색깔만 바꾸는 등의 방법으로 좀 더 느슨하게 리밸런싱하므로 트리 회전 횟수가 감소된다
AVL Tree 는 트리의 밸런스가 좀 더 엄격하게 유지되기 때문에 탐색에 유리
RB Tree 는 밸런싱을 느슨하게 하기 때문에 AVL Tree 에 비해 탐색엔 불리하지만 삽입, 삭제에 유리