외부 이진 트리

외부 이진 트리(External Binary Tree)은 모든 내부 노드가 정확히 두 개의 자식을 가지며, 오직 리프 노드에만 실제 데이터가 저장되는 특수한 형태의 이진 트리이다.

개요

외부 이진 트리는 이진 트리의 한 변형으로, 자료의 저장은 리프 노드에서만 이루어지고 내부 노드는 구조적 용도로만 사용된다. 이러한 구조는 알고리즘 이론, 데이터 압축, 정적 집합 표현 등 다양한 컴퓨터 과학 분야에서 효율성을 높이기 위해 사용된다.

정의

외부 이진 트리는 다음과 같은 조건을 만족한다.

• 각 내부 노드는 정확히 두 개의 자식을 가진다.
• 모든 데이터는 리프 노드에만 저장된다.
• 트리는 완전할 필요는 없지만, 포화적 구조를 갖는 경우가 많다.

특징

• 리프 노드에만 데이터가 존재하므로, 데이터 접근은 항상 리프에 도달한 후에 가능하다.
• 내부 노드는 데이터 대신 분기 조건이나 인덱스 정보 등을 담을 수 있다.
• 트리의 높이가 비교적 일정하여, 최악의 경우 탐색 시간이 제한된다.

활용

외부 이진 트리는 다음과 같은 분야에서 널리 사용된다.

• 허프만 트리: 데이터 압축을 위한 가변 길이 부호화 구조로, 외부 이진 트리를 기반으로 한다.
• 정적 이진 탐색 트리: 변경이 없는 집합을 표현할 때 공간 및 탐색 효율을 위해 사용된다.
• 결정 트리 모델: 머신러닝에서 조건에 따라 분기하며 최종 결정(리프 노드)을 내리는 트리 구조

예시

다음은 4개의 원소 A, B, C, D를 담는 외부 이진 트리의 구조이다.

       ●
      / \
     ●   ●
    / \   / \
   A   B C   D

이 경우 A, B, C, D는 리프 노드이며 실제 데이터를 저장하며, 나머지 ● 노드는 내부 노드로서 트리 구조만을 형성한다.

장점

• 데이터 저장과 구조 표현이 명확히 분리됨
• 균형 유지 및 최적화가 용이
• 순환적 알고리즘 설계가 단순해짐

단점

• 모든 검색이 리프까지 도달해야 하므로 불필요한 경로가 생길 수 있음
• 삽입/삭제 등의 동적 연산에는 부적합

같이 보기

• 허프만 트리
• 이진 탐색 트리
• 결정 트리
• 전위 순회
• 직렬화

참고 문헌

• Donald E. Knuth, "The Art of Computer Programming, Volume 1: Fundamental Algorithms", Addison-Wesley, 1997.
• Peter Brass, "Advanced Data Structures", Cambridge University Press, 2008.