데이터 구조란?
데이터 구조는 큰 데이터를 효과적으로 관리하기 위해 필요하다. 가령 도서관에 책이 분류도, 책장에도 놓여있지 않고 무분별하게 쌓여있다면 찾는 시간이 어마어마하게 걸리지만, 가나다순 혹은 분야별 등 분류 기준에 의해 정리되어 있다면 훨씬 효과적으로 관리 할 수 있다. 데이터 구조의 가장 기본적인 것이 tree 데이터 구조다. tree 데이터 구조는 뿌리, 줄기, 잎으로 구성되어 있으며 현실에서는 기업의 조직도나 디렉토리로 생각하면 쉽다.
tree 데이터 구조 기본지식
Root(뿌리)는 데이터 구조의 시작점이며 0레벨이다. 뿌리에서 가지, 나무로 뻗어나갈 수록 레벨이 1씩 증가한다.
Node(가지)는 트리 구조 데이터의 블록이며 Root 또한 Node다.
Leaf(잎)은 최종 데이터이며 때로는 Node에서 추가적인 Node로 이어지지 않는 경우 Terminal node 라고 불린다. (Root에서 바로 Leaf가 되는 경우처럼.)
tree 데이터 구조 만들기
class Node {
var value: String
var children = [Node]()
weak var parent: Node?
init(value: String) {
self.value = value
}
func add(child: Node) {
children.append(child)
child.parent = self
}
}
Node는 여러명의 자식을 둘 수 있기 때문에 배열로 정의하고, 반대로 부모는 하나뿐이거나 없는 경우도 있기 때문에 옵셔널로 정의한다.
또 add 메서드는 자식을 둠으로써 스스로가 부모가 되는 방식이다.
let beverage = Node(value: "beverage")
let hotBeverage = Node(value: "hot")
let coldBeverage = Node(value: "cold")
beverage.add(child: hotBeverage)
beverage.add(child: coldBeverage)
음료라는 큰 뿌리를 만들고, 뜨거운 음료와 차가운 음료를 만들었다.
let beverages = Node(value: "beverages")
let hotBeverage = Node(value: "hot")
let coldBeverage = Node(value: "cold")
let tea = Node(value: "tea")
let coffee = Node(value: "coffee")
let cocoa = Node(value: "cocoa")
let blackTea = Node(value: "black")
let greenTea = Node(value: "green")
let chaiTea = Node(value: "chai")
let soda = Node(value: "soda")
let milk = Node(value: "milk")
let gingerAle = Node(value: "ginger ale")
let bitterLemon = Node(value: "bitter lemon")
beverages.add(child: hotBeverage)
beverages.add(child: coldBeverage)
hotBeverage.add(child: tea)
hotBeverage.add(child: coffee)
hotBeverage.add(child: cocoa)
coldBeverage.add(child: soda)
coldBeverage.add(child: milk)
tea.add(child: blackTea)
tea.add(child: greenTea)
tea.add(child: chaiTea)
soda.add(child: gingerAle)
soda.add(child: bitterLemon)
다음과 같은 구조를 만들었다.
데이터 구조 확인하기
데이터 구조를 확인하기 위해 Root를 print 해보면 결과가 제대로 나오지 않는다.
그 이유는 컴파일러는 사용자 정의 객체를 인쇄할 방법을 모르기 때문이다.
따라서 구조를 확인하기 위해서는 CustomStringConvertible 프로토콜을 채택해야 한다.
CustomStringConvertible을 채택하면 String 형식의 이름 설명이 있는 연산 프로퍼티를 구현해야 한다.
자식의 자식까지 확인이 필요하므로 재귀적으로 작동해야 한다.
extension Node: CustomStringConvertible {
var description: String {
var text = "\(value)"
if !children.isEmpty {
text += " {" + children.map { $0.description }.joined(separator: ", ") + "} "
}
return text
}
}
이제 print를 해보면 제대로 나온다.
print(beverages) // beverages {hot {tea {black, green, chai} , coffee, cocoa} , cold {soda {ginger ale, bitter lemon} , milk} }
데이터 찾기
extension Node {
func search(value: String) -> Node? {
if value == self.value {
return self
}
for child in children {
if let found = child.search(value: value) {
return found
}
}
return nil
}
}
이 메서드는 트리안에 찾고자 하는 값이 있는지 확인하여 관련된 Node를 리턴해준다.
결과는 다음과 같다.
beverages.search(value: "cocoa") // returns the "cocoa" node
beverages.search(value: "chai") // returns the "chai" node
beverages.search(value: "hot") // returns "hot {tea {black, green, chai} , coffee, cocoa"
beverages.search(value: "bubbly") // returns nil
tea.search(value: "black") // returns the "black" node
tea.search(value: "herb") // returns nil
tea.search(value: "tea") // returns "tea {black, green, chai}"