완전 이진트리

1 개요[ | ]

이진 트리의 하나
마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있는 이진트리
두 개의 자식을 가질 수 있는 노드로 구성된 이진 노드에서, 말단에 있는 노드를 제외한 모든 노드들이 두 개의 자식을 모두 가지고 있는 이진트리
마지막 레벨 h에는 1 ~ 2h-1개의 노드를 있을 수 있다.
이러한 특징에 따라 완전이진트리는 배열을 사용하여 효율적으로 표현될 수 있다.
각 노드는 배열의 인덱스를 통해 부모 노드와 자식 노드의 위치를 쉽게 찾을 수 있기 때문이다.
예를 들어, 배열에서 위치 [math]\displaystyle{ i }[/math]에 있는 노드의 부모 노드는 위치 [math]\displaystyle{ \lfloor \frac{i-1}{2} \rfloor }[/math]에, 왼쪽 자식 노드는 [math]\displaystyle{ 2i+1 }[/math]에, 오른쪽 자식 노드는 [math]\displaystyle{ 2i+2 }[/math]에 위치한다.
완전 이진 트리는 힙과 같은 데이터 구조를 구현하는 데 자주 사용된다.
- 힙은 최대 힙과 최소 힙이라는 특별한 형태의 완전 이진 트리를 사용하여 구현된다.