레드 블랙 트리(Red Black Tree)

레드 블랙 트리(Red Black Tree)

자가균형이진탐색트리(AVL 트리)로서, 대표적으로는 연관 배열 등을 구현하는데 쓰이는 자료구조이다. (AVL트리는 레드-블랙 트리보다 더 엄격하게 균형이 잡혀있기 때문에, 삽입과 삭제를 할 때 최악의 경우에는 더 많은 회전이 필요하다.)

- 최악의 경우에도 O(log n)의 시간 복잡도로 삽입/삭제/검색 가능

- 루트노드보다 가장 먼 리프노드까지의 거리가 가장 가까운 노드 경로까지의 거리의 두배보다 항상 작다는 특성 때문에 성립한다.

0. 삽입되는 노드의 색깔은 무조건 레드이다
1.루트는 블랙이다
2. 모든 리프노드(단말)은 블랙이다 (여기서 리프노드는 일반적인 의미의 리프노드와 다르다. 모든 NIL포인터가 NIL이라는 리프노드를 가리킨다고 가정한다.)
3. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다
4. 루트 노드에서 임의의 리프노드에 이르는 경로에서 만나는 블랙노드의 수는 모두 같다.

 

 

레드 블랙 트리에서의 삽입

1. 이진검색트리에서의 삽입과 같다. 다만 삽입 후 삽입된 노드(x)를 레드로 칠한다.
2. 만일 x의 부모 노드 p의 색상이
   1. 블랙이면 → 아무 문제 없다.
   2. 레드이면 레드 블랙 특성 3번이 깨진다.

 

1️⃣ s가 레드일때 (recolor)

• p, p^2, s 노드의 색을 모두 블랙으로 한다.
• p^2 노드를 레드로 만들어 준다.
  • 이때 p^2노드가 루트노드라면 블랙으로 한다.
  • p^2노드의 부모노드가 빨강일 경우 문제가 발생해 반복해야 한다.

2️⃣ s가 블랙일때

1. x가 p의 오른쪽 자식일때

• 왼쪽 자식으로 만들어 준다.
• 왼쪽 자식일 때의 해결법을 적용한다.

2. x가 p의 왼쪽 자식일때

• p 중심으로 right rotate 시킨다.
• p 노드의 색을 바꿔준다.

 

레드블랙트리에서의 삭제

• 삭제 노드의 자식이 없거나 1개만을 가진 노드로 제한해도 된다
• 삭제하고 싶은 노드를 찾고, 그 노드를 대체할 수 있는 노드 (이진 탐색 트리의 삭제와 동일하다)를 찾아 target으로 만드는 것부터 시작한다.

 

1. 삭제노드가 레드이면 그 노드만 삭제해주면 된다.

2. 삭제노드가 블랙이라도 (유일한)자식이 레드이면 문제 없다. 노드를 삭제해주고 유일한 자식인 레드노드를 블랙으로 바꿔주면 된다.

3. 삭제하려는 노드와 그 자식 노드의 색깔까지 black인 경우

 

CASE 1. p가 레드노드일 때 

- p노드를 블랙노드로 바꾸고 s노드를 레드노드로 변화해준다.

- 루트노드에서 봤을 때 black 노드의 갯수에 변화가 없다

 

 

CASE 2. s노드가 블랙이고 r 노드가 레드인 경우

- left rotate 시켜주면 된다.

- 루트노드에서 봤을 때 black 노드의 갯수에 변화가 없다

 

CASE 3. s노드가 블랙이고 l노드가 레드인 경우

- l,s,r 노드를 right rotate 시켜준다.

- case 2로 해결한다.

 

CASE 4. p가 블랙 노드일때

- s 노드를 레드노드로 변화해준다

- 루트노드에서 봤을 때 black 노드의 갯수에 변화가 있다. -> black 노드가 하나 부족한 것이 p노드로 전이되었다고 할 수 있다. 그러므로 여기서는 p노드를 문제 노드로 놓고 재귀적으로 또 문제를 해결해주어야 한다.

 

CASE 5. s노드가 레드인 경우

- right rotate

- case 1,2,3 의 방법 중 하나로 해결한다.