코딩 테스트 합격자 되기 스터디 4주차 : 트리

트리

트리 개념

트리는 데이터를 저장하고 탐색하기에 유용한 구조

트리의 특성을 활용하는 분야

• 인공지능
• 자동 완성 기능
• 데이터베이스

트리 구성요소

• 노드
  • 트리를 구성하는 노드 루트 노드
  • 노드를 연결하는 에지
  • 부모-자식, 형제 관계를 가지는 노드
  • 자식이 없는 말단 노드
  • 아래로 향하는 간선의 개수, 차수

이진 트리

이진 트리는 배열이나 포인터로 구현할 수 있다.

배열로 표현하기

배열은 선형 자료구조이고 트리는 계측 자료구조이다.

규칙

• 루트 노드는 인덱스 1번에 저장한다
• 왼쪽 자식 노드의 배열 인덱스는 부모 노드 인덱스 * 2 이다.
• 오른쪽 자식 노드의 배열 인덱스는 부모 노드 인덱스 * 2 + 1 이다.

이진 트리 순회

• 전위 순회: 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드
• 중위 순회: 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드
• 후위 순회: 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드

인접 리스트로 표현하기

정점의 번호(수)만큼 리스트를 생성하여, 리스트는 해당 정점에서 연결된 노드의 번호이다.

인접 리스트로 표현시 장점

• 메모리 공간 효율성
• 다음 정점을 빠르게 탐색할 수 있다.
• 시간 복잡도 면에서 이점이 있어 트리를 포함한 그래프 문제에 많이 사용한다.

이진 트리의 시간 복잡도

• 균형이 유지되었다고 가정 시: O(logN)
• 최악의 경우 시간 복잡도: O(n)균형 이진 탐색 트리
• AVL 트리, 레드-블랙 트리

풀어볼만한 문제

길 찾기 게임

https://school.programmers.co.kr/learn/courses/30/lessons/42892
좌표가 적힌 트리 구조를 구현하는 문제이다.
트리 순회는 재귀로 표현하였다.

배열

package t0803;

import java.util.ArrayList;
import java.util.Arrays;

public class p길찾기게임 {

    private static class Node {
        int x, y, num;
        Node left, right;

        public Node(int num, int x, int y) {
            this.num = num;
            this.x = x;
            this.y = y;
        }
    }

    // 이진 트리 생성 메서드
    private static Node makeBt(int[][] nodeinfo) throws Exception{
        Node[] nodes = new Node[nodeinfo.length];
        for (int i = 0; i < nodeinfo.length; i++) {
            // i + 1, x, y
            nodes[i] = new Node(i + 1, nodeinfo[i][0], nodeinfo[i][1]);
        }
        Arrays.sort(nodes, (o1, o2) -> {
            if (o1.y == o2.y) {
                return Integer.compare(o1.x, o2.x);
            }
            return Integer.compare(o2.y, o1.y);
        });

        Node root = nodes[0]; // 루트 노드

        for (int i = 1; i < nodes.length; i++) {
            Node parent = root;
            while (true) {
                // 부모 노드의 x좌표가 더 크면 외쪽
                if (nodes[i].x < parent.x) {
                    if (parent.left == null) {
                        parent.left = nodes[i];
                        break;
                    }
                    else {
                        parent = parent.left;
                    }
                }
                // 부모 노드의 x좌표가 더 작거나 같으면 오른쪽
                else {
                    if (parent.right == null) {
                        parent.right = nodes[i];
                        break;
                    }
                    else {
                        parent = parent.right;
                    }
                }
            }
        }

        return nodes[0];
    }

    // 전위 순회 메서드
    private static void preOrder(Node curr, ArrayList<Integer> answer) {
        if (curr == null) {
            return;
        }
        answer.add(curr.num);
        preOrder(curr.left, answer);
        preOrder(curr.right, answer);
    }

