외부 이진 트리 직렬화 편집하기

외부 이진 트리 직렬화(External Binary Tree Serialization)은 외부 이진 트리에서 리프 노드에만 실제 데이터가 존재한다는 특성을 이용하여 트리의 구조와 데이터를 효율적으로 나누어 저장하는 직렬화 방식이다.
==외부 이진 트리==
외부 이진 트리(External Binary Tree)는 모든 내부 노드가 정확히 두 개의 자식을 가지며, 오직 리프 노드에만 실제 데이터가 저장되는 이진 트리이다. 이러한 구조는 탐색 트리나 허프만 트리, 정적 집합 표현 등에서 활용된다.
==직렬화 방식==
외부 이진 트리 직렬화는 다음의 두 시퀀스로 나누어 트리 전체를 표현한다.
*구조 시퀀스(structure sequence): 전위 순회(preorder traversal) 순서로 각 노드가 내부 노드이면 0, 리프 노드이면 1로 표시한다.
*데이터 시퀀스(data sequence): 전위 순회 순서로 등장하는 리프 노드들의 데이터를 나열한다.
이 방식을 통해 구조 정보와 실제 데이터를 분리하여 저장할 수 있으며, 역직렬화를 통해 원래 트리를 복원할 수 있다.
==예시==
다음은 외부 이진 트리의 구조와 그 직렬화 결과이다.

트리 구조:<pre>       ●
      / \
     ●   ●
    / \   / \
   A   B C   D
</pre>전위 순회 기준 직렬화 결과:
*구조 시퀀스: 0 0 1 1 0 1 1
*데이터 시퀀스: A B C D
설명:
*루트와 그 자식 두 개는 내부 노드이므로 0으로 표현된다.
*리프 노드 A, B, C, D는 1로 표현되며, 이들의 데이터는 별도로 나열된다.
==복원 방식==
역직렬화는 다음 절차로 이루어진다.

* 구조 시퀀스를 앞에서부터 읽는다. 
* 0을 만나면 내부 노드로 간주하고, 왼쪽과 오른쪽 자식을 재귀적으로 생성한다. 
* 1을 만나면 데이터 시퀀스에서 데이터를 하나 꺼내 리프 노드를 생성한다. 
* 4. 모든 구조 시퀀스를 처리하면 완전한 트리를 복원할 수 있다.

==장점==
*구조 정보와 데이터가 분리되어 효율적인 저장 및 처리 가능
*트리 복원이 간단하며, 이진 형식 저장에 적합
*구조 시퀀스를 통한 트리 형태 분석이 용이함
==단점==
*리프 노드 수가 적을 경우 구조 시퀀스가 비대해질 수 있음
*리프 외 위치에 데이터가 필요한 경우에는 사용 불가
==같이 보기==
*[[외부 이진 트리]]
*[[전위 순회]]
*[[직렬화]]
*[[허프만 트리]]
*[[완전 이진 트리]]
==참고 문헌==
*Donald E. Knuth, "The Art of Computer Programming, Volume 1: Fundamental Algorithms", Addison-Wesley, 1997.
*Peter Brass, "Advanced Data Structures", Cambridge University Press, 2008.
==각주==
[[분류:트리 이론]]