트리(Tree) 란?

뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료구조

비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어 있다.

선형구조는 자료를 저장하고 꺼내는 것에 초점,
비선형구조는 표현에 초점

---

이진 트리(Binary Tree)

• 각 노드가 최대 두개의 자식을 가진다
  

---

완전 이진 트리(Complete Binary Tree)

• 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다
  
• 완전 이진 트리 일때, 배열로 표현이 가능하다
• 편의성을 위해 0번째 인덱스는 사용 X
• 왼쪽 자식의 인덱스 = 현재 인덱스 * 2
• 오른쪽 자식의 인덱스 = 현재 인덱스 * 2 + 1
• 부모의 인덱스 = 현재 인덱스 // 2
  
• 트리의 높이 : 루트 노드부터 가장 아래 리프 노드까지의 길이
• 각 레벨에 최대로 들어갈 수 있는 노드의 갯수 = $2^k$ 개
• 높이 h 인 완전이진트리의 최대 노드 갯수 = $2^{h+1}-1$ 개
• 최대 노드 갯수가 $N$ 일때, 높이 h 는? $log_2(N+1) -1$