    // 후위 순회 메서드
    private static void postOrder(Node curr, ArrayList<Integer> answer) {
        if (curr == null) {
            return;
        }
        postOrder(curr.left, answer);
        postOrder(curr.right, answer);
        answer.add(curr.num);
    }

    public static void main(String[] args) {
        try {
            int[][] nodeinfo = {{5,3},{11,5},{13,3},{3,5},{6,1},{1,3},{8,6},{7,2},{2,2}};
            Node root = makeBt(nodeinfo);
            ArrayList<Integer> preOrderList = new ArrayList<>();
            preOrder(root, preOrderList);
            ArrayList<Integer> postOrderList = new ArrayList<>();
            postOrder(root, postOrderList);

            int[][] answer = new int[2][nodeinfo.length];
            answer[0] = preOrderList.stream().mapToInt(Integer::intValue).toArray();
            answer[1] = postOrderList.stream().mapToInt(Integer::intValue).toArray();

            for (int i = 0; i < answer.length; i++) {
                int[] ints = answer[i];
                System.out.println("ints = " + Arrays.toString(ints));
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

연결 리스트

package t0803;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.IntStream;

public class p길찾기게임 {

    private static class Node {
        int x, y, num;
        Node left, right;

        public Node(int num, int x, int y) {
            this.num = num;
            this.x = x;
            this.y = y;
        }
    }

    // 이진 트리 생성 메서드
    private static Node makeBt(int[][] nodeinfo) throws Exception {
        List<Node> nodes = new LinkedList<>();
        for (int i = 0; i < nodeinfo.length; i++) {
            // i + 1, x, y
            nodes.add(new Node(i + 1, nodeinfo[i][0], nodeinfo[i][1]));
        }
        nodes.sort((o1, o2) -> {
            if (o1.y == o2.y) {
                return Integer.compare(o1.x, o2.x);
            }
            return Integer.compare(o2.y, o1.y);
        });

        Node root = nodes.get(0); // 루트 노드

        for (int i = 1; i < nodes.size(); i++) {
            Node parent = root;
            while (true) {
                // 부모 노드의 x좌표가 더 크면 왼쪽
                if (nodes.get(i).x < parent.x) {
                    if (parent.left == null) {
                        parent.left = nodes.get(i);
                        break;
                    } else {
                        parent = parent.left;
                    }
                }
                // 부모 노드의 x좌표가 더 작거나 같으면 오른쪽
                else {
                    if (parent.right == null) {
                        parent.right = nodes.get(i);
                        break;
                    } else {
                        parent = parent.right;
                    }
                }
            }
        }

        return nodes.get(0);
    }

    // 전위 순회 메서드
    private static void preOrder(Node curr, List<Integer> answer) {
        if (curr == null) {
            return;
        }
        answer.add(curr.num);
        preOrder(curr.left, answer);
        preOrder(curr.right, answer);
    }

    // 후위 순회 메서드
    private static void postOrder(Node curr, List<Integer> answer) {
        if (curr == null) {
            return;
        }
        postOrder(curr.left, answer);
        postOrder(curr.right, answer);
        answer.add(curr.num);
    }

    public static void main(String[] args) {
        try {
            int[][] nodeinfo = {{5, 3}, {11, 5}, {13, 3}, {3, 5}, {6, 1}, {1, 3}, {8, 6}, {7, 2}, {2, 2}};

            Node root = makeBt(nodeinfo);

            List<Integer> preOrderList = new LinkedList<>();
            preOrder(root, preOrderList);

            List<Integer> postOrderList = new LinkedList<>();
            postOrder(root, postOrderList);

            int[][] answer = new int[2][nodeinfo.length];
            answer[0] = preOrderList.stream().mapToInt(Integer::intValue).toArray();
            answer[1] = postOrderList.stream().mapToInt(Integer::intValue).toArray();

            IntStream.range(0, answer.length)
                    .mapToObj(i -> "ints = " + Arrays.toString(answer[i]))
                    .forEach(System.out::println);

        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

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

출처

코딩 테스트 합격자 되기