트리(Tree)

트리(Tree)

• 노드와 링크로 구성된 자료구조(그래프의 일종, Cycle 없음)

• 계층적 구조를 나타낼 때 사용

  • 폴더 구조, 조직도 등등..

• 트리의 구조
  

• 특징

  • 하나의 노드에서 다른 노드로 이동하는 경로는 유일
  • 노드가 N개인 트리의 Edge의 수는 N-1개
  • cycle X
  • 모든 노드는 서로 연결되어 있음
  • 하나의 Edge를 끊으면 2개의 tree로 분리됨

이진 트리

• 각 노드는 최대 2개의 자식을 가질 수 있음
• 자식 노드는 좌우를 구분
  • 왼쪽 : 부모 노드의 왼쪽 아래
  • 오른쪽 : 부모 노드의 오른쪽 아래
• 이진 트리 종류
  • 포화 이진 트리 : 모든 레벨에서 노드들이 꽉 채워져 있는 트리
  • 완전 이진 트리 : 마지막 레벨을 제외하고 노드들이 모두 채워져 있는 트리
  • 정 이진 트리 : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
  • 편향 트리 : 한쪽으로 기울어진 트리

이진 탐색 트리

• 왼쪽 자식 노드의 키는 부모 노드의 키보다 작음

• 오른쪽 자식 노드의 키는 부모 노드의 키보다 큼

• 각각의 서브 트리도 이진 탐색 트리를 유지

• 중복된 키를 허용하지 않음
  

• 특징

  • 이진 탐색 트리 규칙에 의해 데이터가 정렬
  • 이진 트리에 비해 탐색이 빠름

• 탐색

  • 찾고자 하는 데이터를 구트 노드부터 비교 시작
  • 대소 비교를 하여 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동
  • 최대 트리 높이 만큼의 탐색이 이루어짐

• 삽입

  • 루트부터 비교 시작, 중복 키 발견 시 종료
  • 삽입할 키가 현재 노드의 키보다 작으면 왼쪽 이동
  • 삽입할 키가 현재 노드의 키보다 크면 오른쪽 이동
  • leaf 노드 도달 후 키 비교하여 작으면 왼쪽, 크면 오른쪽 삽입

• 삭제

  • 삭제 대상 노드가 leaf노드인 경우
    • 삭제 대상 노드 삭제
    • 부모 노드의 해당 자식 링크 null로 변경
  • 삭제 대상 노드에 자식 노드가 하나 있는 경우
    • 자식 노드를 삭제 대상 노드의 부모 노드에 연결
    • 삭제 대상 노드 삭제
  • 삭제 대상 노드에 자식 노드가 둘인 경우
    • 삭제 대상 노드의 왼쪽 서브 트리에서 가장 큰 노드 선택
    • 선택한 노드를 삭제 대상 노드 위치로 올림
    • 위로 올리는 과정에서 다른 자식 노드들의 링크 연결 작업 진행
    • 삭제 대상 노드 삭제

백준1991

import java.io.*;
import java.util.HashMap;

public class Main {
    static class Node{
        char data;
        Node left, right;

        Node(char data){
            this.data = data;
            left = right = null;
        }
    }

    static HashMap<Character, Node> tree = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        for(int i=0; i<N; i++){
            String[] str = br.readLine().split(" ");
            char parent = str[0].charAt(0);
            char left = str[1].charAt(0);
            char right = str[2].charAt(0);

            tree.putIfAbsent(parent, new Node(parent));
            Node parentNode = tree.get(parent);

            if(left != '.'){
                tree.putIfAbsent(left, new Node(left));
                parentNode.left = tree.get(left);
            }

            if(right != '.'){
                tree.putIfAbsent(right, new Node(right));
                parentNode.right = tree.get(right);
            }
        }

        Node start = tree.get('A');
        preOrder(start);
        System.out.println();
        inOrder(start);
        System.out.println();
        postOrder(start);
    }

    public static void preOrder(Node start){
        if(start == null){
            return;
        }
        System.out.print(start.data);
        preOrder(start.left);
        preOrder(start.right);
    }

    public static void inOrder(Node start){
        if(start == null){
            return;
        }
        inOrder(start.left);
        System.out.print(start.data);
        inOrder(start.right);
    }

    public static void postOrder(Node start){
        if(start == null){
            return;
        }
        postOrder(start.left);
        postOrder(start.right);
        System.out.print(start.data);
    }
}