📖Binary Tree

각 노드가 최대 2개의 자식 노드를 가지고 있는 트리

• 루트 노드만 존재해도 이진 트리

📖이진 트리의 종류

📎정 이진 트리(Full Binary Tree)

모든 노드가 0개 또는 2개의 자식 노드를 가진 이진 트리

📎완전 이진 트리(Complete Binary Tree)

마지막 레벨을 제외한 모든 레벨에서 순서대로 노드가 꽉 채워진 이진 트리

• 순서는 왼쪽에서 오른쪽 (즉, 오른쪽 자식을 가지고 있다면 왼쪽 자식도 가지고 있어야 함)

📎포화 이진 트리(Perfect Binary Tree)

모든 노드가 2개의 자식을 가지고 leaf 노드가 모두 같은 레벨을 가진 이진 트리

• 완전 이진 트리(Complete Binary Tree)에 속함 (역은 성립 X)

노드의 개수

$2^{h+1}-1(h:트리의높이)$

📎이진 탐색 트리(Binary Search Tree)

📖1차원 배열에서의 이진 트리

비선형 자료구조이지만 선형 자료구조인 1차원 배열로도 표현 가능

• 간단하게 트리를 나타낼 수 있음
• 공간의 제약이 존재 ( ∵ 배열의 한계)
• 데이터의 삽입/삭제 시 기존 데이터의 이동 ( ∵ 배열의 한계)
• 인덱스 값을 노드의 번호로 취급

노드 번호를 i라고 할 때

0번째 인덱스는 비워두고, 1번째 인덱스부터 사용

• 루트 노드 : i
• 부모 노드 : i/2
• 왼쪽 자식 노드 : i * 2
• 오른쪽 자식 노드 : i * 2 + 1