📗[CS/DataStructure] 트리

트리의 정의

• 트리란?
  • 임의의 두 노드를 연결하는 단순 경로가 정확히 하나 존재하는 그래프
    • 단순 경로 : 같은 노드를 2번 이상 지나지 않는 것.
• 다음과 같은 조건을 만족하면 트리🌲
  • ① 모든 노드가 하나의 연결 요소
    

    

    위 그래프는 트리가 아니다.

  • ② 사이클이 없어야 한다.
    

    

    위에는 트리가 아니다.

  • ③ 노드의 개수가 간선의 개수보다 하나 많다.
    ex) 노드가 3개면 간선은 2개
• 1번, 2번 조건을 만족하면 3번 조건도 만족할 수밖에 없다. (간선이 N개가 되면 무조건 사이클이 생길 수 밖에 없음)
  • 2번, 3번 조건을 만족하면 1번 조건도 만족하고, 1번, 3번 조건을 만족하면 2번 조건도 만족한다.
  • 즉, 위 조건 중 2개가 문제에 나오면 트리라고 생각하면 된다.
    ex) 두 도시를 지나는 경로는 정확히 하나 존재 ⇒ 트리
    ex) 어떤 두 도시를 잡을 때 그 경로가 무조건 존재하고, 도로의 개수는 도시의 개수보다 하나 적다 ⇒ 트리
• 트리가 모이면 ? forest 🌲🌲🌲
  • 2번 조건만 만족하는 그래프는 forest
  • 각 연결 요소가 트리라는 점을 이용할 수 있다.

 

Rooted tree

• 우리가 익숙한 트리
  

  

• 일반 트리는 그래프
  • 일반 트리를 만족하는 정보가 주어지면 그 정보를 기반으로 rooted tree로 만드는 작업을 해야 한다.

• 용어 정리
  • 루트 : 가장 상위에 위치한 노드
  • 리프 : 자식 노드가 없는 노드
  • 부모 : 어떤 노드의 바로 위에 있는 노드(루트 노드를 제외한 노드들은 무조건 부모 노드 하나씩 갖고 있다.)
  • 자식 : 어떤 노드의 바로 아래에 있는 노드
  • 조상 : 어떤 노드의 루트 까지의 모든 경로에 있는 노드
  • 깊이 : 어떤 노드가 루트 노드로부터 얼마나 떨어져 있는지
    ex) 루트 노드는 깊이가 0 또는 1(문제에 명시 됨) → 아래로 내려갈수록 깊이가 1씩 증가
  • 높이 : 트리의 최대 ‘깊이’
  • 서브트리 : ‘몇 번 노드가 루트인 서브트리’, 원래 트리의 일부분을 포함하는 작은 트리
• 그래프 크기 = 노드의 개수
• 탐색은 dfs로 한다. ⇒ O(N)에 모든 노드에 대해 아래 정보를 모두 구할 수 있다.
  (1) 각 노드의 부모 노드 구하기 + 자식 노드 구하기
  (2) 각 노드의 깊이 구하기
  (3) 각 노드가 루트인 서브트리의 크기 구하기

BOJ 11725. 트리의 부모 찾기

• 문제 요약 : 루트 없는 트리가 주어졌을 때, 루트를 1로 정할 때, 각 노드의 부모 노드 구하기
• 문제 해결
  • 주어진 정보로 일반 트리(그래프)를 만든다.
  • 해당 그래프에서 dfs를 돌린다. ⇒ 루트 노드부터 진행
    • 루트에서 dfs를 돌게 되면 부모에서 자식으로 탐색하게 된다.
    • 방문처리를 다르게 하는 법
      • 매개변수에 cur(현재 방문한 노드)를 같이 넘겨 준다. 즉, 다음 노드한테 이전에 어떤 노드였는지 알려줌.
    • 탐색하면서 각 노드의 부모 노드 기록하기
      • par[nxt] = cur

① 각 노드의 부모 노드 구하기

static void dfs(int cur, int prv) {
    for (Integer nxt : list[cur]) {
        if (nxt == prv) continue;

        parent[nxt] = cur;
        dfs(nxt, cur);
        // parent[nxt] = cur; 여기에 추가해도 됨 
    }
}

 

② 각 노드의 자식 노드 구하기

static void dfs(int cur, int prv) {
    for (Integer nxt : list[cur]) {
        if (nxt == prv) continue;

        child[cur].add(nxt);
        dfs(nxt, cur);
    }
}

 

③ 각 노드의 깊이 구하기

static void dfs(int cur, int prv) {
    for (Integer nxt : list[cur]) {
        if (nxt == prv) continue;

        depth[nxt] = depth[cur] + 1;
        dfs(nxt, cur);
        // depth[nxt] = depth[cur] + 1; 이거는 여기에 추가하면 안 됨
	        // 다음 dfs에서 +1 된걸 사용해야 하니까
    }
}

 

④ 각 노드가 루트인 서브트리의 크기 구하기

static void dfs(int cur, int prv) {
    size[cur] = 1; // 나는 무조건 존재하기 때문에 1로 초기화

    for (Integer nxt : list[cur]) {
        if (nxt == prv) continue;

        dfs(nxt, cur);
        size[cur] += size[nxt]; // 나의 자식노드 서프트리 사이즈를 더해준다.
        // 나의 서브트리에 대한 정보가 궁금하다면 dfs 아래에 위치
        // 루트노드부터 조상에 대한 정보가 궁금하다면 dfs 위에 위치
	      // 서브트리 크기는 서브트리에 대한 정보이니까 dfs 아래에 위치해야 한다.
    }
}

 

