트리

• 노드와 엣지로 연결된 그래프의 특수한 형태
  • 그래프의 표현으로도 트리를 표현할 수 있음

트리의 특징

• 순환 구조를 지니고 있지 않고, 1개의 루트 노드 존재
• 루트 노드를 제외한 노드는 단 1개의 부모 노드를 가짐
• 트리의 부분 트리 역시 트리의 모든 특징을 따름
• 트리에서 임의의 두 노드를 이어주는 경로는 유일함

트리의 핵심 이론

코딩테스트에서의 Tree

1. 그래프로 푸는 tree
   • 그래프이기 때문에 인접리스트로 표현 가능
   • DFS, BFS 로 응용하여 풀이 가능
2. tree 만을 위한 문제
   • 이진 트리
   • 세그먼트 트리 (인덱스 트리)
     • 1차원 배열로 tree 표현
   • LCA
     • 1차원 배열로 tree 표현

이진 트리

• 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리

핵심 이론

• 이진 트리의 종류

  

  • 편향 이진 트리 : 한쪽으로 편향돼 생성된 이진 트리
    • 탐색 속도가 저하되고 공간이 낭비됨
  • 포화 이진 트리 : 리프 토드가 꽉찬 이진 트리
  • 완전 이진 트리 : 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리

이진 트리의 순차 표현

• 가장 직관적이면서 편리한 트리 자료구조 형태는 배열

  • 인덱스 0의 요소는 제외

  

최소 공통 조상 (LCA)