💿자료구조 - 레드-블랙 트리

NIL 닐

일반적으로 이진 트리의 노드는 값과 left 및 right를 가지는데, left나 right 중 하나 이상이 None 일 수 없음

 - 즉 좌측 자식이 없거나, 우측 자식이 없거나, 둘다 없거나

모든 None 을 NIL 로 규정 시 아래와 같은 트리를 얻을 수 있음

 

모든 leaf노드 is NIL

값을 가지는 모든 노드는 내부 노드

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Recoloring & Restructing

 

 

걍 아래는 위에꺼 손으로 해보기 전 적어놧던 개념..

---

 

Recoloring 과정

>> 원소 추가시엔 Red만 추가하기 떄문에, Black의 수는 신경 쓸 필요 없고, Red 연속만 신경쓰기

 

 

그런데 중간에 삼촌 노드 땜에 만족하지 않는 경우가 생겼다! ( NIL = 검정)

이땐 어떻게 해야 할까?

 

Restructuring 과정

>> 균형화 후 Recoloring

 

 

따라서!!!