[Data Structures] Tree

Tree

용어 설명

말그대로 트리 모양이다. 물론 진짜 나무는 뿌리가 아래에 있지만 이건 위에 있는..ㅎ

• Node: 링크드리스트처럼 트리도 노드들로 구성되어있다. 노드들은 children의 정보를 가진다
• Parent, Children: 아래 가지들이 모이는 노드를 parent라고 한다. 아래는 children. child는 무조건 하나의 부모를 가진다.
• Root: 트리의 가장 최상위 노드를 말한다. 애는 parent가 없다.
• Leaf: 트리의 가장 최하위 노드들을 말하는데, 이들은 children이 없다.

Tree 구현해보기

우선 Tree를 구현하기 위해서는 TreeNode 부터 생성해야 한다.

TreeNode

class TreeNode<T> {
    var value: T
    var children: [TreeNode] = []
    
    init(value: T) {
        self.value = value
    }

   func add(child: TreeNode) {
        children.append(child)
    }
}

각각의 treenode들은 자신의 값과 children을 저장할 공간이 필요해서 value, children을 선언했다. children을 추가할 수 있도록 add 메서드를 구현했다.

let beverages = TreeNode(value: "Beverages")
let hot = TreeNode(value: "hot")
let cold = TreeNode(value: "cold")

beverages.add(child: hot)
beverages.add(child: cold)

위와 같은 코드를 호출하면 트리 그림으로는 아래와 같은 모양이 나온다.

Traversal Algorithms

트리를 순회하는 알고리즘은 여러가지가 있다. 깊게 먼저 들어가는 게 있기도 하고 층별로 방문해보는 것도 있고, 루트를 어느 순서에 방문할건지에 따라 달라지기도 한다. 여기서는 깊게 먼저 들어가는 Depth-first 와 층별로 방문하는 Level-order 에 대해 알아본다.

Depth-first traversal

TreeNode에 아래 코드를 넣는다.

    func forEachDepthFirst(visit: (TreeNode) -> Void) {
        visit(self)
        children.forEach { $0.forEachDepthFirst(visit: visit) }
    }

forEach 내부에서 forEachDepthFirst를 호출하게 된다. 재귀함수.. 으 재귀함수..

실제로 제대로 동작하는지 실행해보자.

func makeBeverageTree() -> TreeNode<String> {
  let tree = TreeNode("Beverages")

  let hot = TreeNode("hot")
  let cold = TreeNode("cold")

  let tea = TreeNode("tea")
  let coffee = TreeNode("coffee")
  let chocolate = TreeNode("cocoa")

  let blackTea = TreeNode("black")
  let greenTea = TreeNode("green")
  let chaiTea = TreeNode("chai")

  let soda = TreeNode("soda")
  let milk = TreeNode("milk")

  let gingerAle = TreeNode("ginger ale")
  let bitterLemon = TreeNode("bitter lemon")

  tree.add(hot)
  tree.add(cold)

  hot.add(tea)
  hot.add(coffee)
  hot.add(chocolate)

  cold.add(soda)
  cold.add(milk)

  tea.add(blackTea)
  tea.add(greenTea)
  tea.add(chaiTea)

  soda.add(gingerAle)
  soda.add(bitterLemon)

  return tree
}

let tree = makeBeverageTree()
tree.forEachDepthFirst { treeNode in
    print(treeNode.value)
}

요런 트리를 만들어서 Depth-first traversal을 해보면 아래와 같이 결과가 나온다.

줄을 그어보면 깊이 우선이고, 왼쪽 노드부터 방문했다.

Level-order traversal

같은 층부터 방문하는 level-order.

func forEachLevelOrder(visit: (TreeNode) -> Void) {
        visit(self)
        var queue = QueueStack<TreeNode>()
        children.forEach { queue.enqueue($0) }
        
        while let node = queue.dequeue() {
            visit(node)
            node.children.forEach { queue.enqueue($0) }
        }
    }

아까와 순서가 다르다.

층별로 방문한다. Head부터 넣어서 children을 계속 enqueue하는 작업을 해주기 때문에 이렇게 결과가 나온다.

Search

extension TreeNode where T: Equatable {
  func search(_ value: T) -> TreeNode? {
    var result: TreeNode?
    forEachLevelOrder { node in
      if node.value == value {
        result = node
      }
    }
    return result
  }
}

level order로 노드를 하나씩 방문해 원하는 value가 나타날 때 까지 찾아보는 코드.