이진 트리
이진 트리 정의
- 공집합이거나
- 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합
- 이진 트리의 서브 트리들은 모두 서브 트리
- 모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진 트리(binary tree)라 함
- 서브 트리는 공집합일 수 있음
- 따라서 이진 트리의 노드에는 최대 2개까지의 자식 노드가 존재할 수 있고, 모든 노드의 차수가 2 이하
- 서브 트리 간의 순서가 존재
- 순환적으로 정의
이진 트리의 성질
1. n개의 노드를 가진 이진 트리는 (n-1)개의 간선을 가짐
- 이진 트리에서 루트를 제외한 모든 노드는 하나의 부모 노드를 가지고
- 부모 노드와 자식 노드 간에 하나의 간선이 존재하므로
2. 높이가 h인 이진 트리는 최소 h개, 최대 (2ʰ-1)개의 노드를 가짐
- 한 레벨에는 적어도 하나의 노드가 존재해야 하므로 적어도 h개
- 하나의 노드는 최대 2개의 자식 노드를 가질 수 있으므로 레벨 i에서의 노드의 최대 개수는 (2ⁱ-1)개
- 따라서 전체 노드 개수는 (2ʰ-1)개
3. n개의 노드를 가지는 이진 트리의 높이는 최대 n이거나 최소 log₂(n+1)
- 레벨 당 적어도 하나의 노드가 존재하므로 높이가 n 이상일 수 없음
- 높이 h의 이진 트리가 가질 수 있는 노드 개수의 최댓값이 (2ʰ-1)개이므로 n=< 2ʰ-1, 따라서 h>= log₂(n+1)
- h는 정수이므로 올림 연산 필요
이진 트리의 분류
- 포화 이진 트리(full binary tree)
- 완전 이진 트리(complete binary tree)
- 기타 이진 트리
1. 포화 이진 트리
- 각 레벨에 노드가 꽉 차있는 이진 트리
- 높이 k인 포화 이진 트리는 (2ᵏ-1)개의 노드를 가짐
- 포화 이진 트리에는 위와 같이 각 노드에 번호를 붙일 수 있음
- 레벨 단위, 왼쪽→오른쪽 순으로
2. 완전 이진 트리
- 높이가 k일 때 레벨 1부터 k-1까지는 노드가 모두 차 있고, 마지막 레벨 k에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진 트리
- 마지막 레벨에 노드가 꽉 차있지 않아도 되지만 중간에 빈 곳이 있어서는 안 됨
- 포화 이진 트리는 항상 완전 이진 트리
- 그 역은 항상 성립하지는 않음
- 포화 이진 트리의 노드 번호와 완전 이진 트리의 노드 번호는 일대일 대응