트리 종류 (완전이진트리, 포화이진트리, 편향이진트리)

트리 종류 (완전이진트리, 포화이진트리, 편향이진트리)

이진 트리의 노드 배치 방식에 따른 분류

특징: 형태별 성능 특성 상이, 적절한 구조 선택이 중요

포화 이진 트리(Perfect): 모든 레벨 완전 채움, 노드수=2^(h+1)-1, 리프=2^h, O(log n) 보장

완전 이진 트리(Complete): 마지막 레벨만 왼쪽부터 채움, 배열 구현 최적(부모=⌊i/2⌋, 자식=2i/2i+1), 힙 구현에 사용

편향 이진 트리(Skewed): 한쪽 자식만 존재, 높이=n-1, 연결 리스트 동일, O(n), 균형 트리(AVL/RB)로 해결

정 이진 트리(Strictly): 자식 0개 또는 2개, 리프수=내부노드수+1, 허프만/수식 트리

높이와 노드 수: 포화(2^(h+1)-1) / 완전(2^h~2^(h+1)-1) / 편향(h+1)

비교: 포화(꽉참/O(log n)) vs 완전(왼쪽채움/배열최적) vs 편향(한쪽/O(n)) vs 정(0·2자식/허프만)

연관: 힙, 균형 트리, AVL, Red-Black, 배열 표현