[이산수학]이진 트리의 정의 및 종류(완전, 포화, 편향)

[이산수학]이진 트리의 정의 및 종류(완전, 포화, 편향)

부모 노드가 몇 개의 자식 노드를 가졌느냐에 따라 트리의 종류가 달라집니다. n개의 노드일 때, 즉 트리의 최대 차수가 n인 경우를 n항 트리(n-ary tree)라고 합니다. 이진 트리(또는 이항 트리)는 최대 차수가 2인 트리입니다. 즉, 최대로 가질 수 있는 자식 노드가 두개인 트리입니다. 

 

■ 이진 트리(Binary Tree)

트리 T를 구성하는 부모 노드가 갖는 자식 노드의 수가 최대 2개인 트리

 

자식 노드가 하나도 없거나, 하나 혹은 두 개를 갖는 트리 모두 이진 트리에 속합니다. 최대 차수가 2로 제한되기 때문에 이진 트리는 왼쪽 서브 트리와 오른쪽 서브 트리를 구분합니다. 

 

---

 

이진 트리는 완전 이진 트리와 편향 이진 트리로 나눌 수 있습니다. 

완전 이진 트리는 포화 이진 트리를 포함합니다. 

 

■ 완전 이진 트리(Complete Binary Tree)

높이가 h일 때 레벨 1부터 h-1까지 모든 노드가 두 개씩 채워져 있고(h-2까지 자식 노드가 두개다), 레벨 h는 왼쪽부터 노드가 채워져 있는 트리

 

 

■ 포화 이진 트리(Full Binary Tree)

높이가 h일 때, 레벨 1에서 h까지 모든 노드가 두 개씩 채워져 있는 트리

 

 

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

왼쪽이나 오른쪽 서브 트리만 가지는 트리 

 

 

 

수학으로 이해하는 디지털 논리 이산수학 361-364p 참고

 

-----------------------------------

이산수학 총정리

목록 보러가기 

-----------------------------------