⑤ 서브트리의 높이가 궁금하다면?

static void dfs(int cur, int prv) {
    for (Integer nxt : list[cur]) {
        if (nxt == prv) continue;
        
        dfs(nxt, cur);
        height[cur] = Math.max(height[cur], height[nxt] + 1);
    }
}

 

BOJ 15681. 트리와 쿼리

• 문제 요약 : 각 노드의 서브 트리의 크기 구하는 문제

BOJ 26159. 트리와 수열

• 문제 요약 : N개의 정점이 주어지고, 각 노드간 연결 정보와, N-1개의 음이 아닌 값인 수열이 주어진다. 이때, 두 노드를 선택 했을 때 두 노드 간 경로의 가중치 합이 가장 최소가 되는 경우의 값 구하기.
• 문제 해결
  • 간선 별로 몇 번 쓰이는지 체크
      ⇒ 어떻게 구할까? 해당 간선을 기준으로 (좌측 노드 개수) * (우측 노드 개수)
  • 그런 이걸 간선 별로 어떻게 구할까?
      (1) rooted tree로 만든다.
      (2) 각 노드별 서브트리 크기를 구한다. ⇒ 이 정보를 기준으로 간선이 몇 번 쓰이는지 값들을 구할 수 있다.
  • 이때 많이 쓰이는 간선 순서대로 가중치를 작은 것부터 배치하기

 

트리의 지름

• 트리의 지름은 트리 내의 두 노드 간의 가장 긴 경로의 길이를 의미
  • 가중치가 없다면 간선 개수, 가중치가 있다면 가중치를 가지고 트리의 지름을 구할 수 있다.
• 구하는 방법?
  • 임의의 노드를 선택해서 dfs로 제일 먼 노드(V)를 찾는다.
  • 그 다음 해당 노드(V)를 기준으로 dfs로 제일 먼 노드를 찾는다.
  • 아무 노드에서나 제일 먼 노드를 찾아주면, 그 노드가 지름에 속해 있다. 따라서 아무 노드에서 dfs를 한 번 돌려서 제일 먼 노드를 찾고, 거기서 다시 dfs로 제일 먼 노드를 찾으면 그 사이가 지름이다.

public class Main {
    static int N;
    static ArrayList<Integer>[] list;
    static int max, idx;


    static void dfs(int cur, int prv, int d) {
        if (max < d) {
            max = d;
            idx = cur;
        }

        for (Integer nxt : list[cur]) {
            if (nxt == prv) continue;

            dfs(nxt, cur, d + 1);
        }
    }

    public static void main(String[] args) throws  IOException{
        ``` 생략 ```
        
        dfs(1, 0, 0);
        max = -1;
        dfs(idx, 0, 0);
				
        System.out.println(max);
    }
}

 

 

LCA (Lowest Common Ancestor, 최소 공통 조상)

• 두 노드의 공통 조상 중에서 가장 깊이 있는 노드를 의미
  • 즉, 공통 조상 중에서 가장 가까운 조상 노드 찾기
• 구현 방법
  
  • ① 각 노드마다 위로 올라가면서 조상 노드를 리스트에 순서대로 기록
    
    • 그러면 가장 가까운 조상 노드부터 기록된다.
  • ② 그 다음 2중 for문을 돌면서 두 노드의 조상 노드를 담은 리스트의 값을 비교하면 공통 조상 노드를 찾을 수 있음
    • 가장 가까운 걸 찾는 거니까 최초로 공통 조상이 나오면 그게 LCA
    • 2중 for문을 사용하니까 시간복잡도가 O(N*N)이 나옴
      • 시간 복잡도 줄이기
        방법1. 정렬 후 이진 탐색 돌리기 => O(NlogN)
        방법2. 트리의 특성을 이용해서 다음과 같이 풀 수 있다 => O(N)
        
        • 두 리스트의 마지막 노드는 루트 노드가 될 것(그 가음은 깊이가 1, 2, 3,... 인 노드를 순차적으로 보게 됨)
        • 역순으로 비교하다가 서로 다른 노드를 발견하게 되면 그 직전 노드가 LCA
          
          • 즉, 한번 LCA를 발견하면 그 노드부터 루트 노드까지는 게속 공통 조상 노드가 되니까!
        
        

        

 

이진 트리

• 어떤 노드도 3개 이상의 자식을 갖지 않는 트리 (모든 노드가 2개 이하의 자식노드만을 가짐)
  
  

  

•  용어
  • 왼쪽 자식
  • 오른쪽 자식
    ⇒ 왼쪽, 오른쪽에 의미를 부여해서 트리를 구성할 수 있음
    ex) 나보다 작은 애는 왼쪽, 큰 애는 오른쪽
• 전위 순회, 중위 순회, 후위 순회 
  ① 완전 이진 트리를 배열을 이용해 구현하는 방법
  ② 전위 순회 + 중위 순회 or 후위 순회 + 중위 순회로 트리 복구하기
  ③ 중위 순회의 의미 : 왼쪽 - 뿌리 - 오른쪽
  
  • 이진 탐색 트리에서는 정렬된 배열 출력