[자료구조] 이진트리 (Binary Tree) 이해하기

이진트리를 이해하기 전에 트리에 대해 이해하는 것을 추천드립니다.

 

이진트리란?

각 노드가 최대 2개의 자식노드를 가질 때 이진트리 (Binary Tree) 라고 합니다.
자식노드는 왼쪽 자식노드와 오른쪽 자식노드로 표현합니다.

(트리 구조에 따라 시간 복잡도가 악화되는 현상이 발생할 수 있습니다.)

 

 

동일한 루트와 자식노드를 가지고 있어도 자식노드의 위치가 다르면 두 트리는 서로 다른 트리가 됩니다.

 

이진트리의 종류

포화 이진트리 (Perfect Binary Tree)

모든 리프노드가 모두 동일한 레벨에 가득 차 있을때, 포화 이진트리 라고합니다.

포화 이진트리는 높이가 h 일 때, 노드의 수 =  2^(h+1)-1 라는 특징을 가집니다.

포화 이진트리 (Perfect Binary Tree)

 

완전 이진트리 (Complete Binary Tree)

마지막 레벨을 제외하고 모든레벨이 완전히 채워져 있고 노드가 가능한 가장 왼쪽에 있을때, 완전 이진트리라고 합니다.

완전 이진트리는 높이가 h 일 때, 노드의 수 = 2^h 이상, 2^(h+1) 미만 이라는 특징을 가집니다.

포화 이진트리에서 가장 우측 7번 리프를 제거 했을때 CBT인가요? 네. 완전 이진트리입니다.

 

6, 5 번 리프를 제거했을때 CBT 인가요 ? 네. 완전 이진트리입니다.

 

정 이진트리 (Full Binary Tree)

모든 자식 노드가 0개 또는 2개로만 이루졌을때, 정 이진트리라고 합니다.

혹은 엄격한 이진트리 (Strict Binary Tree) 라고 한다.

정 이진트리 (Full Binary Tree)

 

균형 이진트리 (Balanced Binary Tree)

왼쪽 자식, 오른쪽 자식 노드의 개수가 정확하게 일치하지 않아도 되지만, 지나치게 한쪽으로 치우치지 않을때, 균형 이진트리라고 합니다.

균형 이진트리 (Banlanced Binary Tree)

 

변질 이진트리 (Degenerate Binary Tree)

각 부모 노드가 오직 한개의 자식 노드를 갖을때, 변질 이진트리라고 합니다.

(성능면에서 트리가 연결 리스트의 데이터 구조처럼 동작하는것을 의미합니다.)

변질 이진트리 (Degenerate Binary Tree)