📚 정의
각각의 노드가 최대 두 개의 자식 노드를 가지는 트리이다. 따라서 모든 노드의 차수는 2 이하이며, 모든 서브 트리들은 이진 트리이다.
차수(Degree) : 특정 노드가 가지는 자식 노드의 개수
📚 종류
루트가 있는 이진 트리 (Rooted Binary Tree)
완전 이진 트리 (Complete Binary Tree)
마지막 레벨을 제외한 나머지 레벨의 모든 노드가 채워져있는 트리이다. 마지막 레벨에서는 왼쪽 부터 오른쪽으로 노드가 채워져있어야 한다.
힙(Heap)을 구현하는데 완전 이진 트리의 구조를 사용한다. 완전 이진 트리의 구현에는 보통 배열을 사용한다.
정 이진 트리 (Full Binary Tree)
모든 노드가 0개 혹은 2개의 자식 노드를 가지는 트리이다. 즉, 말단 노드를 제외한 모든 노드들이 2개의 자식 노드를 가지는 트리라고도 할 수 있다.
총 말단 노드 갯수는 총 내부 노드 갯수+1 이다.
포화 이진 트리 (Perfect Binary Tree)
모든 노드가 2개의 자식 노드를 가지며 모두 채워진 트리이다.
완전 이진 트리는 포화 이진 트리가 될 수 없지만, 포화 이진 트리는 완전 이진 트리가 될 수 있다.
높이가 h인 포화 이진 트리의 총 노드 갯수는 2^h-1 이다.
변질 트리 (Degenerate/Pathological Tree)
모든 내부 노드가 하나의 자식 노드만을 가지는 트리이다. LinkedList와 성능이 동일하다.
[참고]
