Red/Black_Tree

Red-Black tree(레드-블랙 트리)는 자가 균형 이진 탐색 트리로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조라고 한다. 레드-블랙 트리는 복잡한 자료구조지만, 실 사용에서 효율적이며 최악의 경우에도 O(logN) 시간복잡도를 보장할 정도로 안정(balanced)되었다.

1. 균형 이진 탐색 트리란?

• 기존 이진 탐색 트리는 각 노드가 모두 자식 노드가 2개인 경우 노드 하나를 찾는 데 시간 복잡도 O(log n) 을 보장한다.
  

• 그러나 각 노드가 한쪽 노드에만 자식이 있어서 선형 구조가 되어버리면 시간 복잡도 O(n)이 된다.
• 최악의 경우에도 O(logn) 시간복잡도가 유지되도록, 이진 탐색 트리의 균형을 맞추는 작업을 하는 것.
• 균형 이진 탐색 트리의 종류로는 2-3Tree, AA Tree, AVL Tree, B-Tree, Red-Black Tree, Scapegoat Tree 등이 있다.

2. RBTREE 특성

1. 모든 노드는 red or black
2. root node는 black
3. 모든 leaf node(NIL)는 black
4. 노드가 red일 때, 자식 노드는 모두 black이다. (즉 레드 노드는 연달나 나타날 수 없다)
5. 임의의 노드에서 자손 nil nodes까지 가는 경로들의 black 수는 같다(자기 자신은 카운트에서 제외)
   

#5는 모든 leaf node(NIL)는 자기 위치에서 루트까지 올라가는데 만나는 검은색 노드의 수가 같다는 말이다. NIL노드는 검은색 데이터만 가진 더미 노드인데, 자식 노드가 없는 경우에 NIL을 할당해준다. 이렇게 하면, #3을 항상 유지할 수 있다.

3. RBTREE 기본연산

삽입과 삭제 시 주로 #4 #5 특성을 위반한다. 몇몇 노드의 색을 바꾸거나(색상 전환) 포인터 구조를 바꾸다 보면 자연스럽게 트리의 균형이 잡히게 된다. 이러한 작업을 로테이션이라고 한다.

삽입

기본적으로 삽입하면서 새로 생성되는 노드는 'red'이다(루트는 예외). 신규 노드가 삽입되면서 레드 노드가 연속으로 나타나서 rbtree의 4번 특성을 위반할 수 있다.

• case 1: 부모 노드가 레드인데, 부모의 형제가 없거나 블랙일 때 - 회전
• case 2: 부모 노드가 레드인데, 부모의 형제가 레드일 때 - 색상 변환

부모 노드 기준에서 좌측과 우측의 블랙 노드 개수가 맞지 않게 된다. 이 때는 형제 노드를 레드로 색상 변환하고 부모 노드는 블랙으로 바꾸면 된다.

RB트리가 #5 속성을 만족하고 있고, 두 자녀가 같은 색을 가질 때, 부모와 두 자녀의 색을 바꿔줘도 #5 속성은 여전히 만족한다.

삭제

삭제한 노드가 red일 때는 rbtree의 특성을 위배하지 않는다. 하지만 black일 때는 5번 특성을 위반할 수 있다.

삭제하려는 노드가 블랙이고 자식이 레드라면 자식 노드를 색상 변환하면 해결되지만, 자식 노드도 블랙이면 위에서 말한 것 처럼 #5 속성을 어기게 된다.

(삭제하려는 노드x가 부모의 왼쪽 자식인 경우)

• case 1: x의 형제 노드w가 레드인 경우
  • 형제노드와 부모노드를 색상변환한다. 형제 노드는 black, 부모노드는 red가 된다. 그리고 부모 노드를 기준으로 left 회전을 한다.
  • 형제노드가 블랙인 상황이 되어, case 2,3,4로 해결한다.
• case 2: x의 형제 노드가 블랙이고, w의 두 자식이 모두 블랙일 때
  • 형제노드와 부모노드를 색상변환한다. 형제 노드는 red, 부모노드는 extra black이 추가되었다.
  • 원래 부모가 red였다면 red_and_black이 되어 black으로 변환해주면 된다. 하지만 black이었다면 doubly black이 되어 문제 노드가 된다.
  • 부모노드로 시점을 옮겨 루프를 반복한다.
• case 3: x의 형제 노드가 블랙이고, w의 왼쪽 자식이 레드일 때
  • 형제노드와 형제노드의 왼쪽자식을 색상변환한다.
  • 그리고 형제 노드를 중심으로 right 회전을 하면, case 4와 같은 상황이 된다.
• case 4: x의 형제 노드가 블랙이고, w의 오른쪽 자식이 레드일 때
  • 형제노드와 부모노드를 색상변환한다.
  • 부모노드 중심으로 left 회전을 한다.
  • 이 과정에서 x의 extra black이 삭제되고 문제노드가 사라져, 시점을 root로 옮긴다.