Red-Black 트리

• 이진 탐색 트리(BST)의 한 종류
• 스스로 균형을 잡는 트리
• BST의 worst case의 단점을 개선

Red-Black트리의 속성

1. 모든 모드는 red 혹은 black
2. 루트 노드는 black
3. 모든 nil(leaf) 노드는 black
   • nil노드란?
     1. 존재하지 않음을 의미하는 노드
     2. 자녀가 없을 때 자녀를 nil노드로 표기
     3. 값이 있는 노드와 동등하게 취급
     4. rb트리에서 leaf노드는 nil노드가 됨
4. red의 자녀들은 black임.(red가 연속적으로 존재할 수 없음)
5. 임의의 노드에서 자손 nil노드들까지 가는 경로들의 black 수(black height)는 같음(본인은 카운트에서 제외)
   • 5번 속성을 만족하고 있고 두 자녀가 같은 색을 가질 때 부모와 두 자녀 색을 바꿔줘도 5번 속성은 만족함

RB 트리가 균형을 잡는 법

• 삽입/삭제 시 주로 4,5번 속성을 위반하며 이들을 해결하려고 구조를 바꾸다 보면 자연스럽게 트리의 균형이 잡히게 됨

RB 트리 삽입 방식

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

• 삽입 노드의 색은 항상 red
  - 노드를 삽입할 때 두 nil 노드의 색은 black으로 고정
  - 삽입 후에도 5번 속성을 만족하기 위함
  

2번 속성을 위반했을 때

• 루트 노드를 black으로 바꿔주면 됨
  (nil 노드는 항상 black이기 때문에 상관 없음)

4번 속성을 위반했을 때

• RED하나를 오른쪽으로 넘겨줌
• 구조를 바꿔준 뒤에 BST의 특징 또한 유지되어야되기 때문에, 값을 회전시켜야 함

  1. 20과 50의 색을 바꿔줌
  2. 50을 기준으로 오른쪽으로 회전
     삽입된 RED 노드가 부모의 왼쪽 자녀이고, 부모도 RED이고 조상의 왼쪽 자녀와 부모의 형제는 BLACK이라면, 부모와 조상의 색을 바꾼 후 조상을 기준으로 오른쪽으로 회전(오른쪽 왼쪽을 한 번에 모두 바꿔도 성립)
     

조상까지의 길이 꺾여있는 경우

1. 20을 기준으로 왼쪽으로 회전

2. 40 과 50의 색을 바꾸고 50을 기준으로 오른쪽으로 회전
   

꺽인 길을 펴준 뒤 회전

RED가 한쪽으로 몰려있지 않은 경우

1. 10과 50을 BLACK으로 변경
2. 20을 RED로 변경
   -> 2번 속성을 위반
   
3. 20을 BLACK으로 변경
   

• 모든 속성을 만족

부모와 삼촌을 BLACK으로 바꾸고 조상을 RED로 바꾼 뒤 조상에서 다시 확인을 시작