외부 이진 트리 편집하기

외부 이진 트리(External Binary Tree)은 모든 내부 노드가 정확히 두 개의 자식을 가지며, 오직 리프 노드에만 실제 데이터가 저장되는 특수한 형태의 이진 트리이다.
==개요==
외부 이진 트리는 이진 트리의 한 변형으로, 자료의 저장은 리프 노드에서만 이루어지고 내부 노드는 구조적 용도로만 사용된다. 이러한 구조는 알고리즘 이론, 데이터 압축, 정적 집합 표현 등 다양한 컴퓨터 과학 분야에서 효율성을 높이기 위해 사용된다.
==정의==
외부 이진 트리는 다음과 같은 조건을 만족한다.
*각 내부 노드는 정확히 두 개의 자식을 가진다.
*모든 데이터는 리프 노드에만 저장된다.
*트리는 완전할 필요는 없지만, 포화적 구조를 갖는 경우가 많다.
==특징==
*리프 노드에만 데이터가 존재하므로, 데이터 접근은 항상 리프에 도달한 후에 가능하다.
*내부 노드는 데이터 대신 분기 조건이나 인덱스 정보 등을 담을 수 있다.
*트리의 높이가 비교적 일정하여, 최악의 경우 탐색 시간이 제한된다.
==활용==
외부 이진 트리는 다음과 같은 분야에서 널리 사용된다.
*허프만 트리: 데이터 압축을 위한 가변 길이 부호화 구조로, 외부 이진 트리를 기반으로 한다.
*정적 이진 탐색 트리: 변경이 없는 집합을 표현할 때 공간 및 탐색 효율을 위해 사용된다.
*결정 트리 모델: 머신러닝에서 조건에 따라 분기하며 최종 결정(리프 노드)을 내리는 트리 구조
==예시==
다음은 4개의 원소 A, B, C, D를 담는 외부 이진 트리의 구조이다.<pre>
       ●
      / \
     ●   ●
    / \   / \
   A   B C   D
</pre>이 경우 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.
==각주==
[[분류:트리]]