- 균형 이진 트리(Balanced Binary Tree)
: 모든 노드의 좌우 서브 트리 높이가 1이상 차이나지 않는 트리- 균형 이진 탐색 트리(Balanced Binary Search Tree)
: 노드의 삽입/삭제가 일어날 때 균형을 유지하도록 하는 트리
Ex) AVL-Tree/RB-Tree
1. RB-Tree 개념
- BST의 한 종류
- 스스로 균형(balancing)을 잡는 트리: BST의 worst-case(한 쪽으로 편향될 때 검색/삽입 O(n))를 개선 -> O(lgn)
속성
1. 모든 노드는 red or black의 color를 가짐
2. root 노드는 black
3. 모든 nill(leaf) 노드는 black
-nill: 존재하지 않음을 의미하는 노드, 값이 있는 노드와 동등한 취급
4. red의 자녀들은 black = 즉, red는 연속적으로 존재할 수 없음
5. 임의의 노드에서 leaf 노드까지 가는 경로들의 black 수는 같다 (출발하는 자기 자신 제외)
-black height: 임의 노드의 black height는 정해져 있음. 어차피 nill로 가는 경로에서 black 수는 다 같기 때문
-> 색을 바꾸면서도 5번 속성 유지하기?
원본 RB-Tree가 5번 속성을 만족했다면, 두 자녀가 같은 색을 가질 때 부모와 두 자녀의 색을 바꿔줘도 여전히 만족
ex) A(parent, black)-B(left, red)&C(right, red)일 때 A(parent, red)-B(left, black)&C(right, black)
-> RB-Tree는 어떻게 균형을 잡을까?
삽입/삭제 시 주로 4&5번 속성을 위반하는데, 이를 해결하려고 ‘구조’를 바꾸다 보면 자연스럽게 균형이 잡히게 됨
2. RB-Tree 삽입
- 삽입 전, RB-Tree 속성 모두 만족하는 상태
- 삽입 방식은 BST와 동일
- 삽입 후 RB-Tree 속성 위반 여부 확인
- RB-Tree 속성 위반 시 재조정
- RB-Tree 속성 만족
+) 삽입 노드는 항상 red
그 이유는 삽입 후에도 #5 속성을 만족하기 위해
[속성 위반 여부]
#2 위반: root node의 색을 black으로 바꿔준다
#4 위반: 구조를 바꾸면서도 특징을 유지시키는 방법-> 회전 (색을 바꿔주고 회전)
case3. 삽입된 red 노드가 부모의 '왼쪽'자녀 & 부모도 red고 할아버지의 '왼쪽'자녀 & 삼촌(부모 형제)은 black이라면? (1자 모양)
: 부모와 할아버지의 색을 바꾼 후, 할아버지 기준으로 '오른쪽'으로 회전
case2. 삽입된 red 노드가 부모의 '오른쪽'자녀 & 부모도 red고 할아버지의 '왼쪽'자녀 & 삼촌은 black이라면? (꺾여있는 모양)
: 부모를 기준으로 '왼쪽'으로 회전한 뒤, case3의 방식으로 해결
case1. 삽입된 red 노드의 부모도 red & 삼촌도 red라면
: 부모와 삼촌을 black으로 바꾸고 할아버지를 red로 바꾼 뒤 할아버지에서 다시 확인을 시작
예제) insert: 50 -> 20 -> 10 -> 30 -> 80 -> 40 -> 35 -> 25
3. RB-Tree 삭제
- 삭제 전, RB-Tree 속성 모두 만족하는 상태
- 삭제 방식은 BST와 동일
- 삭제 후 RB-Tree 속성 위반 여부 확인
-> 삭제 시 어떤 색이 삭제되는지 중요- RB-Tree 속성 위반 시 재조정
- RB-Tree 속성 다시 만족
[삭제 방법]
1. 삭제하려는 노드의 자식이 없거나 한 개인 경우
삭제되는 색 = 삭제되는 노드의 색
2. 삭제하려는 노드의 자식이 두 개인 경우
삭제되는 색 = 삭제되는 노드의 successor의 색
즉, successor가 삭제되는 곳을 대체하게 되면서 색도 물려받음
(*successor(후임자): 트리 내에서 주어진 노드 바로 다음으로 큰 값 = 오른쪽 서브트리의 가장 작은 값)
[속성 위반 여부]
삭제되는 색이 red인 경우
: 어떠한 속성도 위반하지 않음
삭제되는 색이 black인 경우
: #2, #4, #5 속성을 위반할 수 있음
- #2 위반: root 노드를 black으로 색 변경
- #5 위반: 삭제된 ‘색’의 위치를 대체한 노드에 extra black 부여
(extra black: 경로에서 black의 수를 count할 때 하나의 black으로 count 되도록)
(doubly black: extra black이 부여된 black 노드)
(red-and-black: extra black이 부여된 red 노드)
[extra black 해결]
분류 기준: doubly black의 형제의 색 & 형제의 자녀들의 색
1. red-and-black : Black으로 바꾸면 해결
2. doubly black
- Case 4: doubly black의 '오른쪽' 형제 black & 형제의 '오른쪽' 자녀가 red일 때
(먼 친척이 red일 때, 1자 형태 )
'오른쪽' 형제 = 부모의 색,
형제의 '오른쪽' 자녀 = black,
부모 = black
“색상을 바꾼 후 부모를 기준으로 '왼쪽'으로 회전해 해결”
- Case 3: doubly black의 '오른쪽' 형제 black & 형제의 '왼쪽' 자녀 red & 형제의 '오른쪽' 자녀 black (가까운 친척이 red일 때, 꺾인 형태)
doubly black의 형제의 '오른쪽' 자녀가 red가 되게 만들어서 case4 적용
“형제와 형제 자식의 색을 바꾸고 rotate”
- Case 2: doubly black의 형제가 black & 형제의 두 자녀 모두 black (모두 black일 때)
doubly black과 형제의 black을 모아 부모에게 전달 -> 부모가 extra black을 해결하도록 위임
“색 뒤집기 해서 부모한테 black 전달해서 부모에서 해결”
- Case 1: doubly black의 '오른쪽' 형제가 red
부모&형제의 색을 바꾸고 부모 기준으로 '왼쪽'으로 회전한 뒤 doubly black을 기준으로 case 2.3.4로 해결
“형제랑 부모 색을 바꾸고 회전해서 case 따지기”
[삭제 과정]
1. 삭제하려는 노드의 자식을 확인
- 없거나 한 개: 삭제되는 색 = 삭제하려는 노드 색
- 두 개: 삭제되는 색 = successor의 색
2. 삭제되는 색 확인
- red: 속성 위반x
- black: 속성 위반, extra black 부여로 height 유지
3. extra black 해결
- case 4,3,2,1
