이진 트리(Binary Tree)

이진 트리(Binary Tree) : 어떠한 노드도 2개보다 많은 Subtree 가질수 없습니다.

- 각 노드는 최대 2개의 자식을 가질 수 있습니다.

- 자식 노드는 좌우를 구분합니다.

    - 왼쪽 자식 : 부모 노드의 왼쪽 아래입니다.

    - 오른쪽 자식 : 부모 노드의 오른쪽 아래입니다.

 

Binary Tree의 예시

Subtree : 하위 트리는 하위 트리로 나눌 수 있습니다.

- 단일 노드도 하위 트리입니다.

Subtree의 예시

 

 

이진 트리의 종류

포화 이진 트리(Perfect Binary Tree) : 모든 레벨에서 노드들이 꽉 채워져 있는 트리

Example of Perfect Binary Tree

완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하고 노드들이 모두 채워져 있는 트리

Example of Complete Binary Tree

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

Example of Full Binary Tree

편향 트리(Skewed Binary Tree) = 사향 트리 : 한쪽으로 기울어진 트리

Example of Skewed Binary Tree

균형 이진 트리(Balanced Binary Tree) : 모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리

Example of Balanced Binary Tree

 

이진 트리의 특징

- 포화 이진 트리의 높이가 h일 때, 노드의 수는 2^(h+1)-1개 이다.

- 포화(or 완전) 이진 트리의 노드가 N개 일 때, 높이는 "logN"입니다.

- 이진 트리의 노드가 N개 일 때, 최대 가능 높이는 N입니다.

 

 

 

 

 

 

References

- Chapter 6. Introduction to Trees, Data Structures: A Pseudocode Approach with C, Second Edition, Richard F. Gilberg Behrouz A. Forouzan.