이진트리

이진트리 (Binary Tree)

정의

모든 노드들이 자식 노드를 최대 2개까지만 가질 수 있는 형태의 트리. (각 노드의 차수를 2 이하로 제한)

• 이진트리는 왼쪽 자식과 오른쪽 자식 노드를 가지는 순서 트리이다.

=> 순서트리이기 때문에 두번째 트리와 세번째 트리는 서로 다른 트리이다.

---

유형

• 정 이진 트리 (Full Binary Tree)

  노드의 차수가 0 또는 2인 이진 트리

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

  모든 레벨의 노드가 꽉 찬 상태인 이진 트리

• 전 이진 트리 (Complete Binary Tree)

  마지막 레벨을 제외하고 모든 레벨이 꽉 찬 상태

  1. 마지막 레벨은 왼쪽부터 노드가 차례대로 채워짐
  2. 오른쪽 형제 노드를 가지지 않는 노드가 존재할 수 있음

• 편향 이진 트리 (Skewed Binary Tree)

  루트 노드로부터, 왼쪽 또는 오른쪽으로만 치우친 이진 트리

---

이진 트리를 사용하여 자료를 효율적으로 저장할 수 있다.
BST (Binary Search Tree)