유튜브 채널
쉬운코드의 레드-블랙 트리 강의를 기반으로 정리한 내용입니다. (바로가기)
Read-Black 트리 개념
- 이진 탐색 트리(BST)의 한 종류
- 스스로 균형(balancing) 잡는 트리
- BST의 worst case의 단점을 개선
- 모든 노드는
red혹은black
이진 탐색 트리란?
각 노드에서 자기보다 작은 값들은 왼쪽 서브트리 반대로 큰 값은 오른쪽 서브트리에 있는 특징을 만족하는 이진 트리를 이진 탐색 트리라고 한다.
BST의 worst case란?
이렇게 한쪽으로 편향이 되어있는 트리에서 삽입/삭제의 시간 복잡도는 O(N)이다. 이게 일반적인 Binary Search Tree의 단점이다. 최악의 상태에서 Binary Search Tree에 있는 모든 노드를 한 번씩 다 확인해야한다는 말이다.
레드-블랙 트리의 장점
스스로 균형을 맞추며 최악의 경우에도 시간 복잡도가 O(N)이 아닌 O(log N)이 나올 수 있도록 보장한다.
Red-Black 트리 속성
1. 모든 노드는 Red 혹은 Black이다.
2. 루드 노드는 Black이다.
3. 모든 nil(leaf) 노드는 Black이다.
nil 노드란?
- 존재하지 않음을 의미하는 노드
- 자녀가 없을 때 자녀를
nil노드로 표기- 값이 있는 노드와 동등하게 취급
- RB 트리에서 leaf 노드는
nil노드
4. Red의 자녀들은 Black이어야 한다.
다른 말로 Red가 연속적으로 존재할 수 없다고도 함
5. 임의의 노드에서 자손 nil 노드까지 가는 경로들의 Black 수는 같다.
자기 자신은 카운트에서 제외함
노드 x의 Black height
- 노드
x에서 임의의 자손nil노드까지 내려가는 경로에서의 black 수 (자기 자신은 카운트에서 제외) - 5번 속성을 만족해야 성립하는 개념임
색을 바꾸면서 5번 속성 유지하기
RB 트리가 5번 속성을 만족하고 있고 두 자녀가 같은 색을 가질 때 부모와 두 자녀의 색을 바꿔줘도 5번 속성은 여전히 만족한다.
A의 부모 관점
A와 B의 색만 바뀐 것이지 Black이 추가 되거나 사라진게 아니기 때문에 경로의 Black 수는 유지 된다.
A의 관점
경로에 흑이 추가된 것 처럼 보이지만 자기 자신이 Red로 변경 되었기 때문에 경로 상 흑 개수는 전과 동일하다.
B, C 관점
자기 자신은 카운트하지 않기 때문에 달라지는 게 없다.
반대로도 그대로 성립함
RB 트리는 어떻게 균형을 잡는가?
삽입/삭제 시 주로 4, 5번을 위반하며 이들을 해결하려고 구조를 바꾸다 보면 자연스럽게 트리의 균형이 잡히게 된다.
Red-Black 트리 삽입 방식
- 삽입 전 RB 트리 속성을 만족해야 한다.
- 삽입 하는 노드의 색상은 Red로 고정한다.
- 삽입 한 후에도 5번 속성을 만족하기 위함임
- 삽입 방식은 일반적인 BST와 동일하다
- 삽입 후 RB 트리 위반 여부를 확인한다.
- RB 트리 속성을 위반했다면 재조정
- RB 트리 속성을 다시 만족해야 한다.
50 삽입
Red 삽입 후 2번 속성을 위반 했을 때 루트 노드를 Black으로 바꿔주면 된다.
이어서 20 삽입
10 삽입
- 20과 50의 색을 바꿔준다.
- 50을 기준으로 오른쪽으로 회전한다.
삽입 후 4번 속성을 위반 했을 때
- 삽입된 Red 노드가 부모의 왼쪽* 자녀
- 부모도 Red고 할아버지의 왼쪽* 자녀
- 삼촌(=부모의 형제)은 Black이라면
부모와 할아버지의 색을 바꾼 후 할아버지 기준으로 오른쪽* 으로 회전한다.
**오른쪽 왼쪽을 바꿔도 성립된다.
이런 형태를 case.3라고 한다.
다른 케이스 알아보기
사진의 예시가 잘못된 20=50 중간에 50으로 변경됨ㅠ 다시 찍기 귀찮
50, 20에 이어 40 삽입
4번 속성을 위반함 해결하기 위해 Red 하나를 넘겨야 하는데 BST 특징 또한 유지하면서 넘기려면 회전을 사용해야 함
case.3와 살짝 다른 점은 삽입된 노드를 기준으로 할아버지까지의 경로가 꺾였다는 점이다.
꺾인 부분을 펴줘서
case.3와 같은 형태로 만들면case.3와 같은 방식으로 해결 가능할 것 같다.
- 20을 기준으로 왼쪽으로 회전한다.
회전 후에도 4번 외의 속성들을 만족하며 이제 case.3의 형태가 됐다.
- 40과 50의 색을 바꾼다.
- 50을 기준으로 오른쪽으로 회전한다.
귀찮아서 nil 노드는 생략함 이제 4번 속성을 포함해서 Red-Black 트리의 모든 속성을 만족함
삽입 후 4번 속성을 위반 했을 때
- 삽입된 Red 노드가 부모의 오른쪽* 자녀
- 부모도 Red고 할아버지의 왼쪽* 자녀
- 삼촌(=부모의 형제)은 Black이라면
부모를 기준으로 왼쪽*으로 회전한 뒤
case.3의 방식으로 해결
오른쪽 왼쪽을 바꿔도 성립됨
이런 형태를 case.2라고 한다.
또 또 다른 케이스를 알아보자
20, 10, 50에 이어서 30 삽입
Red-Black 트리 4번 속성 위반!
Red가 한 쪽으로 몰려 있지 않아서 옮길 수가 없음...
4번 속성을 만족시키면서 5번 속성을 유지하려면 10과 50을 Black으로 바꾸고 20을 Red로 바꾸면 된다.
하지만
루트 노드가 Red가 됐기 때문에 2번 속성을 위반하게 된다. 간단하게도 20을 Black으로 바꿔주면 해결된다.
Red-Black 트리의 모든 속성을 만족하게 됐다.
삽입 후 4번 속성을 위반 했을 때
- 삽입된 Red 노드의 부모도 Red
- 삼촌(=부모의 형제)도 Red라면
부모와 삼촌을 Black으로 바꾸고 할아버지를 Red로 바꾼 뒤 할아버지에서 다시 확인을 시작한다.
할아버지에서 다시 확인을 한다는 것은 할아버지의 색이 Red로 바뀌었는데 그 할아버지가 루트 노드였다면 Black으로 바꿔야하기 때문이다.
마찬가지로 할아버지의 색이 Red로 바뀌었는데 할아버지에게 부모가 있고 할아버지의 부모가 Red라면 4번 속성을 위반하는 것이기 때문에
꼭.꼭.꼭 할아버지에서 다시 확인해야 한다.
이런 형태를 case.1라고 한다.
