RED-BLACK TREE

• balanced binary search tree

특징

• 모든 node는 red / black 의 색을 가져야함

• 삽입되는 새로운 노드는 항상 red

• Root Property : root node는 black

• External Property : leaf(NULL) node는 black

• Internal Property : red node의 child는 모두 black

• Depth Property : 각 노드에서 leaf 로 가는 경로의 black node의 수가 항상 같아야 함
  [ red node의 hieght <= logN ]

Double Red 해결방법 <삽입>

G(할아버지노드) P(부모노드) U(삼촌노드) M(내 노드)

Restructuring ( U is black)

1. 나(M)와 내 부모(P), 할아버지(G)를 오름차순으로 정렬

2. 무조건 가운데 있는 값을 부모로 만들고 나머지 둘을 자식으로 만든다.

3. 올라간 가운데 있는 값을 검정(Black)으로 만들고 그 두자식들을 빨강(Red)로 만든다.
4. 삼촌(U)의 자식이 있다면 붙여준다.

Recoloring (U is Red)

1. 현재 inset된 노드(M)의 부모(P)와 삼촌(U)를 검정(Black)으로 하고 할아버지노드(G)를 빨강(Red)로 한다.

2. 할아버지(G)가 Root node가 아니었을 시 Double Red가 다시 발생 할 수 있다