https://github.com/raywenderlich/swift-algorithm-club/blob/master/Tree/README.markdown

트리

트리는 객체간의 계층 관계를 나타낼 때 쓰인다.

트리는 노드로 구성되어 있고, 노드는 자식노드와 연결되어있다. 자식은 여러 개를 가질 수 있다.

부모가 없는 노드를 root node, 자식이 없는 노드를 leaf node라고 한다.

트리는 계층구조로 되어있기 때문에 사이클을 형성하지 않는다.

다음과 같은 사이클을 형성하는 구조를 그래프라고 한다.

구현

아래 코드는 일반적인 트리이다.

class TreeNode<T> {
    var value: T
    
    weak var parent: TreeNode<T>?
    var child: [TreeNode<T>] = []
    
    init(value: T) {
        self.value = value
    }
    
    func addChild(_ node: TreeNode<T>) {
        child.append(node)
        node.parent = self
    }
}

그리고 다음과 같이 정의하면 트리를 구성할 수 있다.

let tree = TreeNode<String>(value: "beverages")

let hotNode = TreeNode<String>(value: "hot")
let coldNode = TreeNode<String>(value: "cold")

let teaNode = TreeNode<String>(value: "tea")
let coffeeNode = TreeNode<String>(value: "coffee")
let chocolateNode = TreeNode<String>(value: "cocoa")

let blackTeaNode = TreeNode<String>(value: "black")
let greenTeaNode = TreeNode<String>(value: "green")
let chaiTeaNode = TreeNode<String>(value: "chai")

let sodaNode = TreeNode<String>(value: "soda")
let milkNode = TreeNode<String>(value: "milk")

let gingerAleNode = TreeNode<String>(value: "ginger ale")
let bitterLemonNode = TreeNode<String>(value: "bitter lemon")

tree.addChild(hotNode)
tree.addChild(coldNode)

hotNode.addChild(teaNode)
hotNode.addChild(coffeeNode)
hotNode.addChild(chocolateNode)

coldNode.addChild(sodaNode)
coldNode.addChild(milkNode)

teaNode.addChild(blackTeaNode)
teaNode.addChild(greenTeaNode)
teaNode.addChild(chaiTeaNode)

sodaNode.addChild(gingerAleNode)
sodaNode.addChild(bitterLemonNode)

높이와 깊이

트리의 높이는 루트에서 자식까지 선의 갯수로 위 트리의 높이는 3이다.
트리의 깊이는 해당 노드에서 루트노드까지의 선의 갯수이다. tea를 예로 들면 루트까지 2개의 선이 있으므로 깊이는 2이다.

구성

트리는 다양한 방법으로 construct할 수 있다. 어떨 때는 부모 속성을 바꿀 필요가 없다. 이진트리같은 경우에는 최대 2개의 자식만 줄 수 있다. 아주 보편적인 형태는 이진 탐색 트리(Binary Search Tree)이다.

여기에 표시된 일반적인 트리는 계층적 데이터를 설명하는 데 유용하지만, 실제로는 어떤 종류의 추가 기능이 필요한지 애플리케이션에 따라 다르다.

탐색

extension Node {
  // 1
  func search(value: String) -> Node? {
    // 2
    if value == self.value {
      return self
    }
    // 3
    for child in children {
      if let found = child.search(value: value) {
        return found
      }
    }
    // 4
    return nil
  }
}