map stl 시간초과 이슈

[gyurim]

백준 10816번 문제를 풀다가 map으로 구현한 뒤, 이분 탐색(lower_bound)으로 풀었을 때는 시간초과가 나고, 배열을 sort한 후 이분 탐색 (lower_bound, upper_bound)으로 풀었을 때는 성공함. -> 왜 이런 결과가 났을까?

map은 red black tree로 구현이 되어있다. 따라서 이진 탐색 트리와 red black tree 비교해보자.

이진 탐색 트리

개념

• 각 노드의 왼쪽 서브 트리에는 해당 노드의 값보다 작은 값을 가진 노드들로 이루어짐
• 각 노드의 오른쪽 서브 트리에는 해당 노드의 값보다 큰 값을 가진 노드들로 이루어짐

탐색

• leaf 노드를 만날 때까지 혹은 원하는 값을 찾을 때까지 이진 탐색 트리를 내려가며 탐색한다.
• 탐색의 시간 복잡도는 O(h) : 트리의 높이(루트 노드에서 leaf 노드에 이르는 엣지의 수의 최대값)
• 그러므로 이진 탐색 트리가 균형 상태라면 O(h) = O(logN), 불균형 상태라면 O(h) = O(N) 시간이 걸린다.

삽입

• 새 노드는 항상 leaf 노드에 삽입된다.
• 시간 복잡도는 O(h) : 삽입할 위치를 찾는데 걸리는 시간, O(1): 삽입 시간

삭제

• 시간 복잡도는 (3) 삭제할 노드에 값이 둘 있는 경우에 해당하는 계산량을 따른다.
• 삭제할 노드의 레벨이 d일 때, 1단계에서 d 번의 비교 연산이 필요하므로 O(d) -> 2단계에서 삭제 대상 노드의 서브 트리 높이(h-d)에 해당하는 비교 연산이 필요하므로 O(h-d) -> 총 O(d+h-d) = O(h)

(1) 삭제할 노드가 leaf 노드인 경우

• 해당 노드 삭제해주면 됨

(2) 삭제할 노드에 자식이 하나 있는 경우

• 삭제할 노드의 부모와 자식을 연결해주면 됨

(3) 삭제할 노드에 자식이 둘 있는 경우

• successor 노드 값과 삭제할 노드의 값을 바꿔준 뒤, successor 노드를 삭제
• successor 노드?
  • 삭제할 노드의 오른쪽 서브 트리에서 최소값
  • 즉, inorder(중위) 순회에서 다음 노드를 말함
• 과정
  • 1단계) 삭제 대상 노드의 오른쪽 서브 트리를 찾는다.
  • 2단계) Successor 노드를 찾는다.
  • 3단계) 2에서 찾은 successor의 값을 삭제 대상 노드에 복사(바꿈)
  • 4단계) Successor 노드를 삭제

한계점

• 이진 탐색 트리의 연산은 O(h)이다. 그러나 불균형한 이진 트리의 경우, O(h) = O(n)이 되기 때문에 결론적으로 이진 탐색 트리의 계산복잡도는 O(n)이 된다.
• 따라서, 트리 전체의 균형을 맞추는 AVL Tree 제안됨

Red Black Tree

개념

• 이진 탐색 트리의 일종이다. 단 아래의 속성을 만족해야함.
  • 1. 모든 노드는 빨간색, 검은색 둘 중 하나이다.
  • 2. 루트 노드는 검은색이다.
  • 3. 모든 leaf 노드는 검은색이다.
  • 4. 어떤 노드가 빨간색이라면 두 개의 자식 노드는 모두 검은색이다.
  • 5. 각 노드로부터 그 노드의 자손인 leaf 노드로 가는 경로들은 모두 같은 수의 검은색 노드를 포함한다.

탐색

• 이진 탐색 트리의 탐색 방법과 같음
• 시간 복잡도 O(logN)

삽입

• 1단계) 이진 탐색 트리의 특징대로 삽입 후, 삽입 노드의 색깔을 빨간색으로 설정한다.

• 2단계) 삽입 후, Red Black Tree의 특징을 위반할시, 노드의 색깔을 조정하고, Black-Height가 위배되었다면 restructuring을 통해 height를 조정

• 새로 삽입할 노드를 z라고 가정

• 시간복잡도는 O(logN)

(1) z의 삼촌이 빨간색 -> Recoloring

• 1단계) z의 부모와 z의 삼촌 노드를 red -> black으로 변경하고, z의 할아버지 노드를 black -> red로 변경
• 2단계) z의 할아버지 노드의 부모 노드가 빨간색인 경우, 위의 과정을 반복한다.
• 3단계) z의 부모가 검은색을 만날 때 종료되며, 루트까지 올라가게 되면 루트 노드를 검은색으로 바꾸고 종료

(2) z의 삼촌이 없거나 검은색 -> Rotation & Restructuring

• 1단계) z 노드, z 노드의 부모, z 노드의 할아버지 노드를 오름차순으로 정렬
• 2단계) 중앙값을 부모 노드로 만들고 나머지 노드를 자식으로 변환
• 3단계) 부모 노드가 된 노드를 검은색으로, 나머지 노드를 빨간색으로 변경

삭제

• 삽입 연산과 유사한 방식으로 rotation을 구현함으로써 해결 가능
• 빨간색 노드를 삭제할 때는 그냥 삭제를 수행하면 됨
• 시간복잡도는 O(logN)

특징

• AVL 트리가 Red Black Tree보다 탐색이 빠르다.
  • AVL 트리가 더 엄격한 균형을 유지하기 때문
• Red Black Tree는 AVL 트리보다 빠른 삽입과 제거를 제공

백준 문제와 비교해서 생각해보기

• map이나 set은 red black tree 자료구조를 사용하는데 이는 시간복잡도는 log를 보장해주지만 상수가 매우 큰 자료구조이다.
• 특히 삽입/삭제 연산에서 상당히 많은 작업이 들어갈 수 있음.
• 따라서, 입력을 한 번에 받고 나중에 정렬하는 것이 훨씬 빠르다.