이진 탐색트리의 한 종류

스스로 균형을 잡는 트리

1. 모든 노드는 레드 혹은 블랙
2. 루트 노드는 블랙

nil node는 자식 노드가 없을때 그 자식을 nil node라고 하고 값이 있는 노드와 동등하게 취급한다.

레드블랙 트리의 리프노드는 nil 노드

1. 모든 nil 노드는 블랙
2. 레드의 자식노드는 무조건 블랙 == 레드가 연속으로 존재 할 수 없다.
3. 임의의 노드에서 자손의 nil 노드까지 도달하는데 거치는 블랙노드 수(== black height)는 같다. (자기 자신 카운트 제외)

삽입 / 삭제 시 레드블랙트리의 규칙을 위반하게 되고 이때 재조정하면서 트리의 밸런스 유지

• 삽입하는 노드의 색은 항상 레드이다. (루트라면 블랙으로 바꾼다.)

  왜 레드인가 들어가는 레드 노드의 자식(닐 노드)가 블랙이므로 리프노드 블랙인것을 만족

  레드를 삽입한 이후의 블랙 height 가 일치하기 때문에

   50(블랙)
  

20(레드)

현재 트리에 10 insert하면 20(레드) 왼쪽 자식에 10(레드) 들어가게 되서 레드 연속이 생김. 위반!

이 연속된 레드를 나누자 r-b-r