레드 블랙 트리 (Red-Black Tree) 삽입

레드 블랙 트리 (Red-Black Tree)

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC

조건

1. Root는 Black이다

2. 모든 리프(NIL)는 Black이다.

3. node가 Red -> node의 자식은 반드시 Black

• 연속된 Red node X

4. Root에서 임의의 리프 node까지 만나는 Black node의 수는 같다.

레드 블랙 트리 삽입

• 삽입한 node는 무조건 Red node 입니다.

• Red node - Red node 겹칠 때 Case 파악

  • Red node의 부모 node도 Red일 경우
  • 맨 밑의 Red node가 기준 입니다.

Restructuring

삽입된 node(m) 부모의 형제가 Black인 경우

1. m, m의 부모, m의 부모의 부모를 오름 차순으로 정렬

2. 가운데 값을 부모로 만들고 나머지는 자식 node

3. 가운데 값을 Black 나머지 자식은 Red

Recoloring

삽입된 node(m) 부모의 형제가 Red인 경우

1. m의 부모(p), m의 부모 형제를 Black으로 변환

2. m의 부모의 부모(p^2)를 Red로 변환

3. p^2가 Root node가 아니면 문제 발생

좋은 자료
https://goodgid.github.io/Red-Black-Tree-Algorithm/