🎄이진트리

---

모든 노드들이 둘 이하의 자식을 가진 트리.

1️⃣이진트리 유형

---

전 이진 트리 (Full Binary Tree or Strict Binary Tree)

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

완전 이진 트리 (Complete Binary Tree)

마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리.
마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.

포화 이진 트리 (Perfect Binary Tree)

모든 내부 노드가 두 개의 자식 노드를 가지며 모든 잎 노드가 동일한 깊이 또는 레벨을 갖음

균형 이진 트리 (Balaned Binary Tree)

왼쪽과 오른쪽 트리의 높이 차가 모두 1만큼 나는 트리. AVL, Red-Black 트리

2️⃣이진트리 속성

---

1. 이진 트리의 레벨 L에서 노드의 최대 수는 2^L이다.

2. 높이가 h이고 하나의 노드를 가진 트리의 높이가 1이라면 최대 노드 수는 2^h - 1이다.

3. 리프 노드 높이가 1이라면 최소 높이는 $`log_2(N+1)`$이다.
4. 전 이진트리에서 리프 노드 수는 항상 자식이 두 개인 노드보다 하나 더 많다.

3️⃣ 이진 트리 표현

---

이진 트리는 배열 또는 연결 리스트로 표현이 가능하다.

1. 배열(순차) 표현

이진 트리는 다음과 같은 속성 때문에 배열로 표현이 가능하다.

• 루트 노드의 인덱스 i가 0인 경우

  • 노드 i의 왼쪽 자식은 2*i+1 번째 노드이다.
  • 노드 i의 오른쪽 자식은 2*i+2 번째 노드이다.
  • 노드 i의 부모는 (i-1)/2 번째 노드이다.

• 루트 노드의 인덱스 i가 1인 경우

  • 노드 i의 왼쪽 자식은 2*i 번째 노드이다.
  • 노드 i의 오른쪽 자식은 2*i+1 번째 노드이다.
  • 노드 i의 부모는 i/2 번째 노드이다.

배열을 사용하면 노드 접근이 빠르고 구현이 용이하다는 장점이 있지만,

편향 이진트리 같은 경우 많은 공간이 낭비될 수 있고 배열 크기 이상 노드를 추가할 수 없다.

2. 연결리스트 표현

포인터를 사용하여 이진트리를 표현할 수 있다.

노드들이 가지고 있는 데이터가 정수라고 한다면 다음과 같이 표현할 수 있다.

struct BinaryTreeNode {
  int data;
  struct BinaryTreeNode *left
  struct BinaryTreeNode *right
}

연결 리스트는 배열보단 접근 속도가 느리지만 삽입, 삭제가 쉽고 노드를 포인터로 연결하기 때문에 노드 수에 제한이 없다.

4️⃣ 이진트리 용도

---

다음은 이진트리가 중요한 역할을 수행하는 응용들이다

• 수식 트리(Expression Tree)
• 허프만 코딩 트리(Huffman coding Tree)
• 이진 검색 트리(Binary Search Tree)
• 우선 순위 큐(PQ)

---

출처
https://yoongrammer.tistory.com/70?category=956616 yoongrammer 블로그
프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 2 - 구종만 지음
https://blog.encrypted.gg/1013?category=773649 바킹독 실전 알고리즘 이진트리