트리

트리(Tree)는 노드와 에지로 연결된 그래프의 특수한 형태.

• 순환 구조(Cycle)가 없다. 1개의 루트만 존재한다.
• 루트 노드를 제외한 노드는 단 1개의 부모 노드만 갖는다.
• 트리의 부분 트리(Subtree) 역시 트리의 모든 특징을 따른다.

트리의 구성 요소

• 노드
  • 데이터의 index와 value를 표현하는 요소
• 에지
  • 노드와 노드의 연결 관계를 나타내는 선
• 루트 노드
  • 트리에서 가장 상위에 존재하는 노드
• 부모 노드
  • 두 노드 사이의 관계에서 상위 노드에 해당하는 노드
• 자식 노드
  • 두 노드 사이의 관계에서 하위 노드에 해당하는 노드
• 리프 노드
  • 트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)
• 서브 트리
  • 전체 트리에 속한 작은 트리

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

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main {

    static ArrayList<Integer>[] alArr;
    static int[] arr;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt() + 1;

        alArr = new ArrayList[n];

        for (int i = 0; i < n; i++) {
            alArr[i] = new ArrayList<>();
        }

        for (int i = 0; i < n - 2; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            alArr[a].add(b);
            alArr[b].add(a); // 방향이 없기 때문에 양방향 모두 저장
        }

        arr = new int[n];
        visited = new boolean[n];

        DFS(1);

        for (int i = 2; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    private static void DFS(int root) {
        Stack<Integer> s = new Stack<>();
        s.add(root);

        while (s.isEmpty() == false) {
            int node = s.pop();

            if (visited[node] == false) {
                visited[node] = true;
                for (int n :
                        alArr[node]) {
                    if (visited[n] == false) {
                        s.add(n);
                        arr[n] = node;
                    }
                }
            }
        }
    }
}

트라이

트라이(Trie)는 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조.

트라이는 일반적으로 단어들을 사전의 형태로 생성한 후 트리의 부모 자식 노드 관계를 이용해 검색을 수행.

• N진 트리
  • 문자 종류의 개수에 따라 N이 결정.
  • 예를 들어 알파벳은 26개의 문자로 이뤄져 있으므로 26진 트리로 구성된다.
• 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지

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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        Node root = new Node();
        // 트라이 자료구조 생성
        while (n-- > 0) {
            String text = sc.next();
            Node node = root;

            for (int i = 0; i < text.length(); i++) {
                char c = text.charAt(i);
                if (node.next[c - 'a'] == null) {
                    node.next[c - 'a'] = new Node();
                }

                node = node.next[c - 'a'];
                if (i == text.length() - 1) node.isEnd = true; // 마지막 문자 체크
            }
        }
        // 트라이 자료구조 검색
        int count = 0;
        while(m-- > 0) {
            String text = sc.next();
            Node node = root;
            for (int i = 0; i < text.length(); i++) {
                char c = text.charAt(i);
                if (node.next[c - 'a'] == null) break;

                node = node.next[c - 'a'];
                if(i == text.length() -1 && node.isEnd) count++; // 마지막 문자 일치 확인
            }
        }
        System.out.println(count);
    }
}

class Node {
    Node[] next = new Node[26];
    boolean isEnd;
}

이진 트리

이진 트리(Binary tree)는 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성돼 있는 트리를 말한다.

트리 영역에서 가장 많이 사용되는 형태.

• 평향 이진 트리
  • 노드들이 한쪽으로 편향돼 생성된 이진 트리
• 포화 이진 트리
  • 트리의 높이가 모두 일정하며 리프 노드가 꽉찬 이진 트리
• 완전 이진 트리
  • 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리

데이터를 트리 자료구조에 저장할 때 편향 이진트리의 형태로 저장하면 탐색 속도가 저하되고 공간이 낭비된다.

일반적으로 코딩 테스트에서 데이터를 트리에 담는다고 하면 완전 이진트리 형태.

 

가장 직관적이면서 편리한 트리 자료구조 형태는 '배열'

 

이동 목표 노드 (index)	인덱스 연산	제약 조건(N = 노드 개수)
루트 노드	index = 1
부모 노드	index = index / 2	현재 노드가 루트 노드가 아님
왼쪽 자식 노드	index = index * 2	index * 2 <= N
오른쪽 자식 노드	index = index * 2 + 1	index * 2 + 1 <= N

import java.util.Scanner;

public class Main {
    static int[][] arr = new int[26][2];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        arr = new int[26][2]; // 알파벳 전체 길이, 좌우 저장

        for (int i = 0; i < n; i++) {
            int node = sc.next().charAt(0) - 'A'; // 인덱스로 관리
            int left = sc.next().charAt(0);
            int right = sc.next().charAt(0);

            if (left == '.') arr[node][0] = -1; // 값이 없으면 -1
            else arr[node][0] = left - 'A';

            if (right == '.') arr[node][1] = -1;
            else arr[node][1] = right - 'A';
        }

        preOrder(0); // 루트부터 시작
        System.out.println();
        inOrder(0);
        System.out.println();
        postOrder(0);
    }


    /**
     * 전위 순회
     *
     * @param now
     */
    private static void preOrder(int now) {
        if (now == -1) return;
        System.out.print((char) (now + 'A'));
        preOrder(arr[now][0]);
        preOrder(arr[now][1]);
    }

    /**
     * 중위 순회 *
     *
     * @param now
     */
    private static void inOrder(int now) {
        if (now == -1) return;
        inOrder(arr[now][0]);
        System.out.print((char) (now + 'A'));
        inOrder(arr[now][1]);
    }

    /**
     * 후위 순회 *
     *
     * @param now
     */
    private static void postOrder(int now) {
        if (now == -1) return;
        postOrder(arr[now][0]);
        postOrder(arr[now][1]);
        System.out.print((char) (now + 'A'));
    }
}

세그먼트 트리

주어진 데이터들의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태.

더 큰 범위는 '인덱스 트리'라고 하는데 코딩 테스트 영역에서는 큰 차이가 없다.

• 세그먼트 트리의 종류
  • 구간 합
  • 최대 / 최소 구하기
• 구현 단계
  • 트리 초기화
  • 질의 값 구하기 (구간 합 또는 최대 / 최소)
  • 데이터 업데이트

*어려워서 pass, 나중에 다시 보자

최소 공통 조상

*어려워서 pass, 나중에 다시 보자