[백준 알고리즘, 자료구조] Tree 정의 및 종류 및 백준 1920 수 찾기 풀이

오늘은 자료구조 Tree 에 대해 알아보려고 한다. Tree에 대해 최근 배웠고, 오늘 푼 알고리즘 문제가 트리와 관련이 있기 때문에 정리하려고 한다.

참고로 B Tree 내용이 많기 때문에 내일 다시 정리하려고 한다. 우선 트리에 대해 정리하고, 마지막에 알고리즘 풀이를 하겠다.

1. 트리의 특징

나무위키 가라사대, 트리는 부모 노드 밑에 자식 노드가 연결되 있고, 자식 노드 밑에 또 다른 자식 노드가 연결되 있는 재귀적 형태의 자료구조를 의미한다.

트리는 그래프의 한 종류로서 각각의 노드들을 연결하는 간선은 하나뿐이며, 비순환형 그래프를 트리라고 부른다. 트리와 그래프를 비교해보자!

그래프	트리
각각의 노드들 사이에 2개 이상의 경로 가능, 양방향 경로 가능	두개의  노드 사이에 오직 한개의 경로만 가능
Self-Loop 및 순환 가능, 루트 존재(X)  부모-자식 관계의 개념 (X)	Self-Loop 및 순환,   오직 한개의 루트 가능하며, 자식 노드는 하나의 부모 노드만 가능
그래프의 순회 : BFS, DFS	그래프의 순회 : Pre Order, In Order, Post Order
순환 혹은 비순환 그래프	오직 비순환 그래프 (Directed Acyclic Graphs 의 한 종류)
네트워크 모델	계층 모델
간선의 유무 및 수는 그래프에 따라 다름	간선 = 정점 - 1

2. 트리의 용어

 - 형제 노드 (Sibling Node) : 부모가 같은 노드

 - 차수 (Degree) : 자식의 수

 - 잎 노드 (Leaf Node) : 차수가 0인 노드이며, 자식 노드가 없는 노드

 - 길이 (Depth) : 루트 노드로부터 자신의 노드까지 경로의 길이 (루트 노드는 0 기준)

 - 레벨 (Level) : 루트 노드로부터 자신의 노드까지 경로의 길이 + 1 (루트 노드의 레벨은 1)

 - 크기 (Size) : 자기 자신 및 자손 노드의 수

3. 이진트리

부모 노드는 자식 노드를 최대 2개만 가질 수 있는 트리를 의미한다. 보통 노드의 값과 노드의 왼쪽/오른쪽 자식노드를 가리키는 참조값을 가지는 형태로 구현한다.

완전 이진 트리 경우에는 배열을 통해 구현이 가능하다. n번째 원소의 왼쪽자식은 2n, 오른쪽 자식은 2n + 1, 부모 노드는 n/2가 된다. 

 - 완전 이진 트리 (Complete Binary Tree) : 트리의 원소를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워나간 형태

 - 포화 이진 트리 (Full Binary Trr) : 모든 트리의 자식 노드의 갯수는 0 (리프 노트) 또는 2 인 형태

이진 트리의 순회 방법은 In Order, Pre Order, Post Order 존재한다. 아래의 그림을 이용해서 확인해보자!

 - In Order : 왼쪽, 부모, 오른쪽 (1 → 3 → 4 → 6 → 7 → 8 → 10 → 13 → 14)

 - Pre Order : 부모, 왼쪽, 오른쪽 (8 → 3 → 1 → 6 → 4 → 7 → 10 → 14 → 13)

 - Post Order : 왼쪽, 오른쪽, 부모 (1 → 4 → 7 → 6 → 3 → 13 → 14 → 10 → 8)

4. 이진 탐색 트리

왼쪽 자식 노드는 보모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 큰 값들로 구성되어 있는 이진트리의 하나의 종류이다. 정렬이 되었기 때문에 

특정 n의 값을 찾을 때, 부모 노드와 비교해서 값이 크다면, 왼쪽 노드에 있는 값들을 비교하지 않고, 오른쪽 노드의 값들로만 비교하면 되기 때문에 탐색의

속도가 빠르다. 삽입/삭제/탐색 모두 시간복잡도가 O(logN)이다. 

왼쪽 자식 노드느에는 노드의 값보다 작은 값들만 있고, 오른쪽 가지에는 큰 값들만 있도록 구성되었다. 자식 노드들도 동일한 방법으로 정렬되어 노드의 왼쪽 자식의 왼쪽 가지에는 왼쪽 자식이 가진 값보다 작은 값만 있고, 왼쪽 자식의 오른쪽 가지에는 왼쪽 자식의 값보다 큰 값들만 있고, 오른쪽 자식의 왼쪽 가지에는… 이런 식으로 이진 탐색 트리의 어느 노드를 잡아도 동일한 규칙으로 정렬이 되어 있다.

이렇게 구성해 두면 어떤 값 n을 찾을 때, 루트 노드와 비교해서 n이 더 작다면 루트 노드보다 큰 값들만 모여 있는 오른쪽 가지는 전혀 탐색할 필요가 없다. 마찬가지로 루트 노드의 왼쪽 자식보다 n이 크다면 왼쪽 자식의 왼쪽 가지는 탐색할 필요가 없고… 다시 말해 트리 자체가 이진 탐색을 하기에 적합한 구성이 되는 것이다. 또한 값을 찾을 때 뿐만이 아니라 값을 삽입하거나 삭제할 때도 똑같은 과정을 거치므로, 이상적인 상황에서 탐색/삽입/삭제 모두 시간복잡도가 O(log N)이 된다. 하지만 최악의 경우 값을 탐색하는데 O(N)의 시간이 소요된다. (예 : 1, 2, 3, 4 ... 순차적인 경우) 이럴 경우에는 트리의 구조가 이루어지지 

않고, 하나의 직선으로 보일 것이며, 선형 탐색이나 다를게 없다. 이러한 경우를 트리가 편향되었다고 하며, 회전을 통해 균형일 맞추는 것이 가능하다. 

참고로 위의 그림이 이진 탐색 트리의 그림이다.

5. Java 구현

            
package Q1920;

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        Set set = new TreeSet<>();
        Stream.of(br.readLine().split(" "))
                .map(s -> Integer.parseInt(s)).forEach(i -> set.add(i));

        int m = Integer.parseInt(br.readLine());
        String[] arr = br.readLine().split(" ");
        for(int i = 0; i < m; i++)
            sb.append(set.contains(Integer.parseInt(arr[i])) ? "1" : "0").append(System.lineSeparator());

        bw.write(sb.toString());
        bw.close();
    }
}

6. 코드설명

 

처음에는 List 자료구조를 활용하였고, Contain() 메소드를 활용해서 숫자의 유무를 확인했다. contain() 메소드의 시간복잡도는 O(n)이기 때문에 문제가 되지

않을거라 생각을 했다. 하지만, 시간초과 오류가 났다. 그렇다면 탐색을 하는데 O(n)보다 더 빠르게 찾아야 한다는 것이고 이럴 경우에는 대체로 O(logN) 이다.

그래서 좀더 빠른 탐색을 지원하는 이진탐색트리 자료구조를 활용하게 되었다. 이진탐색트리는 검색/삭제/삽입의 시간복잡도가 O(logN) 이다.

이진탐색트리를 이용해서 구현을 하니 시간초과를 해결할 수 있었다!