트리(Tree)의 개념과 특징을 이해할 수 있다.

Goal

  • 트리(Tree)의 기본 개념을 이해한다.
  • 트리(Tree)의 종류를 구분할 수 있다.
  • 트리(Tree)의 특징을 이해할 수 있다.

트리(Tree)의 개념

트리는 노드로 이루어진 자료 구조

  1. 트리는 하나의 루트 노드를 갖는다.
  2. 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
  3. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.

트리(Tree)와 관련된 용어

트리(Tree)의 특징

트리(Tree)의 종류

트리 VS 이진 트리

이진 트리 VS 이진 탐색 트리

균형 트리 VS 비균형 트리

완전 이진 트리 VS 전 이진 트리 VS 포화 이진 트리

이진 힙(최소힙과 최대힙)

트라이(trie) (‘접두사 트리(Prefix Tree)’라고도 부른다.)

트리(Tree)의 구현 방법

기본적으로 트리는 그래프의 한 종류이므로 그래프의 구현 방법(인접 리스트 또는 인접 배열)으로 구현할 수 있다.

인접 배열 이용

  1. 1차원 배열에 자신의 부모 노드만 저장하는 방법
    • 트리는 부모 노드를 0개 또는 1개를 가지기 때문
    • 부모 노드를 0개: 루트 노드
  2. 이진 트리의 경우, 2차원 배열에 자식 노드를 저장하는 방법
    • 이진 트리는 각 노드가 최대 두 개의 자식을 갖는 트리이기 때문
    • Ex) A[i][0]: 왼쪽 자식 노드, A[i][1]: 오른쪽 자식 노드

인접 리스트 이용

  1. 가중치가 없는 트리의 경우
    • ArrayList< ArrayList > list = new ArrayList<>();
  2. 가중치가 있는 트리의 경우
    • 1) class Node { int num, dist; // 노드 번호, 거리 } 정의
    • 2) ArrayList[] list = new ArrayList[정점의 수 + 1];

그래프와 트리의 차이

관련된 Post

References