이진 트리(Binary Tree)

- 이진 트리 (Binary Tree)

모든 노드들이 둘 이하(공집합 포함)의 자식을 가진 트리

- 이진 트리 유형

 1. 전 이진트리 (Full Binary Tree or Strict Binary Tree) : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

 

 

 2. 완전 이진 트리 (Complete Binary Tree) : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리, 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 함

 

 3. 포화 이진 트리 (Perfect Binary Tree) : 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 리프 노드가 동일한 깊이 또는 레벨을 갖음

 

 

 4. 균형 이진 트리 (Balanced Binary Tree) : 왼쪽과 오른쪽 트리의 높이 차이가 모드 1만큼 차이나는 트리 (ex. AVL, Red-Black Tree)

 

 

- 이진 트리 표현

 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. 연결 리스트 표현 : 포인터를 사용하여 이진트리를 표현, 포인터로 연결하기 때문에 배열보단 접근 속도가 느리지만 삽입, 삭제가 쉽고 노드 수에 제한이 없음