[알고리즘] 레드블랙트리(red-black tree) - 특징, 삽입

red-black tree

자가 균형 이진 탐색트리로써, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조.

트리에 n개의 원소가 있을 때 최악의 경우에도 일정한 O(log n)의 시간복잡도로 삽입, 삭제, 검색을 한다.

또, 레드-블랙 트리에서는 리프 노드들은 비어있고, 자료를 가지고 있지 않다.

1. 특징

• 트리의 모든 노드의 색은 BLACK or RED
• 루트 노드의 색은 무조건 BLACK 
• 모든 리프 노드(자식이 없는 노드)의 색은 BLACK 
• RED 노드의 자식들은 모두 BLACK , BLACK 노드의 자식들은 BLACK or RED
• 루트 노드에서 모든 리프 노드 사이에 있는 BLACK 노드의 수는 모두 동일

> BLACK 은 연달아 올 수 있지만, RED 는 연달아 올 수 없다.

2. 연산

[ 회전 ] > 새로운 노드가 삽입/삭제 되었을 경우 red-black tree의 특징을 유지하기 위해 

- 우회전

왼쪽에 있던 자식 노드 → 부모 노드

왼쪽 자식 노드의 오른쪽 자식 노드 → 부모 노드의 왼쪽 자식

- 좌회전

오른쪽에 있던 자식 노드 → 부모 노드

오른쪽 자식 노드의 왼쪽 자식 노드 → 부모 노드의 오른쪽 자식

[ 삽입 ]

1. 이진 탐색을 통해 삽입될 데이터의 위치를 찾는다.

2. 찾은 위치에 삽입한 후, 노드를 RED로 만든다.

3. NULL을 삽입한 노드의 자식 노드로 한다.

4. red-black tree 의 특징을 만족시키기 위해(리프 노드는 무조건 BLACK) 회전을 반복한다.

- case. 삼촌 노드 RED ( 삽입한 노드 = N )

위의 그림에서 삼촌노드란 U를 말한다.

• 부모노드, 삼촌노드 → BLACK 

• 할아버지 노드 → RED

• 할아버지 노드를 삽입한 노드라고 생각하고 루트까지 확인하며 반복

- case. 삼촌 노드 BLACK && 삽입한 노드가 오른쪽 자식

• 부모를 기준으로 좌회전

• 부모였던 노드를 삽입한 노드로 생각하고 아래의 case에 따름

- case. 삼촌노드 BLACK && 삽입한 노드가 왼쪽 자식

• 부모 노드 → BLACK

• 할아버지 노드 → RED

• 할아버지 노드를 우회전
  

삭제연산에 대한 포스팅은 다음에 이어서 :-D