Tree

• 그래프 자료구조의 일종
  • 많은 양의 데이터를 관리하기 위한 목적으로 사용
    • ex) 데이터베이스 시스템, 파일 시스템
      
      
• 하나 이상의 노드로 구성된 유한 집합
  • 원소 가운데 단 하나의 루트 노드
    • 최상단 노드
  • 루트 노드를 제외한 노드는 n개의 서로 분리된 부분집합으로 나누어짐
  • 단말 노드
    • 최하단 노드
  • 서브 트리들의 집합
• 우선순위 큐를 구현하기 위해 최소 힙이나 최대 힙을 이용하는데 최소 힙은 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조로서 트리 자료구조에 속함
  • 컴퓨터 공학에서는 보통 방향 그래프라 간주

결정 트리(decision tree)

• 알고리즘에서 나오는 조합을 나열한 것
• 왼쪽 끝에서 시작하여 오른쪽으로 이동
  • 조건이 성립하면 윗가지, 성립하지 않으면 아랫가지

이진 탐색 트리

• 이진 탐색이 동작할 수 있더록 고안된 효율적인 탐색이 가능한 자료구조
• 각 노드의 차수가 2 이하인 순서 트리

구조

왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

• 부모 노드보다 왼쪽 자식 노드가 작다
• 부모 노드보다 오른쪽 자식 노드가 크다

종류

• 포화 이진트리 : 높이 h까지 중간에 빈 자리 없이 꽉 차 있는 트리
• 전 이진트리 : 각 노드의 차수 = 0 or 전 노드의 차수가 1인 경우가 없는 트리
• 완전 이진트리 : 노드의 레벨의 마지막 레벨 전까지가 포화 이진트리이고 마지막 레벨의 노드들이 왼쪽에서부터 마지막까지 중간에 빠짐없이 채워져 있는 트리
• 균형 이진트리 : 왼쪽 서브트리와 오른쪽 서브트리의 노드레벨 차이가 1이내인 트리

구현

• 배열 이용한 경우
• 연결리스트를 이용하는 경우

Graph와 차이점

• 참고 : https://velog.io/@sung-ik-je/Graph