간결한 인코딩이란?
이진 트리가 하나 주어져 있다고 가정해 봅시다. 이진 트리의 간결한(succinct) 인코딩은 이론적으로 가능한 최소 공간에 가까운 크기로 트리를 표현하는 방법입니다.
서로 다른 n개의 노드를 가질 수 있는 이진 트리의 구조적 형태 개수는 n번째 카탈란 수(Catalan number)와 같습니다. n이 충분히 크면 이 값은 대략 4n에 근사하므로, 트리의 구조를 표현하는 데 최소한 log2(4n) = 2n 비트가 필요합니다. 따라서 간결하게 인코딩된 이진 트리는 2n + O(n) 비트만큼의 공간을 사용하게 됩니다.
문제 예시
예를 들어 입력으로 다음과 같은 이진 트리가 주어진다고 합시다.
그렇다면 출력은 다음과 같습니다.
- 인코딩 결과
- 구조 리스트(Structure List): 1 1 1 0 0 1 0 0 1 0 1 0 0
- 데이터 리스트(Data List): 10 20 40 50 30 70
- 디코딩 결과: 위 그림과 동일한 원래의 트리
해결 접근 방식
이 문제는 전위 순회(preorder traversal)를 활용하여 해결할 수 있습니다. 단계별로 살펴보겠습니다.
Encode(인코딩) 함수
- Encode(root, struc, data) 함수를 정의합니다. root는 트리의 루트 노드, struc은 구조 정보를 담는 리스트, data는 노드 값을 담는 리스트입니다.
- root가 NULL이라면 struc의 끝에 0을 추가하고 함수를 종료합니다.
- root가 NULL이 아니라면 struc의 끝에 1을 추가합니다.
- root의 값을 data 리스트 끝에 추가합니다.
- 왼쪽 자식과 오른쪽 자식에 대해 재귀적으로 Encode를 호출합니다.
Decode(디코딩) 함수
- Decode(struc, data) 함수를 정의합니다.
- struc의 크기가 0 이하라면 NULL을 반환합니다.
- struc의 첫 번째 원소를 꺼내어 b에 저장합니다.
- b가 1이라면:
- data의 첫 번째 원소를 꺼내 key에 저장합니다.
- key 값을 가진 새 노드를 생성하여 root로 만듭니다.
- 왼쪽 자식과 오른쪽 자식을 Decode를 재귀 호출하여 채웁니다.
- root를 반환합니다.
- b가 0이라면 NULL을 반환합니다.
C++ 구현 예제
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
#include<bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) {
val = data;
left = NULL;
right = NULL;
}
};
void Encode(TreeNode *root, list<bool>&struc, list<int>&data){
if(root == NULL){
struc.push_back(0);
return;
}
struc.push_back(1);
data.push_back(root->val);
Encode(root->left, struc, data);
Encode(root->right, struc, data);
}
TreeNode *Decode(list<bool>&struc, list<int>&data){
if(struc.size() <= 0)
return NULL;
bool b = struc.front();
struc.pop_front();
if(b == 1){
int key = data.front();
data.pop_front();
TreeNode *root = new TreeNode(key);
root->left = Decode(struc, data);
root->right = Decode(struc, data);
return root;
}
return NULL;
}
void preorder_trav(TreeNode* root){
if(root){
cout << "key: "<< root->val;
if(root->left)
cout << " | left child: "<< root->left->val;
if(root->right)
cout << " | right child: "<< root->right->val;
cout << endl;
preorder_trav(root->left);
preorder_trav(root->right);
}
}
main() {
TreeNode *root = new TreeNode(10);
root->left = new TreeNode(20);
root->right = new TreeNode(30);
root->left->left = new TreeNode(40);
root->left->right = new TreeNode(50);
root->right->right = new TreeNode(70);
cout << "The Tree\n";
preorder_trav(root);
list<bool> struc;
list<int> data;
Encode(root, struc, data);
cout << "\nEncoded Tree\n";
cout << "Structure List\n";
list<bool>::iterator si; // Structure iterator
for(si = struc.begin(); si != struc.end(); ++si)
cout << *si << " ";
cout << "\nData List\n";
list<int>::iterator di; // Data iIterator
for(di = data.begin(); di != data.end(); ++di)
cout << *di << " ";
TreeNode *newroot = Decode(struc, data);
cout << "\n\nPreorder traversal of decoded tree\n";
preorder_trav(newroot);
}입력
root->left = new TreeNode(20); root->right = new TreeNode(30); root->left->left = new TreeNode(40); root->left->right = new TreeNode(50); root->right->right = new TreeNode(70);
출력
The Tree key: 10 | left child: 20 | right child: 30 key: 20 | left child: 40 | right child: 50 key: 40 key: 50 key: 30 | right child: 70 key: 70 Encoded Tree Structure List 1 1 1 0 0 1 0 0 1 0 1 0 0 Data List 10 20 40 50 30 70 Preorder traversal of decoded tree key: 10 | left child: 20 | right child: 30 key: 20 | left child: 40 | right child: 50 key: 40 key: 50 key: 30 | right child: 70 key: 70
정리
이처럼 전위 순회 순서로 트리의 구조(노드 존재 여부를 나타내는 1/0 비트열)와 데이터(노드 값)를 분리하여 저장하면, 이론적 하한에 가까운 2n + O(n) 비트 수준으로 이진 트리를 압축할 수 있습니다. 또한 동일한 순서로 struc 리스트를 읽어 들이며 재귀적으로 노드를 생성하면 원래의 트리를 손실 없이 완벽하게 복원할 수 있습니다.