Red-Black tree

• 이진 탐색 트리의 한 종류
• 스스로 균형을 잡는 트리 -> BST의 worst case 단점 개선
• 모든 노드는 red 혹은 black

속성

1. 모든 노드는 red 혹은 black

2. 루트 노드는 black

3. 모든 nil 노드는 black

4. Red의 자녀들은 black (red가 연속적으로 존재할 수 없다.)

5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들끼리의 black 수는 같다. (자기 자신 제외)

   black height : 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black 수 (자신은 카운트하지 않음)

   nil 노드

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

레드블랙트리 쉬운코드