개요
이진 탐색 트리(Binary Search Tree, BST)를 직렬화하고 역직렬화하는 알고리즘을 설계해 보겠습니다. 직렬화(Serialization)란 데이터 구조나 객체 같은 것을 비트 열로 변환하여 파일이나 메모리 버퍼에 저장하거나 네트워크 연결을 통해 전송할 수 있도록 만드는 과정입니다. 반대로 직렬화된 데이터를 나중에 원래의 구조로 복원하는 과정을 역직렬화(Deserialization)라고 합니다.
예를 들어 입력이 [5,2,9,1,3,7]이라면 다음과 같은 결과가 나옵니다.
- 직렬화 결과: 5.2.9.1.3.7.N.N.N.N.N.N.N
- 역직렬화 결과(중위 순회): 1, 2, 3, 5, 7, 9
알고리즘 접근 방식
이 문제를 해결하기 위해 다음 단계를 따릅니다.
1. serialize() 함수 정의
- 루트 노드(root)를 인자로 받습니다.
- 결과를 담을 새 리스트 res를 생성합니다.
- 큐(queue)를 하나 만들고 root를 삽입합니다.
- 큐가 비어 있지 않은 동안 다음을 반복합니다.
- current := queue[0]
- current를 res의 끝에 추가합니다.
- 큐에서 첫 번째 요소를 제거합니다.
- current.left가 null이 아니면 current.left를 큐 끝에 삽입하고, 그렇지 않으면 None을 삽입합니다.
- current.right가 null이 아니면 current.right를 큐 끝에 삽입하고, 그렇지 않으면 None을 삽입합니다.
- 빈 문자열 s를 생성한 뒤, res의 각 요소를 순회하며 값이 있으면 해당 노드의 data를, 없으면 "N"을 문자열에 이어 붙입니다. 각 항목 사이에는 "." 구분자를 넣습니다.
- 최종적으로 문자열 s를 반환합니다.
2. deserialize() 함수 정의
- 직렬화된 문자열(data)을 인자로 받습니다.
- data를 "." 기준으로 분할하여 리스트로 만듭니다.
- data[0]이 'N'이면 None을 반환합니다(빈 트리).
- data[0]으로 새 노드를 만들어 root로 지정하고 스택(stack)에 삽입합니다.
- i := 1, current := 0으로 초기화한 뒤, i가 data 길이보다 작은 동안 다음을 반복합니다.
- data[i]가 'N'이 아니면 새 노드를 만들어 stack[current].left에 연결하고 스택에 추가하며, 'N'이면 left를 None으로 설정합니다.
- i를 1 증가시킨 후, 같은 방식으로 stack[current].right를 처리합니다.
- current와 i를 각각 1씩 증가시킵니다.
- root를 반환합니다.
구현 예제
아래 구현 예제를 통해 더 잘 이해할 수 있습니다.
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def insert(temp,data):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if (not temp.right):
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
def print_tree(root):
# 중위 순회(inorder traversal)로 출력
if root is not None:
print_tree(root.left)
print(root.data, end = ', ')
print_tree(root.right)
class Codec:
def serialize(self, root):
res =[]
queue = [root]
while queue:
while True and queue:
current = queue[0]
res.append(current)
queue.pop(0)
if current:
break
if not current:
break
if current.left:
queue.append(current.left)
else:
queue.append(None)
if current.right:
queue.append(current.right)
else:
queue.append(None)
s=""
for i in range(len(res)):
if res[i]:
s+=str(res[i].data)
else:
s+="N"
if i == len(res)-1:
break
s+="."
return s
def deserialize(self, data):
data = data.split(".")
stack = []
if data[0]=='N':
return None
root = TreeNode(int(data[0]))
stack.append(root)
i = 1
current = 0
while i <len(data):
left= False
if data[i] !='N':
temp = TreeNode(int(data[i]))
stack[current].left = temp
stack.append(temp)
else:
stack[current].left = None
i+=1
if data[i] !='N':
temp = TreeNode(int(data[i]))
stack[current].right = temp
stack.append(temp)
else:
stack[current].right = None
current+=1
i+=1
return root
ob = Codec()
root = make_tree([5,2,9,1,3,7])
ser = ob.serialize(root)
print('Serialization:',ser)
print_tree(ob.deserialize(ser))입력
[5,2,9,1,3,7]
출력
Serialization: 5.2.9.1.3.7.N.N.N.N.N.N.N 1, 2, 3, 5, 7, 9,
마무리
이처럼 레벨 순서(너비 우선) 탐색을 활용하면 트리의 구조를 문자열 형태로 손쉽게 직렬화할 수 있으며, 직렬화된 문자열에서 '.' 구분자와 'N'(null 표시)을 이용해 원래의 트리 구조를 정확히 복원할 수 있습니다. 직렬화된 데이터는 파일 저장, 메모리 캐싱, 네트워크 전송 등 다양한 상황에서 유용하게 활용됩니다.