[TIL] 자료구조 - Red Black Tree 규칙

※ Red Black Tree 규칙

- 레드 블랙 트리는 자가 균형 이진 탐색 트리로, AVL 트리처럼 스스로 균형을 잡는 트리이다. 레드 블랙 트리에서는 다음과 같은 규칙으로 정렬해 균형을 맞춘다.

 

규칙

1. 모든 노드는 빨간색이나 검은색이다

2. 루트는 항상 검은색이다

3. 새로 추가되는 노드는 항상 빨간색이다

4. 루트에서 잎 노드로 가는 모든 경로는 같은 수의 검은 노드가 있어야 한다

5. 어떤 경로에서도 빨간색 노드 2개가 연속으로 있어서는 안된다

6. 모든 빈 노드는 검은색이라 가정한다

 

균형 맞추기

1) 이모 노드가 검은색인 경우

- 회전을 하고 나면 부모 노드는 검은색, 두 자식노드는 빨간색이 되어야 한다

 

2) 이모 노드가 빨간색인 경우

- 색상 전환을 하고 나면 부모 노드는 빨간색, 두 자식 노드는 검은색이 되어야 한다