Red-Black Tree

정의

특징

1. 이진 탐색 트리

2. 스스로 균형 잡는 트리
1. 삽입, 삭제 시 4, 5번 규칙을 어기게 되는데, 이를 해결하려고 구조를 바꾸면 자연스럽게 트리의 균형이 잡힘

시간복잡도

규칙

1. 노드는 레드 혹은 블랙 중의 하나이다.

2. 루트 노드는 블랙이다.

3. 모든 리프 노드(NIL)들은 블랙이다.

4. 레드 노드의 자식 노드들은 언제나 블랙이다.
1. → 레드 노드가 연속적으로 존재할 수 없다.

5. 어떤 노드로부터 시작되어 리프 노드(= NIL)에 도달하는 모든 경로에는 모두 같은 개수의 블랙 노드가 있다.(자기 자신은 카운트 X)

용어

NIL

• 값이 있는 노드들과 동등하게 취급

• → 모든 리프 노드(= NIL)들은 블랙이다.

Black Height

왼쪽 회전 (Left rotation)

오른쪽 회전 (Right rotation)

CRUD

삽입

1. 삽입 전, RB 트리 속성 만족한 상태

2. 삽입 방식은 일반적인 BST와 동일

3. 삽입 후, RB 트리 위반 여부 확인

4. RB 트리 속성을 위반했다면 재조정

5. RB 트리 속성을 다시 만족

규칙

1. 삽입하는 노드는 항상 레드다.
1. 삽입 후에도 5번 규칙을 만족하기 위해(Black Height의 변화가 없음)

Case.1

Case.2

Case.3

삭제

1. 삭제 전 RB 트리 속성 만족한 상태

2. 삭제 방식은 일반적인 BST와 동일

3. 삭제 후 RB 트리 속성 위반 여부 확인

4. RB 트리 속성을 위반했다면 재조명

5. RB 트리 속성을 다시 만족

규칙

1. 삭제하려는 노드의 유효한 자녀가 없거나 하나라면
1. 삭제되는 색 = 삭제되는 노드의 색

2. 삭제하려는 노드의 유효한 자녀가 둘이라면
1. 삭제되는 색 = 삭제되는 노드의 successor의 색
2. successor = 선택한 노드의 오른쪽 서브트리중 가장 작은값을 가지는 노드

3. 삭제되는 색이 레드라면
1. 어떠한 속성도 위반하지 않는다.

4. 삭제되는 색이 블랙이라면
1. 2, 4, 5번 규칙을 위반할 수 있다.

2번 위반

5번 위반

1. doubly black = extra black이 부여된 black 노드
1. Case.1







2. Case.2





3. Case.3







이제 Case.4와 같은 상황이므로





4. Case.4









5. Case.6

2. red and black = extra black이 부여된 red 노드
1. red and black을 black으로 교체

출처