Red-Black 트리 개념 보기

1. Red-Black 트리란?

• root 노드와 leaf 노드의 색은 black
• red 색 노드의 자식은 black (double red 불가)
• 모든 leaf 노드에서 root 노드까지 가는 경로의 black 노드 수는 같음
• 조건이 깨지는 상황에서 Rebalancing
  • NIL = NULL

NIL : RB Tree 의 leaf node (규칙을 위한 노드, Null Node 라고 이해)

2. 삽입

• 노드 삽입 후 double red 발생 case 1
  • 부모 노드의 형제 노드가 red 일 때
• Recoloring 진행
  • 삽입한 노드의 부모와 부모의 형제 노드를 black으로 변경
  • 부모의 보모 노드를 red로 변경
  • 부모의 부모 노드가 root인지 double red 인지에 따라 조정 진행

duble red 발생 예시 case1(왼쪽), Recoloring(오른쪽)

• 노드 삽입 후 double red 발생 case 2
  • 부모 노드의 형제 노드가 black 이거나 없을 때
• Restructuring 진행
  • 조정 대상 : 삽입한 노드, 부모 노드, 부모의 부모 노드
  • 조정 대상 노드들을 오름차순 정렬
  • 가운데 노드를 부모 노드로 선정하고 black 으로 변경
  • 나머지 두 노드를 자식 노드로 두고 red로 변경

double red 발생 예시 case 2(왼쪽), Restructuring(오른쪽)

3. 삭제

• 삭제 대상 노드가 black 이고 그 자리에 오는 노드가 red 인 경우
  • 해당 자리로 오는 red 노드를 black 으로 변경

에고...... 모르겠다 여긴.... 😞😞😞😞😞