Red-Black Tree

서경원·2023년 5월 5일

Red-Black Tree

목록 보기

1/1

Red-Black 트리

이진 탐색 트리(BST)의 한 종류
스스로 균형(balancing) 잡는 트리
BST의 worst case의 단점을 개선
- 최악의 경우에는 링크드리스트처럼 일렬로 쭉 늘어지는 형태가 될 수 있다. 이 경우에는 시간복잡도가 O(N)이 되어서 일반적인 경우의 시간복잡도 O(logN)에 비해 매우 느리게 된다.
모든 노드는 red 혹은 black

Red-Black 속성

1. 모든 노드는 red 혹은 black
2. 루트 노드는 black

# nil 노드란?

존재하지 않음을 의미하는 노드
자녀가 없을 때 자녀를 nil 노드로 표기
값이 있는 노드와 동등하게 취급한다.
RB 트리에서 leaf 노드는 nil 노드

3. 모든 nil(leaf) 노드는 black
4. red의 자녀들은 black or red가 연속적으로 존재할 수 없다.
5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다.(자기 자신은 카운트에서 제외)

노드 x의 black height

노드 x에서 임의의 자손 nil노드까지 내려가는 경로에서의 black 수(자기 자신은 카운트에서 제외)
rbtree의 #5 속성을 만족해야 성립하는 개념

색을 바꾸면서도 #5 속성을 유지하기

RB 트리가 #5 속성을 만족하고 있고 두 자녀가 같은 색을 가질 때 부모와 두 자녀의 색을 바꿔줘도 #5 속성은 여전히 만족한다.
#5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다.(자기 자신은 카운트에서 제외)

RB 트리는 어떻게 균형을 잡는가?

삽입/삭제 시 주로 #4, #5를 위반하며 이들을 해결하려고 구조를 바꾸다 보면 자연스럽게 트리의 균형이 잡히게 된다.
#4. red의 자녀들은 black or red가 연속적으로 존재할 수 없다.
#5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다.(자기 자신은 카운트에서 제외)

삽입 overview

삽입전 RB 트리 속성 만족한 상태
삽입 방식은 일반적인 BST와 동일
삽입 후 RB 트리 위반 여부 확인
RB 트리 속성을 위반했다면 재조정
RB 트리 속성을 다시 만족

삽입 노드의 색은 항상 red다.

insert(50)

노드를 삽입할 때 두 nil 노드의 색은 black으로 고정한다. 그러면 자연스럽게 #3 속성을 만족한다.
#3. 모든 nil(leaf) 노드는 black

현재 Red-Black 트리 #2 속성 위반한 상태. 루트 노드를 black으로 바구면 해결~
#2. 루트 노드는 black

왜 새로 삽입하는 노드는 red인가?

삽입 후에도 #5 속성을 만족하기 위해
#5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다.(자기 자신은 카운트에서 제외)

그림에서 위쪽 그림은 RB트리에 nil노드가 하나 나와있는 모양이고 그 아래 그림은 그 nil노드에 red 노드를 삽입하는 것을 보여준다. red를 삽입하면 경로에 black의 노드가 추가되는 것은 아니기 때문에 #5 속성을 만족할 수 있다.

삽입 후 #4 속성 위반(case 1)

1. insert(30)

이 경우 #4와 #5를 위반했다. #4를 만족시키면서 #5를 유지하려면 10과 50을 black으로 바꾸고 20을 red로 바꾸면 된다.
4. red의 자녀들은 black or red가 연속적으로 존재할 수 없다.
5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다.(자기 자신은 카운트에서 제외)

이렇게 되면 #4와 #5는 해결했지만 20이 루트 노드라서 #2 속성을 위반. 20을 black으로 바꿔주자
2. 루트 노드는 black