[백준/자바(JAVA)] 5639 이진 검색 트리

💌문제

---

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

5639번: 이진 검색 트리

💌풀이

---

참고: https://girawhale.tistory.com/59 & 챗GPT

문제 구현

전위 순회일 경우, 처음 탐색한 값이 항상 루트이다. 그래서 먼저 처음 값을 루트로 설정해 주어야 한다. 그리고 이후 루프를 돌면서 Node에 insert 함수를 구현하여 현재 노드의 값보다 작으면 왼쪽 자식, 크면 오른쪽 자식으로 넘어가 null일 경우 해당 노드를 생성해주고 아니라면 재귀적으로 다시 탐색하는 방식으로 구현한다.

또한 트리가 모두 완성되면 후위 순회 함수를 구현해 왼쪽 자식, 오른쪽 자식, 현재 노드 순으로 탐색해 출력해줘야 한다.

 

이진 검색 트리 설명

이진 검색 트리는 이진 트리의 일종으로, 각 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값의 노드들이 위치하고 오른쪽 서브트리에는 해당 노드보다 큰 값의 노드들이 위치하도록 구성된다. 이를 통해 트리를 탐색하면서 노드의 값을 비교하여 탐색 시간을 줄일 수 있다.

이진 검색 트리의 구현은 일반적으로 Node 클래스와 이진 검색 트리 클래스로 나눠서 구현한다. 각 노드는 노드 자신의 값, 왼쪽 자식 노드, 오른족 자식 노드를 가리키는 포인터를 갖는다. 이진 검색 트리 클래스는 루트 노드를 가리키는 포인터와 삽입, 삭제, 탐색 등의 메서드를 포함할 수 있다.

 

이 문제에서는 따로 삭제나 탐색이 필요없기 때문에 삽입 메서드만 구현하면 된다.

 

• 삽입: 삽입하려는 값을 현재 노드와 비교하여 작으면 왼쪽 서브트리로, 크면 오른쪽 서브트리로 이동하면서 재귀적으로 삽입 위치를 찾는다.
• 삭제: 삭제하려는 값을 현재 노드와 비교하여 작으면 왼쪽 서브트리로, 크면 오른쪽 서브트리로 이동하면서 재귀적으로 삭제할 노드를 찾는다.

 

이진 검색 트리의 시간복잡도

이진 검색 트리의 시간 복잡도는 트리의 균형 상태에 따라 결정된다. 균형 상태가 좋은 트리는 탐색, 삽입, 삭제 모두 O(log n)의 시간 복잡도를 갖지만, 균형 상태가 나쁜 트리는 최악의 경우 O(n)의 시간 복잡도를 갖는다. 따라서 이진 검색 트리를 구현할 때는 트리의 균형을 유지하는 것이 중요하다.

 

이진 검색 트리의 순회

전위순회: 루트 노드를 먼저 방문하고, 왼쪽 서브트리를 순회한 뒤 오른쪽 서브트리를 순회한다. 이 방법으로 순회하면 트리의 노드들을 전체적으로 탐색할 수 있다.

중위순회: 왼쪽 서브트리를 먼저 순회하고 루트 노드를 방문하고, 오른쪽 서브트리를 순회하는 방법이다. 이 방법으로 순회하면 이진 검색 트리에서 노드들을 오름차순으로 정렬할 수 있다.

후위순회: 왼쪽 서브트리와 오른쪽 서브트리를 먼저 순회한 후에 루트 노드를 방문한다. 이 방법으로 순회하면 트리에서 자식 노드들을 먼저 탐색하고 부모 노드를 나중에 방문하게 된다.

 

💌자바 코드

---

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

public class BinarySearchTree {
    static class Node{
        int num;
        Node left, right;

        Node(int num){
            this.num=num;
        }
        Node(int num,Node left,Node right){
            this.num=num;
            this.left=left;
            this.right=right;
        }
        void insert(int n){
            if(n<this.num){ //현재 노드보다 작으면 왼쪽 서브트리로
                if(this.left==null)
                    this.left=new Node(n);
                else this.left.insert(n);
            }else{ //현재 노드보다 크면 오른쪽 서브트리로
                if(this.right==null)
                    this.right=new Node(n);
                else this.right.insert(n);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        Node root=new Node(Integer.parseInt(br.readLine())); //루트 노드 입력
        String s;
        while (true){
            s=br.readLine();
            if(s==null||s.equals("")) break;
            root.insert(Integer.parseInt(s));
        }
        postOrder(root);
    }
    static void postOrder(Node node){
        if(node==null) return;
        postOrder(node.left); //왼쪽 순회
        postOrder(node.right); //오른쪽 순회
        System.out.println(node.num);
    }
}