외부 이진 트리 직렬화

외부 이진 트리 직렬화(External Binary Tree Serialization)은 외부 이진 트리에서 리프 노드에만 실제 데이터가 존재한다는 특성을 이용하여 트리의 구조와 데이터를 효율적으로 나누어 저장하는 직렬화 방식이다.

외부 이진 트리

외부 이진 트리(External Binary Tree)는 모든 내부 노드가 정확히 두 개의 자식을 가지며, 오직 리프 노드에만 실제 데이터가 저장되는 이진 트리이다. 이러한 구조는 탐색 트리나 허프만 트리, 정적 집합 표현 등에서 활용된다.

직렬화 방식

외부 이진 트리 직렬화는 다음의 두 시퀀스로 나누어 트리 전체를 표현한다.

• 구조 시퀀스(structure sequence): 전위 순회(preorder traversal) 순서로 각 노드가 내부 노드이면 0, 리프 노드이면 1로 표시한다.
• 데이터 시퀀스(data sequence): 전위 순회 순서로 등장하는 리프 노드들의 데이터를 나열한다.

이 방식을 통해 구조 정보와 실제 데이터를 분리하여 저장할 수 있으며, 역직렬화를 통해 원래 트리를 복원할 수 있다.

예시

다음은 외부 이진 트리의 구조와 그 직렬화 결과이다.

트리 구조:

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

전위 순회 기준 직렬화 결과:

• 구조 시퀀스: 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.