• 계층적 관계를 갖는 자료구조
  • 사이클이 없는 그래프

  • 노드(Node) + 선분(Branch)로 구성

  • 용어
    • 디그리(차수) : 노드에서 뻗어나온 가지 수
    • 근 노드 : 맨 위에 있는 노드
    • 자식 노드 : 해당 노드의 하위 레벨에 있는 노드
    • 부모 노드 : 해당 노드의 상위 레벨에 있는 노드
    • 형제 노드 : 동일한 부모를 갖는 노드(같은 레벨)
    • 단말 노드 : 자식이 하나도 없는 노드

1. 이진트리(Binary Tree)

: 자식 노드가 최대 2개인 트리 (차수가 2 이하)

  • 완전이진트리(Complete Binary Tree) : n-1 레벨까지는 포화이진트리이고 n 레벨은 왼쪽->오른쪽 순으로 채워지는 트리
  • 정이진트리(Full Binary Tree) : 자식노드의 수는 0이거나 2인 트리 (자식노드가 1개만 있으면 안됨)
  • 포화이진트리(Perfect Binary Tree) : 모든 노드가 자식노드 수가 2인 트리
    (포화이진트리 ⊂ 완전이진트리)

2. 이진탐색트리(Binary Search Tree)

  • 이진탐색 + 연결리스트
  • 자식의 갯수는 2이하여야 하고 노드는 중복되지 않아야 한다.
  • 부모노드는 왼쪽 자식의 노드보다 크고 오른쪽 자신의 노드보다 작다 (왼쪽자식 < 부모 < 오른쪽자식)

  • 중위순회를 적용할 시 오름차순이 된다.

  • 평균 검색시 : O(logn)
  • 최악 검색시 : O(n)

3. 트라이 트리(Trie Tree)

  • 문자열에서 검색을 빠르게 도와주는 이진탐색트리 구조
  • 문자열의 길이가 n일때 검색시 : O(n)