[백준] 2957 이진 탐색 트리 java, 이해하기

1. 문제 설명 📌

문제 설명

2. 접근 방식 🗃️

KEY WORD: BLACK-RED TREE, BST(Binary_Search_Tree)

• (0) BLACK-RED TREE 로 구현된 TreeSet을 활용한다.
• 일반 BST일 때의 Depth를 저장하는 int [] depth 배열도 만든다.

• (1) TreeSet에 0과 N-1을 넣는다. (Null Pointer Exception 방지)
  depth[0]과 depth[N-1] 의 값은 -1을 넣는다. (계산에 영향을 주지 않기 위함)
• (2) TreeSet에 root 노드부터 끝노드까지 차례로 조회한다.
  조회했을 당시의 해당 노드보다 작으면서 최대값과 크면서 최소값인 노드가 무엇인지 구한다.
• (3) depth[현재 노드] = (2)에서 구한 둘 중 depth 값이 더 큰 값 + 1 이다.

• (4) 노드들을 순회하며 그떄의 depth를 구하고 그것의 누적값을 출력하면 된다.

(0) BST 구현하면 안됨?

안된다. 최악의 경우, 데이터 300,000개가 내림차순 혹은 오름차순으로 입력될 것이다. 이 경우 BST의 시간복잡도는 O(N)이 되는데, 이것이 단발적인 것이 아니라, 첫번째 값 삽입 : O(1), 두 번째 값 삽입 O(2), 세 번째 값 삽입 O(3)로 점차 연산횟수가 증가한다. 즉 $O(\frac{N*(N+1)}{2})$ 즉 $O(N^{2})$가 되므로 시간 초과가 난다.

(1) BST 말고 BLACK-RED TREE 써도 됨?

문제에서 바라는 건 BST에서의 비교 횟수 누적 출력 인데, BLACK-RED TREE를 써도 되는가?

이러한 의문이 들 수 있다. 결론은 실제 TREE 모양을 활용하는 것이 아니라, 비교횟수만 봄으로 상관없다 이다.

a. BLACK-RED TREE 란? ✨

BLACK-RED TREE는 자가 균형 Tree 로서 BST에서 비효율적으로 깊이가 깊어지는 것을 내부 규칙을 통해 방지하여, 정렬된 데이터를 유지하면서도 효율적인 삽입, 삭제, 조회를 가능하게 하는 Tree 이다.

왼쪽이 일반 BST이고, 오른쪽이 BLACK-RED TREE 이다. BST에서는 위와 같이 오름차순 내림차순 데이터가 입력으로 들어오면 O(N)의 삽입 시간이 들지만, BLACK-RED TREE는 저러한 경우에도 O(logN)이 든다.

둘의 모양새가 이렇게 다른데, 어떻게 활용해야 할까?

b. C는 한번의 조회에서 얼마나 증가하는가?

C는 현재 조회 중인 노드의 깊이 만큼 증가한다. 현재 조회중인 Node의 깊이는 해당 NODE가 들어가기 전, 그 NODE와 가장 가까운 노드의 깊이 + 1이다.

위의 왼쪽 예시에서도 2를 넣을 때는 depth 0의 1보다 한칸 깊어져서 c += 0 + 1 하면 되었고, 3을 넣을 때는 depth 1인 2보다 한칸 깊어졌으니, c += 0 + 1 + 1, 4를 넣을 때는 depth 2인 3보다 1 높아져 c+= 0 + 1 + 1 + 1을 해주면 된다.

깊이는 달리보면, 해당 노드가 깊어질 때까지의 비교횟수와 같은 말이다. 왼쪽 예시를 보면 4는 3번의 비교를 거쳐 자리를 잡았고, 3은 2번의 비교를 거쳐, 2는 한 번의 비교를 거쳐 자리를 잡았다. 이것 또한 누적으로 나타내면
4는 노드 3의 비교 횟수 + 1만큼 비교해서 자리를 잡았고, 3은 노드 2의 비교횟수 + 1만큼 비교해서 자리를 잡았고, 2는 노드 1의 비교횟수 + 1만큼 비교해서 자리를 잡았다.

따라서 내가 하고 싶은 말은 가장 가까운 노드의 비교횟수 + 1을 C에 더해가면 된다는 것이다. 이는 B-R Tree에서도 노드 각각의 누적된 비교횟수는 BST와 같다. 따라서 B-R Tree를 쓰며, 조회하는 값마다 가장 가까운 노드의 비교횟수 + 1씩 해나가면 된다.

c. 가까운 노드가 2개일 수 있는데, 이건 어떻게 함?

만약 현 노드가 5이고 4와 6이란 노드가 동시에 존재할 수 있다. 이때는 비교 횟수가 더 높은 값의 비교 횟수를 쓴다. 왜냐하면 비교를 더 많이 한 것이 깊이가 더 깊다는 소리이고, 현재 삽입된 값은 리프노드에 가깝게 배치되기 때문이다.

(2) 0과 N-1을 넣는 이유

가장 가까운 노드 2개를 출력해야 하는데, 삽입하는 값이 당시의 최소값 혹은 최대값이면, NullException이 발생하기 떄문이다. 둘의 depth를 -1로 설정하면, 우리는 비교 횟수가 더 높은 값만 사용하기에, 계산에서 걸림돌이 되지 않는다.

(3) 직접 해보기

사실 나도, BLACK-RED TREE가 익숙치 않고, 공유된 답변이 내 의문점을 시원하게 해소해주지 않아서 직접 해보면서 직관적으로 익혔다. 아직도 BLACK-RED TREE와 BST 모두 노드마다 누적된 비교횟수가 같은 이유는 해설하지 못하겠다. 하지만 예시를 직접 해보면서 대략적으로나마 이해를 하긴 했다.
다음은 입력이 2, 11, 4, 12, 6, 13, 8,14, 10, 15, 1, 16, 3, 17, 5, 18, 7, 19, 9로 들어갔을 때 BST와 BLACK-RED TREE의 모양이다.

샌프란시스코 대학에서 그래프 비주얼라이져를 만들어서 무료로 올려놓았다 ㅠㅠ 이걸 쓰면 예시 들며 이해하기 쉬우니 직접 해보며 익히길 바란다. 다음은 링크다.

 

https://www.cs.usfca.edu/~galles/visualization/BST.html

Binary Search Tree Visualization

 

 

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

Red/Black Tree Visualization

 

3. 코드 소개 🔎

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;

public class Main {
    static int N;
    static long sum = 0;
    static int [] depth = new int [300002];
    static TreeSet<Integer> BST = new TreeSet<>();

    public static void main(String[] args) throws IOException {
        StringBuilder answer = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        BST.add(0); BST.add(N+1);
        depth[0] = -1; depth[N+1] = -1;
        for (int i = 0; i < N; i++) {
            int now = Integer.parseInt(br.readLine());
            depth[now] = Math.max(depth[BST.lower(now)], depth[BST.higher(now)]) + 1;
            BST.add(now);
            sum += depth[now];
            answer.append(sum).append("\n");
        }
        System.out.println(answer.toString());
    }
}

4. 배운 것들 🎯

BLACK-RED TREE에 대략적으로나마 이해한 것 같다.