트리

이 주제에 대한 튜토리얼은 여기에서 확인할 수 있다.

트리는 객체 간의 계층적 관계를 나타낸다. 다음은 트리의 예시다:

트리

트리는 노드로 구성되며, 이 노드들은 서로 연결되어 있다.

노드는 자식 노드들과 연결되고, 보통 부모 노드와도 연결된다. 자식 노드는 특정 노드 아래에 위치한 노드들을 의미하며, 부모 노드는 위에 위치한 노드를 가리킨다. 노드는 항상 하나의 부모만 가질 수 있지만, 여러 자식을 가질 수 있다.

트리

부모가 없는 노드를 루트 노드라고 한다. 자식이 없는 노드는 리프 노드라고 한다.

트리의 포인터는 순환 구조를 형성하지 않는다. 다음은 트리가 아니다:

트리가 아님

이런 구조는 그래프라고 한다. 트리는 그래프의 매우 단순한 형태다. (비슷한 맥락에서, 연결 리스트는 트리의 단순한 버전이라고 할 수 있다. 생각해 보라!)

이 글은 일반적인 목적의 트리에 대해 다룬다. 이는 각 노드가 가질 수 있는 자식의 수나 노드의 순서에 제한이 없는 트리를 의미한다.

다음은 Swift로 구현한 기본적인 트리 구조다:

public class TreeNode<T> {
  public var value: T

  public weak var parent: TreeNode?
  public var children = [TreeNode<T>]()

  public init(value: T) {
    self.value = value
  }

  public func addChild(_ node: TreeNode<T>) {
    children.append(node)
    node.parent = self
  }
}

이는 트리의 단일 노드를 표현한다. 제네릭 타입 T의 값을 가지며, 부모 노드에 대한 참조와 자식 노드들의 배열을 가지고 있다.

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

extension TreeNode: CustomStringConvertible {
  public var description: String {
    var s = "\(value)"
    if !children.isEmpty {
      s += " {" + children.map { $0.description }.joined(separator: ", ") + "}"
    }
    return s
  }
}

플레이그라운드에서 이를 실행해 보자:

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)

tree의 값을 출력하면 다음과 같은 결과를 얻는다:

beverages {hot {tea {black, green, chai}, coffee, cocoa}, cold {soda {ginger ale, bitter lemon}, milk}}

이는 다음과 같은 구조에 해당한다:

예시 트리

beverages 노드는 부모가 없으므로 루트 노드다. black, green, chai, coffee, cocoa, ginger ale, bitter lemon, milk 노드는 자식이 없으므로 리프 노드다.

어떤 노드에서든 parent 프로퍼티를 통해 루트 노드까지 거슬러 올라갈 수 있다:

teaNode.parent           // "hot" 노드
teaNode.parent!.parent   // 루트 노드

트리를 논의할 때는 주로 다음과 같은 정의를 사용한다:

트리를 구성하는 방법은 다양하다. 예를 들어, 때로는 parent 프로퍼티가 전혀 필요하지 않을 수도 있다. 또는 각 노드가 최대 두 개의 자식만 가질 수 있도록 제한할 수도 있다. 이런 트리는 이진 트리라고 한다. 매우 흔한 트리 유형 중 하나는 이진 탐색 트리 (또는 BST)다. 이는 이진 트리의 엄격한 버전으로, 노드들이 특정한 방식으로 정렬되어 탐색 속도를 높인다.

여기서 보여준 일반적인 목적의 트리는 계층적 데이터를 설명하는 데 유용하지만, 실제로 필요한 추가 기능은 애플리케이션에 따라 달라진다.

다음은 TreeNode 클래스를 사용해 트리가 특정 값을 포함하는지 확인하는 예시다. 먼저 노드의 value 프로퍼티를 확인한다. 일치하는 값이 없으면 모든 자식 노드를 차례대로 확인한다. 물론, 이 자식 노드들도 TreeNode이므로 동일한 과정을 재귀적으로 반복한다: 먼저 자신의 값을 확인하고, 그 다음 자식들을 확인한다. 그리고 그 자식들도 같은 작업을 반복한다. 재귀와 트리는 밀접한 관계가 있다.

다음은 해당 코드다:

extension TreeNode where T: Equatable {
  func search(_ value: T) -> TreeNode? {
    if value == self.value {
      return self
    }
    for child in children {
      if let found = child.search(value) {
        return found
      }
    }
    return nil
  }
}

이를 사용하는 예시는 다음과 같다:

tree.search("cocoa")    // "cocoa" 노드 반환
tree.search("chai")     // "chai" 노드 반환
tree.search("bubbly")   // nil 반환

트리를 배열만으로도 표현할 수 있다. 배열의 인덱스가 서로 다른 노드 간의 연결을 만든다. 예를 들어, 다음과 같은 경우:

0 = beverage		5 = cocoa		9  = green
1 = hot			6 = soda		10 = chai
2 = cold		7 = milk		11 = ginger ale
3 = tea			8 = black		12 = bitter lemon
4 = coffee

다음 배열로 트리를 표현할 수 있다:

[ -1, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 6, 6 ]

배열의 각 항목은 부모 노드를 가리킨다. 인덱스 3의 tea는 부모가 hot이므로 값이 1이다. 루트 노드는 부모가 없으므로 -1을 가리킨다. 이런 트리는 노드에서 루트로만 이동할 수 있고, 그 반대는 불가능하다.

참고로, 때로는 알고리즘에서 포레스트라는 용어를 사용하기도 한다. 이는 별개의 트리 객체들의 집합을 의미한다. 이에 대한 예시는 union-find를 참고하라.

Swift Algorithm Club의 Matthijs Hollemans가 작성함