참고: 이 글을 이해하려면 이진 트리에 대한 기본 지식이 필요하다.
트리는 복잡한 구조를 가진다. 배열이나 연결 리스트와 같은 선형 컬렉션과 달리, 트리는 비선형 구조이며 각 요소는 노드 간의 부모-자식 관계와 같은 위치 정보를 포함한다. 트리 구조를 백엔드로 전송하려면 각 노드의 데이터와 함께 노드 간의 부모-자식 관계를 표현할 방법이 필요하다.
이 정보를 표현하는 방식을 선택하는 전략을 인코딩 전략이라고 한다. 반대로 인코딩된 데이터를 원래 형태로 되돌리는 과정은 디코딩 전략이다.
트리를 인코딩하고 디코딩하는 방법은 다양하다. 중요한 점은 인코딩과 디코딩 전략이 밀접하게 연관되어 있다는 것이다. 트리를 인코딩하는 방식은 디코딩 방법에 직접적인 영향을 미친다.
인코딩과 디코딩은 트리를 직렬화하고 역직렬화하는 것과 동일한 의미로 사용된다.
참고로, 다음 코드는 일반적인 이진 트리의 Node 타입을 나타낸다:
class BinaryNode<Element: Comparable> {
var data: Element
var leftChild: BinaryNode?
var rightChild: BinaryNode?
// ... (나머지 구현)
}
인코딩과 디코딩 메서드는 BinaryNodeEncoder와 BinaryNodeDecoder 클래스에 위치한다:
class BinaryNodeCoder {
// 노드를 문자열로 변환
func encode<T>(_ node: BinaryNode<T>) throws -> String where T: Encodable {
}
// 문자열을 `BinaryNode`로 변환
func decode<T>(from string: String)
throws -> BinaryNode<T> where T: Decodable {
}
}
앞서 언급했듯이, 인코딩에는 여러 방법이 있다. 특별한 이유 없이, 다음과 같은 규칙을 적용한다:
String 객체가 된다.이 작업을 코드로 구현한 예시는 다음과 같다:
fileprivate extension BinaryNode {
// 1
func preOrderTraversal(visit: (Element?) throws -> ()) rethrows {
try visit(data)
if let leftChild = leftChild {
try leftChild.preOrderTraversal(visit: visit)
} else {
try visit(nil)
}
if let rightChild = rightChild {
try rightChild.preOrderTraversal(visit: visit)
} else {
try visit(nil)
}
}
}
class BinaryNodeCoder {
// 2
private var separator: String { return "," }
// 3
private var nilNode: String { return "X" }
// 4
func encode<T>(_ node: BinaryNode<T>) -> String {
var str = ""
node.preOrderTraversal { data in
if let data = data {
let string = String(describing: data)
str.append(string)
} else {
str.append(nilNode)
}
str.append(separator)
}
return str
}
// ...
}
위 코드를 높은 수준에서 요약하면 다음과 같다:
separator는 문자열에서 노드를 구분하는 방법이다. 예를 들어, “banana”라는 인코딩된 문자열이 있다면, 이 트리 구조가 인코딩 전에 어떻게 생겼는지 알 수 없다. separator가 없으면 이를 구분할 수 없다.
nilNode는 빈 자식 노드를 식별하기 위해 사용한다. 이 정보는 나중에 트리를 다시 구성할 때 필수적이다.
encode는 BinaryNode의 String 표현을 반환한다. 예를 들어, “ba,nana,nil”은 두 개의 노드(“ba”와 “nana”)로 이루어진 트리를 전위 순회 형식으로 표현한 것이다.
디코딩 전략은 인코딩 전략과 정반대이다. 인코딩된 문자열을 받아 이진 트리로 다시 변환한다.
인코딩 전략은 다음과 같은 규칙을 따른다:
String 객체이다.구현 시 추가된 중요한 세부 사항은 다음과 같다:
,로 구분한다.nil 자식은 nil 문자열로 표시한다.이러한 세부 사항이 decode 작업의 형태를 결정한다. 다음은 가능한 구현 예시이다:
class BinaryNodeCoder {
// ...
// 1
func decode<T>(_ string: String) -> BinaryNode<T>? {
let components = encoded.lazy.split(separator: separator).reversed().map(String.init)
return decode(from: components)
}
// 2
private func decode(from array: inout [String]) -> BinaryNode<String>? {
guard !array.isEmpty else { return nil }
let value = array.removeLast()
guard value != "\(nilNode)" else { return nil }
let node = AVLNode<String>(value: value)
node.leftChild = decode(from: &array)
node.rightChild = decode(from: &array)
return node
}
}
위 코드의 개요는 다음과 같다:
String을 받아 인코딩 단계에서 정의된 separator를 기준으로 split을 사용해 문자열을 배열로 분할한다. 결과를 먼저 reversed로 뒤집은 후 String으로 매핑한다. reverse 단계는 다음 함수를 위한 최적화로, array.removeFirst() 대신 array.removeLast()를 사용할 수 있게 한다.
배열을 스택으로 사용해 각 노드를 재귀적으로 디코딩한다. 배열은 노드의 순서와 진행 상황을 추적한다.
다음은 인코딩 및 디코딩 과정을 거치는 트리의 예시 출력이다:
원본 트리
┌──8423
┌──8391
│ └──nil
┌──7838
│ │ ┌──4936
│ └──3924
│ └──2506
830
│ ┌──701
└──202
└──169
인코딩된 트리: 830,202,169,X,X,701,X,X,7838,3924,2506,X,X,4936,X,X,8391,X,8423,X,X,
디코딩된 트리
┌──8423
┌──8391
│ └──nil
┌──7838
│ │ ┌──4936
│ └──3924
│ └──2506
830
│ ┌──701
└──202
└──169
원본 트리와 디코딩된 트리가 동일함을 확인할 수 있다.
Swift 알고리즘 클럽을 위해 Kai Chen과 Kelvin Lau가 작성