[백준] No.2957 - 이진 탐색 트리 (C++)

문제

 

www.acmicpc.net/problem/2957

2957번: 이진 탐색 트리

 

 

풀이

 

solved.ac 난이도: Platium 5

 

일단 문제에서 주어지는 의사 코드(pseudo code)로 구현해보았다.

 

int counter =0;
 
class Node{
  public:
  int num;
  Node* parent;
  Node* left = nullptr;
  Node* right = nullptr;
 
  Node(Node* p, int n): parent(p), num(n) {}
 
  void Insert(int x){
    ++counter;
    if(x<num){
      if(left ==nullptr)
        left = new Node(this, x);
      else
        left->Insert(x);
    }else{
      if(right ==nullptr)
        right = new Node(this,x);
      else
        right->Insert(x);
    }
  }
 
};

 

하지만 역시나 skewed binary tree(사향 이진 트리, 한쪽으로 노드가 치우쳐진 트리)가 예제 입력으로 주어지는 경우 시간 초과가 발생한다. 따라서 skewed한 트리를 방지하기 위해 적절히 이진 트리의 균형을 맞춰주는 자료구조를 사용하자.

 

map은 red-black tree( 자가 균형 이진 탐색 트리(self-balancing binary search tree))로 이루어져있다. 

red-black tree에 대해서는 ZeddiOS님의 게시글을 참조하자.

Red-Black Tree - ZeddiOS

 

즉, map을 이용하면 예제 입력이 skewed하게 주어지더라도 O(logN)의 복잡도로 값을 찾을 수 있다.

 

이제 다시 문제로 돌아가서 의사 코드를 살펴보자.

카운터 C값은 무엇을 의미할까?

 

카운터 값은 insert()함수가 한번 호출될 때마다 1씩 증가한다.

insert 함수는 x값을 삽입할 자리를 찾기 위해 현재 노드의 값과 비교하여 삽입할 곳이 아니라면 재귀호출로 하위 노드로 한 칸씩 이동한다.

즉, insert가 호출될 때마다 현재 노드의 깊이는 1씩 증가한다.

따라서 카운터 C는 x가 트리에 삽입되는 곳의 깊이를 의미한다.

 

또 다른 이진 검색 트리 자료구조인 set을 이용한다면 각각의 x값을 저장할 수 있겠지만 set에 저장된 값들은 자동으로 균형이 맞춰지기 때문에 의사 코드와 같은 형태의 트리를 이루지 않는다.

그렇기에 기존의 트리에서 x가 삽입될 곳의 깊이를 set으로는 구할 수는 없다.

 

하지만 map 자료구조에는 key와 value값, 두 값을 저장할 수 있다.

따라서 key로는 x의 값, value에는 기존 트리에서의 x가 삽입될 깊이(dep)를 저장하자.

 

 

low_node을 트리에서 x보다 작은 값 중에 가장 큰 값의 노드

up_node을 트리에서 x보다 큰은 값 중에 가장 작은 값의 노드라고 할 때

 

x가 삽입될 dep은 아래와 같다.

dep = max(low_node의 dep, up_node의 dep) + 1

 

왜냐하면 의사 코드에서처럼 x가 삽입 연산을 거칠 때 자신의 위치를 찾기 위해 노드의 num이 자신보다 크다면 왼쪽 노드로, 자신보다 작다면 오른쪽 노드로 이동한다. 하위 노드로 이동하기 위한 재귀 호출을 반복하다 x가 삽입되는 경우(이를 최종 분기라고 하자)는 왼쪽이나 오른쪽에 더 이상 재귀 호출할 하위 노드가 없는 경우다.

 

최종 분기에서 결국 현재 노드의 num보다 x가 작다면 x는 현재 노드의 왼편에 삽입될 것이다.

(만약  x보다 작은 값 중에 가장 큰 값 현재 노드가 아니라면 노드의 오른쪽 편에 해당 노드가 있을 것이고 이는 재귀 호출에서 이미 끝까지 서칭 되었을 것이다.)

이때의 현재 노드는 up_node를 의미한다.

 

반대로 num보다 x가 크다면 x는 현재 노드의 오른편에 삽입될 것이다.

이때의 현재 노드는 low_node를 의미한다.

 

두 노드 모두 x를 하위 노드로 가질 가능성을 지닌다.

그렇다면 어째서 두 노드의 깊이 중 더 큰 값을 사용할까?

 

일단 up_node보다 low_node가 깊이 있는 경우를 생각해보자.

x는 low와 up사이의 값일 것이다.

그렇다면 적어도 x는 up보다 클 수가 없다.

따라서 x가 up의 오른쪽에 삽입될 수 없고 x보다 작지만 가장 큰 low의 오른편에 삽입될 것이다.

따라서 x가 삽입되는 깊이는 low_node의 dep +1이다.

 

반대로 low_node보다 up_node가 깊이 있는 경우도 같은 이유로

더 깊은 up_node의 dep +1 이 x가 삽입될 깊이이다.

 

그렇다면 위와 다르게 up_node와 low_node가

서로 다른 서브 트리에 존재한다면 어떻게 할지 의문이 생길 수 도 있다.

하지만 이러한 경우는 불가능하다.

 

 

만약 위처럼 root의 왼쪽 서브 트리의 어딘가에 low_node가 존재하고 

오른쪽 서브 트리의 어딘가에 up_node가 존재한다고 생각해보자.

하지만 root 노드의 하위 노드들에서 low_node(x보다 작은 값 중에 가장 큰 값의 노드)와 up_node(x보다 큰은 값 중에 가장 작은 값의 노드)가 동시에 존재할 수 없다.

root와 x는 모두 low_node와 up_node사이의 값이다.

따라서 root 노드가 low_node가 되거나 up_node가 되는 트리만 존재한다.

 

이제 map의 x보다 큰 값 중 가장 작은 값의 iterator을 반환하는 upper_bound(x) 함수를 이용하여 해당 풀이를 구현하자.

이때 미리 tree에 미리 0과 300001 값을 넣어두면 x보다 작은 값이 없거나 큰 값이 없는 경우의 예외처리를 해주지 않아도 된다.

 

코드