이진 트리

이진 트리는 각 노드가 0개, 1개, 또는 2개의 자식 노드를 가지는 트리 구조이다. 다음은 이진 트리의 예시이다:

자식 노드는 보통 왼쪽 자식과 오른쪽 자식으로 불린다. 자식 노드가 없는 노드는 리프 노드라고 부른다. 트리의 가장 상단에 위치한 노드는 루트 노드라 한다 (프로그래머들은 트리를 거꾸로 그리는 것을 선호한다).

종종 노드는 부모 노드로 돌아가는 링크를 가지지만, 이는 반드시 필요한 것은 아니다.

이진 트리는 주로 이진 탐색 트리로 사용된다. 이 경우 노드는 특정 순서로 정렬되어야 한다 (작은 값은 왼쪽, 큰 값은 오른쪽). 하지만 모든 이진 트리가 이 규칙을 따를 필요는 없다.

예를 들어, 다음은 (5 * (a - 10)) + (-4 * (3 / b))와 같은 산술 연산 시퀀스를 표현한 이진 트리이다:

코드

Swift에서 범용 이진 트리를 구현하는 방법은 다음과 같다:

public indirect enum BinaryTree<T> {
  case node(BinaryTree<T>, T, BinaryTree<T>)
  case empty
}

이를 사용하는 예제로, 산술 연산 트리를 만들어 보자:

// 리프 노드
let node5 = BinaryTree.node(.empty, "5", .empty)
let nodeA = BinaryTree.node(.empty, "a", .empty)
let node10 = BinaryTree.node(.empty, "10", .empty)
let node4 = BinaryTree.node(.empty, "4", .empty)
let node3 = BinaryTree.node(.empty, "3", .empty)
let nodeB = BinaryTree.node(.empty, "b", .empty)

// 왼쪽 중간 노드
let Aminus10 = BinaryTree.node(nodeA, "-", node10)
let timesLeft = BinaryTree.node(node5, "*", Aminus10)

// 오른쪽 중간 노드
let minus4 = BinaryTree.node(.empty, "-", node4)
let divide3andB = BinaryTree.node(node3, "/", nodeB)
let timesRight = BinaryTree.node(minus4, "*", divide3andB)

// 루트 노드
let tree = BinaryTree.node(timesLeft, "+", timesRight)

트리를 만들 때는 리프 노드부터 시작해 위로 올라가는 방식으로 구축해야 한다.

트리를 출력할 수 있도록 description 메서드를 추가하면 유용하다:

extension BinaryTree: CustomStringConvertible {
  public var description: String {
    switch self {
    case let .node(left, value, right):
      return "value: \(value), left = [\(left.description)], right = [\(right.description)]"
    case .empty:
      return ""
    }
  }
}

print(tree)를 실행하면 다음과 같은 결과를 볼 수 있다:

value: +, left = [value: *, left = [value: 5, left = [], right = []], right = [value: -, left = [value: a, left = [], right = []], right = [value: 10, left = [], right = []]]], right = [value: *, left = [value: -, left = [], right = [value: 4, left = [], right = []]], right = [value: /, left = [value: 3, left = [], right = []], right = [value: b, left = [], right = []]]]

약간의 상상력을 발휘하면 트리 구조를 볼 수 있다. 들여쓰기를 하면 더 명확해진다:

value: +, 
	left = [value: *, 
		left = [value: 5, left = [], right = []], 
		right = [value: -, 
			left = [value: a, left = [], right = []], 
			right = [value: 10, left = [], right = []]]], 
	right = [value: *, 
		left = [value: -, 
			left = [], 
			right = [value: 4, left = [], right = []]], 
		right = [value: /, 
			left = [value: 3, left = [], right = []], 
			right = [value: b, left = [], right = []]]]

트리의 노드 수를 세는 메서드도 유용하다:

  public var count: Int {
    switch self {
    case let .node(left, _, right):
      return left.count + 1 + right.count
    case .empty:
      return 0
    }
  }

예제의 트리에서 tree.count는 12가 된다.

트리에서 자주 필요한 작업 중 하나는 모든 노드를 순회하는 것이다. 이진 트리를 순회하는 세 가지 방법은 다음과 같다:

중위 순회 (또는 깊이 우선 순회): 노드의 왼쪽 자식을 먼저 보고, 그 다음 노드 자신을 보고, 마지막으로 오른쪽 자식을 본다.
전위 순회: 노드 자신을 먼저 보고, 그 다음 왼쪽과 오른쪽 자식을 본다.
후위 순회: 왼쪽과 오른쪽 자식을 먼저 보고, 마지막에 노드 자신을 처리한다.

이를 구현하는 방법은 다음과 같다:

  public func traverseInOrder(process: (T) -> Void) {
    if case let .node(left, value, right) = self {
      left.traverseInOrder(process: process)
      process(value)
      right.traverseInOrder(process: process)
    }
  }
  
  public func traversePreOrder(process: (T) -> Void) {
    if case let .node(left, value, right) = self {
      process(value)
      left.traversePreOrder(process: process)
      right.traversePreOrder(process: process)
    }
  }
  
  public func traversePostOrder(process: (T) -> Void) {
    if case let .node(left, value, right) = self {
      left.traversePostOrder(process: process)
      right.traversePostOrder(process: process)
      process(value)
    }
  }

트리 구조를 다룰 때 일반적으로 이러한 함수들은 재귀적으로 호출된다.

예를 들어, 산술 연산 트리를 후위 순회하면 다음과 같은 순서로 값을 볼 수 있다:

5
a
10
-
*
4
-
3
b
/
*
+

리프 노드가 먼저 나타나고, 루트 노드는 마지막에 나타난다.

이러한 표현식을 평가하기 위해 스택 머신을 사용할 수 있다. 다음은 의사 코드 예제다:

tree.traversePostOrder { s in 
  switch s {
  case this is a numeric literal, such as 5:
    push it onto the stack
  case this is a variable name, such as a:
    look up the value of a and push it onto the stack
  case this is an operator, such as *:
    pop the two top-most items off the stack, multiply them,
    and push the result back onto the stack
  }
  the result is in the top-most item on the stack
}

Swift Algorithm Club의 Matthijs Hollemans가 작성