[Datastructure] Map, Set 그리고 Red-black 트리

Map과 Set

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>
> class map;

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class set;

STL의 Map은 unique key들로 key-value 쌍을 저장하는 정렬된 컨테이너이다.
Key들은 Compare라는 함수를 통해 비교되어 정렬된다.

검색, 삽입, 삭제연산은 로그시간의 시간복잡도를 가지고, Map은 RB tree를 통해 구현된다.

반면, Set은 key-value가 아닌 unique key값만을 정렬해 저장한다.

standard library는 Compare 요구사항을 사용하는 모든 곳에서 uniqueness를 == 연산을 통해 확인한다.

STL의 RB tree

gcc4.0.0의 RB tree를 기준으로 작성합니다.
gcc4.0.0에서 map과 set은 stl_tree.h에 구현된 RB_tree의 메서드를 사용해 map과 set의 메서드를 구현한다.

RB tree란

RB tree는 self-balancing binary search tree로, AVL tree와 같이 원소의 삽입, 삭제 시 트리의 높이를 스스로 균형잡는 자료구조이다.
다만, AVL tree의 경우, RB tree보다 엄격하게 균형이 잡혀있어 삽입과 삭제 연산 시, 최악의 경우에 더 많은 rotation이 필요하다.
RB tree는 최악의 경우에도 우수한 실행속도를 보장하며 삽입, 삭제, 검색 연산 시 log N의 시간복잡도를 보장한다.

RB tree 특성

• 이진 탐색 트리(BST)의 특성 + RB tree의 고유한 특성을 모두 만족해야 유효한 RB tree가 된다.

• BST의 특징
  1. 각 노드는 값을 가지고있다.
  2. 값들은 비교될 수 있어야한다.
  3. 노드의 왼쪽 subtree에는 노드의 값보다 작은 값을 가진 노드들로 이루어져있다.
  4. 오른쪽 subtree에는 노드의 값보다 큰 값을 가진 노드들로 이루어져있다.
  5. 좌 우 하위트리는 각각이 1,2,3,4를 만족한다.
• RB tree의 특징
  1. 노드는 R(Red) 혹은 B(Black) 중 1개이다.
  2. root node는 black이다.
  3. 모든 leef node(NIL) node는 B이다.
  4. 모든 red node의 자식은 black이다.
  5. 특정 노드에서 그에 속한 leaf node까지 도달하는 모든 경로에는 leaf node를 제외하고 동일한 수의 Black노드로 이루어져있다.

RB tree의 특징을 만족하는 트리는 5번 속성에 의해 아래와같은 중요한 특징을 가진다.

• 존재하는 모든 경로에 대해 최장 경로의 길이는 최단 경로의 2배이상이 될 수 없다.

Uncle, Grandparent

• rb tree를 구현하기위해서 일단 grandparent, uncle node의 위치를 정의한다.

Sentinel node

• Sentinel node는 Root node와 NILL node에 사용된다.
• 트리의 end point를 나타내기위해 사용되며, Value값이 없는 Node이다.
• ROOT와 END node에 대한 코너케이스를 처리해야하는 필요성을 줄이기 위해 사용한다.

Insert 전략

• Insert하는 노드는 R로 시작한다.

1. Case 1

• Insert 한 노드의 위치가 root라면 Black으로 칠하고, 아니라면 Case2로 이동한다.

1. Case 2

• 부모노드가 Black이라면 모든 red node의 자식은 black이라는 조건을 만족하게된다.
• 부모노드가 Red라면 Case3을 적용한다.

1. Case 3

• Parent와 Uncle이 모두 Red라면 Parent, Uncle을 Black으로, G는 Red로 변경한다.
• 이때, G를 Red로 바꾸면서 root가 Black이어야한다는 특성2와
• G의 부모가 Red일 경우, Red의 모든 자식이 Black이어야한다는 특성4를 만족하지 못하게되기때문에
• Case1 ~ Case3을 재귀적으로 호출한다.

• Case4와 Case5는 같이 생각해야한다.

1. Case 4

• Case4에서는 P가 Red, Uncle이 Black인 경우이다.
• 이때는 N을 기준으로 Right rotation을 한다.
• 다만, N과 P가 모두 Red이므로 특성 4 만족을 위해 Case5를 적용한다.
• tree rebalancing 과정에서 ll, lr, rl, rr case를 나누어서 처리하곤하는데, Case4는 Case5를 위한 조화과정이라고 생각하면된다.
• lr, rl case를 rr, ll case로 만든다.

1. Case 5

• G를 기준으로 Left rotation을한다.
• 그리고

deletion전략

• 이진검색트리에서 삭제연산은 일반적으로 두 개의 non-leaf자식을 가진 노드를 지울때는 자신의 왼쪽 subtree의 최우측 node 혹은 오른쪽 subtree의 최좌측 node를 복사해서 insert한다.
• 이때 복사된 node를 지우게되는데, 이 node는 반드시 1개 이하의 자식을 가진다.(최우측, 최좌측이면 당연함)
• rb tree에서는 삭제한 주변 노드가 특성을 위반하는지 여부를 확인해야한다.

자, 첫 번째로 삭제하는 노드를 대체해보자.
3가지 경우로 나눌 수 있는데,

1. 삭제하고자하는 노드의 LEFT가 NULL인 경우
2. 삭제하고자하는 노드의 RIGHT가 NULL인 경우
3. 삭제하고자하는 노드의 LEFT, RIGHT가 모두 NON-NULL인 경우이다.

• 이후에는 rb tree의 특성에 맞춰 rebalancing작업을 한다.

• 주변 노드가 특성을 위반하는지 여부는 삭제된 노드의 원래 색이 검은색인가?이다.
  • 삭제된 node의 색이 black이라면, 해당 경로의 black height와 해당 경로를 통과하지 않은 다른 경로의 black height가 달라지게된다.
• 이때, 총 4가지의 경우가 있다.
  • 현재 대체된 노드를 x라 가정할때, x의 sibling을 w라고 하자.
    1. w 색이 red일때,

1. w가 black, w의 right, left가 모두 black

1. w가 black, w의 left가 red, w의 right가 black

1. w가 black, w의 right가 red

• 1 ~ 4 절차가 끝난 후에, x를 black으로 업데이트한다.

STL에서 RB tree

• stl의 RB tree는 크게 6가지 class와 tree에서 연산을 구현한 7개의 메서드로 이루어져있다.
• 클래스
  1. sentinel node를 표현하는 node_base클래스
  2. value값을 가지는 node클래스
  3. iterator 클래스
  4. const iterator 클래스
  5. tree color 클래스
  6. 위의 클래스를 이용해 impl을 선언해서 사용하는 tree 클래스
• 메서드
  1. root와 node를 받아 현재 node로부터 부모까지의 black node를 계산하는 black_count 메서드
  2. iterator 구현을 위해 tree에서 현재 노드의 값 바로 다음의 값을 찾는 increment 메서드
  3. decrement
  4. insert한 후 rebalance하는 메서드
  5. left rotate
  6. right rotate