5. 이진트리 종류를 살펴보고
각각의 이진트리 특성을 알아봅시다
(1) 포화이진트리
: 모든 단말 노드의 깊이가 같은 완전이진 트리이다.
트리 전체가 모든 노드가 가득 체워져 있다.
- 특성
높이가 1이면 루트 하나만 있으므로 노드 개수는 1개이며 1
높이가 2이면 루트와 양쪽 자식을 합쳐 세 개의 노드가 존재한다. 1+2
높이가 3이면 7개, 1+2+4
높이가 4이면 15개이며 일반적으로 높이가 n이다. 1+2+4+8
포화 이진 트리의 노드 개수는 2n-1개이다.
(2) 완전이진트리
: 끝 부분(마지막 레벨)을 제외하고
모든 노드가 채워진 (마지막 레벨을 제외하고는
모든 노드가 자식노드를 2개를 가진) 이진트리.
마지막 레벨의 노드들은 왼쪽으로 채워져 있다.
마지막 레벨이 다 채워질 수도 있다.
- 특성
높이가 n인 완전 이진 트리의 노드 개수는
2n-1보다 크거나 같고 2n-1보다 작거나 같다
(3) 균형이진트리
: 좌우의 높이 차가 같은 이진 검색 트리.
이진 검색 트리의 검색 시간을
가능한 한 빠르게 하기 위해
단말 노드들의 레벨이 거의 같은,
완전이진트리 모양으로 구성하는 트리이다.
균형잡힌 이진트리
불균형한 이진트리
- 특성
:1. 모든 단말 노드의 깊이 차이가 많아야 1인 트리이다.
:2. 예측 가능한 깊이를 가진다.
:3.노드의 개수를 n이라 하면 깊이는 logn 과 같다.(바닥함수)
