트리의 기본 개념부터 파생되는 직렬화, 역직렬화 이슈 다루기 (Tree Serialize & Deserialize Solution)
1. 트리 구조에 대한 개념 설명
트리 구조는 위 아래 구조를 컴퓨터에서 표현한 형태이다.
워낙 많이 언급되는 부분이기도 하고, 배우는 단계에서는 꽤 어려운 알고리즘인데 이렇게 중요한 트리의 속성 중 하나는 재귀로 정의된 자기 참조 자료구조라는 점이다.
쉽게 말하면, 트리는 자식도 트리고, 또 그 자식도 트리다. 이 구조를 쉽게 서브 트리로 구성된다는 표현을 하는데, 우리가 알고리즘 문제를 풀 때 Sub String, Sub Array 등을 자주 접하는 것처럼 트리도 이러한 Sub Tree를 갖고 있는 것이 이상한 일은 아닌 것 같다.
그래프와 트리의 가장 큰 차이점을 물어본다면, 아마 “트리는 순환 구조를 갖지 않는 그래프”라는 점일 것이다.
아직 그래프 부분을 깊게 배우지 않았지만, 트리도 특수한 형태의 그래프의 일종이고, 그래프 범주에 포함된다고 한다.
사실 트리 구조를 생각하면, 나는 Binary Search Tree (이진 탐색 트리), 그리고 이진트리를 가장 먼저 떠올리고, 일반적으로 정의되는 트리와 위의 2개를 구분하지 못했다.
앞서 언급한 것처럼 일반적인 의미의 트리는 재귀로 정의된 자기 참조 자료구조이나,
이진트리는 (Binary Tree)
여기서 더 나아가 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드를 포함할 수 있다.
그렇다면 이진 탐색 트리는? (Binary Search Tree)
이진 탐색트리는 기본적으로 이진 트리 구조를 갖고 있으면서, 각 노드에 값이 있고 값들은 전순서가 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
한 번 간단하게 이진 트리 알고리즘의 노드를 구성하고, 여기에 데이터를 삽입하는 알고리즘을 구성해보자.
매우 간단하다. 처음에 root값을 지정하고, 순서대로 입력되는 수의 삽입에 따라 12(root) — 6(left) — 14(right) — 3(left child) 형태로 삽입된다.
2. 트리 구조의 직렬화, 역직렬화
직렬화는 파일이나 디스크에 저장하기 위해서는 물리적인 형태로 바꿔줘야하는데, 이를 작업하는 것을 의미하고
역직렬화는 이 반대 작업을 의미한다. (leet code 설명)
(다만, 역직렬화의 경우 결과 값이 배열이나 문자열 형태가 아니라 주소값이 출력되는 것으로 봐선, 직렬화처럼 특정 값으로 눈에 시각화되어 보여지는 것은 아닌 것 같다.)
예를 들어 1(root) — 2(left) — 3(right) — 4(right.left) — 5(right.right) 형태로 트리 구조를 이룬다고 생각해보자.
직렬화를 한다는 것은 이 트리를 [1,2,3,null,null,4,5] 형태로 변경하는 것을 의미한다.
막상 코드를 옮기고 나보니 함수 단위로 코드를 이해하면 그렇게 어려운 문제는 아닌 것 같다.
그러나 트리 탐색과 관련해서는 BFS, DFS가 항상 언급되는 것 같고, 연결리스트도 기본적으로 다루는 것 같으니 이 3개는 기본 개념으로 상시 다루는 것이 좋을 것 같다.
하다못해 얼마전에 알고리즘 문제를 풀다가 일반적으로 파이썬에서 큐를 개발자가 직접 구현하면 리스트를 사용해서 구현하는데,
deque 라이브러리를 사용하면 이중연결리스트로 구현되기 때문에 연산속도가 O(1)이라 성능차이가 분명히 발생한다.
큐를 리스틀 사용해 pop(0)으로적용했을 때시간 초과가 났던 문제를 deque사용해 popleft()했을 때 풀었던 거랑 차이를 잘 몰랐다.
조금씩 분명히 실력은 오르고 있다. 좌절하지 말자.
Ryan
참고 자료
파이썬 알고리즘 인터뷰 (박상길 저)
