[코딩 테스트 합격자 되기 C++ 스터디] STEP 4. 트리

인프런 강의 링크: https://inf.run/DuvN7

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런

4주 차

스터디 일자: (2024. 07. 28(일) ~ 2024. 08. 03(토))

 

시작에 앞서

DB에서 자주 나오는 B-Tree, Red-Black Tree, AVL Tree 개념 외에도 트리를 사용한 다양한 알고리즘이 있다

트리에 관한 문제는 많이 풀어보진 않았지만 이번 기회에 개념을 정리하고 넘어가면 좋을 듯 하다

 

---

1. 트리 개념

트리는 노드와 간선으로 이루어진 비선형적, 계층적 자료구조이다

상위 노드는 부모로, 하위 노드는 자식으로 부를 수 있다

 

그래프와 같으나 사이클이 존재하지 않고, 계층이 존재한다

자식이 없는 맨 마지막 노드는 리프 노드(단말 노드, 터미널 노드)라고 부른다

자식의 수는 해당 노드의 차수이다

 

자식이 있는 노드는 비단말 노드라고 부른다

 

부모가 없는 최상위 노드는 루트 노드라고 부른다

(루트 노드 딸랑 하나 있으면 루트 노드이면서 단말 노드이고, 자식이 하나라도 있으면 루트 노드이면서 비단말 노드일 것)

 

레벨은 각 층의 depth, 깊이를 말하며 위에서부터 0 또는 1에서 시작한다

트리의 높이는 트리의 최대 레벨을 의미한다

 

2. 이진트리 표현

이진 트리에서 루트 노드의 인덱스는 1로 시작한다(자식 트리를 나타내기 편해서라고 들었다)

루트 노드의 왼쪽 자식 노드 인덱스는 부모 노드 인덱스 * 2

오른쪽 자식 노드 인덱스는 부모 노드 인덱스 * 2 + 1로 나타낼 수 있다

 

배열과 리스트로 나타낼 수 있는데

배열은 빈 공간이 많이 생기는 단점이 있다

 

리스트는 공간 활용도가 배열에 비해 좋다

다만 자식이 많은 경우 자식을 찾는데 시간이 많이 소요된다

 

3. 이진트리 순회

트리 노드를 방문하는 방법을 의미한다

전위 순회, 중위 순회, 후위 순회가 있다

---

전위 순회는 왼쪽으로 내려가며 먼저 방문한 노드를 탐색한다

부모 → 왼쪽 자식 → 오른쪽 자식의 순서로 보면 편할 것 같다

    1

  2    3

4 5  6 7

 

이런 모양의 트리가 있을 때

전위 순회는 1 2 4 5 3 6 7의 순서로 진행한다

---

중위 순회는 왼쪽 아래로 내려가며 왼쪽 자식 → 부모 → 오른쪽 자식 순서로 탐색한다

4 2 5 1 6 3 7의 순서로 탐색된다

 

중위 탐색 순서를 다시 트리로 나타내면

    4

  2    6

1 3  5 7

의 형태를 나타내는데, 이 상태에서 왼쪽 자식 노드는 항상 부모 노드보다 작고, 오른쪽 자식 노드는 항상 부모 노드보다 크게 정렬된다

---

후위 순회는 왼쪽 자식 → 오른쪽 자식 → 부모 순서로 탐색한다

4 5 2 6 7 3 1의 순서로 탐색한다

폴더 삭제가 후위 순회의 예시이다(루트 폴더를 지우기 위해 하위 폴더를 모두 지우는 개념)

 

 

결국 순회의 중심은 부모가 언제 탐색되느냐로 이름이 정해진다

 

백준에 순회 문제가 있는데, 참고하면 좋을듯 하다

 

https://www.acmicpc.net/problem/1991

 

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

public class 트리_순회_1991 {

  static class Node {
    String self;
    Node left, right;

    public Node(String self, Node left, Node right) {
      this.self = self;
      this.left = left;
      this.right = right;
    }

    @Override
    public String toString() {
      return "Node{" + "self='" + self + '\'' + ", left=" + left + ", right=" + right + '}';
    }
  }

  static Node head = new Node("A", null, null);
  static StringBuilder sb = new StringBuilder();

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());

    StringTokenizer st;
    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      String a = st.nextToken();
      String b = st.nextToken();
      String c = st.nextToken();

      insert(head, a, b, c);
    }

    preOrder(head);
    sb.append("\n");
    inOrder(head);
    sb.append("\n");
    postOrder(head);

    System.out.println(sb);
  }

  static void preOrder(Node now) {
    if (now == null) return;
    sb.append(now.self);
    preOrder(now.left);
    preOrder(now.right);
  }

  static void inOrder(Node now) {
    if (now == null) return;
    inOrder(now.left);
    sb.append(now.self);
    inOrder(now.right);
  }

  static void postOrder(Node now) {
    if (now == null) return;
    postOrder(now.left);
    postOrder(now.right);
    sb.append(now.self);
  }

  static void insert(Node now, String value, String left, String right) {
    if (now.self.equals(value)) {
      now.left = left.equals(".") ? null : new Node(left, null, null);
      now.right = right.equals(".") ? null : new Node(right, null, null);
    } else {
      if (now.left != null) insert(now.left, value, left, right);
      if (now.right != null) insert(now.right, value, left, right);
    }
  }
}

 

4. 이진탐색트리

이진 탐색 트리는 중위 순회 개념과 유사하다

효율적 탐색을 위해 만들어졌으며, 왼쪽 자식 노드는 부모 노드보다 작고 오른쪽 자식 노드는 부모 노드보다 크다

 

보통 $$logN$$ 의 시간 복잡도를 가지지만, 최악의 경우는 $$N$$ 의 시간 복잡도를 가진다

계속 큰 값만 입력되어 오른쪽으로 치우쳐진 편향 트리가 되는 경우이다

균형이 잘 잡혀야 $$O(logN)$$ 의 시간 복잡도를 가진다

 

 

 

5. 문제 풀이

5-1. 길 찾기 게임

https://school.programmers.co.kr/learn/courses/30/lessons/42892

프로그래머스

 

5-2. 예상 대진표

https://school.programmers.co.kr/learn/courses/30/lessons/12985

프로그래머스

 

마무리

이번 주는 시험, 면접, 인프콘 등으로 조금 바빠서 내용을 많이 채우지 못했다

다음 주 내로 문제 풀이 코드와 이진 탐색 트리 구현을 작성해야겠다