[자료구조] 완전 이진트리란?

완전 이진트리란?

• 완전 이진트리
  • 자식 노드가 왼쪽부터 순서적으로 채워진 이진트리 높이가 균형을 유지

완전 이진트리 표현

• 배열로 표현한다.
  • 이유는 완전이진트리의 속성인 균형이 유지되기 때문

 

완전 이진트리 자료구조

• 0부터 시작해도 되지만 노드의 인덱싱의 조금 더 가시성이 좋기 때문에 1부터 시작해도 된다.
• 1부터 시작할 경우
• 배열 인덱스 i의 부모노드: i/2의 바닥함수(내림) 노드
• 배열 인덱스 i의 왼쪽 자식: 2i의 노드
• 배열 인덱스 i의 오른쪽 자식: 2i + 1의 노드
• 완전 이진트리의 레벨 i에서 노드의 수는 2^(i-1)개
• 완전이진트리의 높이가 h일 경우 최대 노드의 수는 2^h -1개

• 완전 이진트리에서 노드의 수 n일 경우 트리의 높이는 O(logn)
• 완전이진트리를 사용한 알고리즘의 수행시간은 트리의 높이에 비례

완전 이진트리의 응용

완전이진 트리만 사용하는 경우는 별로 없다.

완전이진트리의 종류인 힙트리를 사용하여 많이 사용한다.