이진 탐색 트리(BST)

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

이진 탐색 트리는 특별한 종류의 이진 트리이다. 각 노드가 최대 두 개의 자식 노드를 가지는 이진 트리 구조를 기반으로, 삽입과 삭제를 수행할 때 항상 정렬된 상태를 유지한다.

트리에 대한 더 자세한 정보는 이 글을 먼저 읽어보는 것이 좋다.

"항상 정렬된" 속성

다음은 유효한 이진 탐색 트리의 예시이다:

각 왼쪽 자식 노드가 부모 노드보다 작고, 각 오른쪽 자식 노드가 부모 노드보다 크다는 점에 주목하라. 이는 이진 탐색 트리의 핵심 특징이다.

예를 들어, 2는 7보다 작으므로 왼쪽에 위치한다. 5는 2보다 크므로 오른쪽에 위치한다.

새로운 노드 삽입

새로운 값을 삽입할 때, 먼저 루트 노드와 값을 비교한다. 새로운 값이 더 작으면 왼쪽 가지로 이동하고, 더 크면 오른쪽 가지로 이동한다. 이 과정을 반복하며 트리를 따라 내려가다가 새로운 값을 삽입할 수 있는 빈 자리를 찾는다.

새로운 값 9를 삽입한다고 가정해 보자:

트리의 루트 노드(값이 7인 노드)에서 시작해 새로운 값 9와 비교한다.
9 > 7이므로 오른쪽 가지로 이동하고, 이번에는 값이 10인 노드에서 같은 과정을 반복한다.
9 < 10이므로 왼쪽 가지로 이동한다.
이제 더 이상 비교할 값이 없는 지점에 도달했다. 이 위치에 새로운 노드 9를 삽입한다.

새로운 값 9를 삽입한 후의 트리는 다음과 같다:

트리에서 새로운 엘리먼트를 삽입할 수 있는 위치는 단 하나뿐이다. 이 위치를 찾는 것은 일반적으로 빠르다. 이 과정은 O(h) 시간이 소요되며, 여기서 h는 트리의 높이를 의미한다.

참고: 노드의 높이는 해당 노드에서 가장 낮은 리프 노드까지 이동하는 데 필요한 단계 수를 의미한다. 전체 트리의 높이는 루트 노드에서 가장 낮은 리프 노드까지의 거리를 나타낸다. 이진 탐색 트리의 많은 연산은 트리의 높이를 기준으로 표현된다.

이 간단한 규칙(왼쪽에는 더 작은 값, 오른쪽에는 더 큰 값)을 따르면 트리가 정렬된 상태를 유지한다. 따라서 트리를 쿼리할 때마다 특정 값이 트리에 있는지 쉽게 확인할 수 있다.

트리 검색

트리에서 값을 찾기 위해 삽입과 동일한 단계를 수행한다:

값이 현재 노드보다 작으면 왼쪽 가지를 따라간다.
값이 현재 노드보다 크면 오른쪽 가지를 따라간다.
값이 현재 노드와 같으면 원하는 값을 찾은 것이다.

대부분의 트리 연산과 마찬가지로, 이 과정은 원하는 값을 찾거나 더 이상 살펴볼 노드가 없을 때까지 재귀적으로 수행된다.

다음은 값 5를 검색하는 예제이다:

트리 구조를 활용하면 검색이 빠르게 이루어진다. 이 연산은 O(h) 시간에 실행된다. 만약 백만 개의 노드로 이루어진 균형 잡힌 트리가 있다면, 이 트리에서 어떤 값을 찾는 데 약 20단계만 걸린다. (이 아이디어는 배열에서의 이진 검색과 매우 유사하다.)

트리 순회 방법

특정 노드만이 아니라 모든 노드를 살펴봐야 할 때가 있다.

이진 트리를 순회하는 방법은 세 가지가 있다:

중위 순회(in-order, 깊이 우선 순회): 노드의 왼쪽 자식을 먼저 확인한 후 노드 자체를 확인하고, 마지막으로 오른쪽 자식을 확인한다.
전위 순회(pre-order): 노드를 먼저 확인한 후 왼쪽과 오른쪽 자식을 확인한다.
후위 순회(post-order): 왼쪽과 오른쪽 자식을 먼저 확인하고, 마지막으로 노드 자체를 처리한다.

트리 순회는 재귀적으로 이루어진다.

이진 탐색 트리를 중위 순회하면 모든 노드를 낮은 값에서 높은 값으로 정렬된 순서대로 확인한다. 예제 트리의 경우 1, 2, 5, 7, 9, 10을 출력한다:

노드 삭제

노드를 삭제하는 작업은 간단하다. 노드를 제거한 후, 해당 노드를 왼쪽 서브트리에서 가장 큰 자식이나 오른쪽 서브트리에서 가장 작은 자식으로 대체한다. 이렇게 하면 삭제 후에도 트리가 정렬된 상태를 유지한다. 다음 예제에서는 10을 삭제하고 9(그림 2) 또는 11(그림 3)로 대체한다.

대체는 노드가 최소한 하나의 자식을 가질 때만 필요하다. 자식이 없는 경우, 단순히 부모와의 연결을 끊으면 된다:

코드 (해결책 1)

이론은 이 정도로 충분하다. 이제 Swift에서 이진 탐색 트리를 어떻게 구현할 수 있는지 살펴보자. 여러 가지 접근 방식이 있다. 먼저 클래스 기반 버전을 만드는 방법을 보여주고, 이후에 열거형(enum)을 사용하는 방법도 다룰 것이다.

다음은 BinarySearchTree 클래스의 예제다:

public class BinarySearchTree<T: Comparable> {
  private(set) public var value: T
  private(set) public var parent: BinarySearchTree?
  private(set) public var left: BinarySearchTree?
  private(set) public var right: BinarySearchTree?

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

  public var isRoot: Bool {
    return parent == nil
  }

  public var isLeaf: Bool {
    return left == nil && right == nil
  }

  public var isLeftChild: Bool {
    return parent?.left === self
  }

  public var isRightChild: Bool {
    return parent?.right === self
  }

  public var hasLeftChild: Bool {
    return left != nil
  }

  public var hasRightChild: Bool {
    return right != nil
  }

  public var hasAnyChild: Bool {
    return hasLeftChild || hasRightChild
  }

  public var hasBothChildren: Bool {
    return hasLeftChild && hasRightChild
  }

  public var count: Int {
    return (left?.count ?? 0) + 1 + (right?.count ?? 0)
  }
}

이 클래스는 전체 트리가 아닌 단일 노드를 표현한다. 제네릭 타입이므로 노드는 어떤 종류의 데이터든 저장할 수 있다. 또한 left와 right 자식 노드, 그리고 parent 노드에 대한 참조를 가지고 있다.

이 클래스를 사용하는 방법은 다음과 같다:

let tree = BinarySearchTree<Int>(value: 7)

count 프로퍼티는 이 노드가 표현하는 서브트리에 포함된 노드의 수를 반환한다. 이는 단순히 노드의 직계 자식만을 세는 것이 아니라, 그 자식들의 자식들까지 모두 포함한다. 만약 이 객체가 루트 노드라면, 전체 트리에 있는 노드의 수를 반환한다. 초기값은 count = 0이다.

참고: left, right, parent가 옵셔널 타입이므로 Swift의 옵셔널 체이닝(?)과 nil 병합 연산자(??)를 유용하게 활용할 수 있다. if let을 사용해도 되지만, 코드가 더 길어질 수 있다.

노드 삽입

트리 노드만으로는 아무런 쓸모가 없다. 여기서는 트리에 새로운 노드를 추가하는 방법을 알아본다.

  public func insert(value: T) {
    if value < self.value {
      if let left = left {
        left.insert(value: value)
      } else {
        left = BinarySearchTree(value: value)
        left?.parent = self
      }
    } else {
      if let right = right {
        right.insert(value: value)
      } else {
        right = BinarySearchTree(value: value)
        right?.parent = self
      }
    }
  }

다른 많은 트리 연산과 마찬가지로, 삽입도 재귀를 사용해 구현하는 것이 가장 간단하다. 새 값을 기존 노드의 값과 비교해 왼쪽 가지에 추가할지, 오른쪽 가지에 추가할지 결정한다.

더 이상 왼쪽이나 오른쪽 자식 노드가 없으면, 새 노드를 위해 BinarySearchTree 객체를 생성하고 parent 속성을 설정해 트리에 연결한다.

참고: 이진 탐색 트리의 핵심은 왼쪽에 더 작은 노드, 오른쪽에 더 큰 노드를 두는 것이다. 항상 루트에 요소를 삽입해 유효한 이진 트리를 유지해야 한다.

예제에서 전체 트리를 만들려면 다음과 같이 한다.

let tree = BinarySearchTree<Int>(value: 7)
tree.insert(2)
tree.insert(5)
tree.insert(10)
tree.insert(9)
tree.insert(1)

참고: 나중에 명확해질 이유로, 숫자를 무작위 순서로 삽입해야 한다. 정렬된 순서로 삽입하면 트리가 올바른 형태를 갖추지 못한다.

편의를 위해, 배열의 모든 요소에 대해 insert()를 호출하는 초기화 메서드를 추가한다.

  public convenience init(array: [T]) {
    precondition(array.count > 0)
    self.init(value: array.first!)
    for v in array.dropFirst() {
      insert(value: v)
    }
  }

이제 다음과 같이 간단히 트리를 생성할 수 있다.

let tree = BinarySearchTree<Int>(array: [7, 2, 5, 10, 9, 1])

배열의 첫 번째 값이 트리의 루트가 된다.

디버그 출력

복잡한 데이터 구조를 다룰 때는 사람이 읽기 쉬운 디버그 출력이 유용하다.

extension BinarySearchTree: CustomStringConvertible {
  public var description: String {
    var s = ""
    if let left = left {
      s += "(\(left.description)) <- "
    }
    s += "\(value)"
    if let right = right {
      s += " -> (\(right.description))"
    }
    return s
  }
}

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

((1) <- 2 -> (5)) <- 7 -> ((9) <- 10)

루트 노드는 가운데에 위치한다. 약간의 상상력을 발휘하면 이 출력이 실제로 다음과 같은 트리 구조와 일치함을 알 수 있다:

중복된 항목을 삽입할 때 어떤 일이 발생하는지 궁금할 것이다. 중복된 항목은 항상 오른쪽 가지에 삽입된다. 직접 시도해 보자!

검색

이제 트리에 몇 가지 값이 있으니 무엇을 해야 할까? 당연히 값을 검색해야 한다! 빠르게 항목을 찾는 것이 이진 검색 트리의 주요 목적이다. :-)

다음은 search()의 구현이다:

  public func search(value: T) -> BinarySearchTree? {
    if value < self.value {
      return left?.search(value)
    } else if value > self.value {
      return right?.search(value)
    } else {
      return self  // 찾았다!
    }
  }

로직이 명확하기를 바란다: 이 메서드는 현재 노드(보통 루트)에서 시작해 값을 비교한다. 검색 값이 노드의 값보다 작으면 왼쪽 가지에서 계속 검색하고, 검색 값이 더 크면 오른쪽 가지로 들어간다.

더 이상 볼 노드가 없을 때(left나 right가 nil일 때) 검색 값이 트리에 없다는 것을 나타내기 위해 nil을 반환한다.

참고: Swift에서는 옵셔널 체이닝을 통해 편리하게 처리할 수 있다. left?.search(value)라고 작성하면 left가 nil일 때 자동으로 nil을 반환한다. if 문으로 명시적으로 확인할 필요가 없다.

검색은 재귀적인 과정이지만, 간단한 루프로도 구현할 수 있다:

  public func search(_ value: T) -> BinarySearchTree? {
    var node: BinarySearchTree? = self
    while let n = node {
      if value < n.value {
        node = n.left
      } else if value > n.value {
        node = n.right
      } else {
        return node
      }
    }
    return nil
  }

이 두 구현이 동일하다는 것을 확인해 보라. 개인적으로 나는 재귀 코드보다 반복 코드를 선호하지만, 여러분의 의견은 다를 수 있다. ;-)

검색을 테스트하는 방법은 다음과 같다:

tree.search(5)
tree.search(2)
tree.search(7)
tree.search(6)   // nil

처음 세 줄은 해당 BinaryTreeNode 객체를 반환한다. 마지막 줄은 값이 6인 노드가 없기 때문에 nil을 반환한다.

참고: 트리에 중복 항목이 있으면 search()는 "가장 높은" 노드를 반환한다. 루트에서 아래로 검색을 시작하기 때문에 이는 합리적이다.

트리 순회

트리의 모든 노드를 탐색하는 세 가지 방법을 기억하는가? 여기 그 방법들이 있다:

  public func traverseInOrder(process: (T) -> Void) {
    left?.traverseInOrder(process: process)
    process(value)
    right?.traverseInOrder(process: process)
  }

  public func traversePreOrder(process: (T) -> Void) {
    process(value)
    left?.traversePreOrder(process: process)
    right?.traversePreOrder(process: process)
  }

  public func traversePostOrder(process: (T) -> Void) {
    left?.traversePostOrder(process: process)
    right?.traversePostOrder(process: process)
    process(value)
  }

이 모든 메서드는 동일하게 작동하지만 순서만 다르다. 모든 작업은 재귀적으로 수행된다. Swift의 옵셔널 체이닝은 왼쪽이나 오른쪽 자식 노드가 없을 때 traverseInOrder() 등의 호출이 무시됨을 명확히 보여준다.

트리의 모든 값을 낮은 순서부터 높은 순서로 정렬하여 출력하려면 다음과 같이 작성한다:

tree.traverseInOrder { value in print(value) }

이 코드는 다음과 같은 결과를 출력한다:

트리에 map()이나 filter()와 같은 기능을 추가할 수도 있다. 예를 들어, map()을 구현한 코드는 다음과 같다:

  public func map(formula: (T) -> T) -> [T] {
    var a = [T]()
    if let left = left { a += left.map(formula: formula) }
    a.append(formula(value))
    if let right = right { a += right.map(formula: formula) }
    return a
  }

이 코드는 트리의 각 노드에 대해 formula 클로저를 호출하고 결과를 배열에 저장한다. map()은 트리를 중위 순회하며 작동한다.

map()을 사용하는 매우 간단한 예제는 다음과 같다:

  public func toArray() -> [T] {
    return map { $0 }
  }

이 코드는 트리의 내용을 정렬된 배열로 변환한다. 플레이그라운드에서 직접 시도해 볼 수 있다:

tree.toArray()   // [1, 2, 5, 7, 9, 10]

연습 문제로, filter와 reduce를 구현해 보자.

노드 삭제

코드 가독성을 높이기 위해 몇 가지 헬퍼 함수를 정의한다.

  private func reconnectParentTo(node: BinarySearchTree?) {
    if let parent = parent {
      if isLeftChild {
        parent.left = node
      } else {
        parent.right = node
      }
    }
    node?.parent = parent
  }

트리를 변경하려면 parent, left, right 포인터를 수정해야 한다. 이 함수는 현재 노드의 부모를 다른 노드에 연결하는 데 도움을 준다. 여기서 '다른 노드'는 현재 노드의 자식 중 하나가 된다.

또한 노드의 최솟값과 최댓값을 반환하는 함수가 필요하다:

  public func minimum() -> BinarySearchTree {
    var node = self
    while let next = node.left {
      node = next
    }
    return node
  }

  public func maximum() -> BinarySearchTree {
    var node = self
    while let next = node.right {
      node = next
    }
    return node
  }

나머지 코드는 자명하다:

  @discardableResult public func remove() -> BinarySearchTree? {
    let replacement: BinarySearchTree?

    // 현재 노드를 대체할 노드는 왼쪽 서브트리의 최댓값 또는 
    // 오른쪽 서브트리의 최솟값 중 nil이 아닌 값으로 선택
    if let right = right {
      replacement = right.minimum()
    } else if let left = left {
      replacement = left.maximum()
    } else {
      replacement = nil
    }

    replacement?.remove()

    // 대체 노드를 현재 노드 위치에 배치
    replacement?.right = right
    replacement?.left = left
    right?.parent = replacement
    left?.parent = replacement
    reconnectParentTo(node:replacement)

    // 현재 노드는 더 이상 트리의 일부가 아니므로 정리
    parent = nil
    left = nil
    right = nil

    return replacement
  }

노드의 깊이와 높이

노드의 높이는 해당 노드에서 가장 낮은 리프 노드까지의 거리를 의미한다. 다음 함수를 통해 이를 계산할 수 있다:

  public func height() -> Int {
    if isLeaf {
      return 0
    } else {
      return 1 + max(left?.height() ?? 0, right?.height() ?? 0)
    }
  }

왼쪽과 오른쪽 가지의 높이를 확인하고 더 큰 값을 선택한다. 이 역시 재귀적인 방법이다. 이 함수는 노드의 모든 자식을 확인하므로 성능은 **O(n)**이다.

참고: Swift의 null-coalescing 연산자는 left나 right 포인터가 nil인 경우를 간단히 처리하기 위해 사용된다. if let을 사용해도 되지만 이 방법이 더 간결하다.

실행 예시:

tree.height()  // 2

노드의 깊이도 계산할 수 있다. 깊이는 루트 노드까지의 거리를 의미한다. 다음은 이를 계산하는 코드다:

  public func depth() -> Int {
    var node = self
    var edges = 0
    while let parent = node.parent {
      node = parent
      edges += 1
    }
    return edges
  }

이 코드는 parent 포인터를 따라 트리를 위로 올라가며 루트 노드(parent가 nil인 노드)에 도달할 때까지 반복한다. 이 과정은 O(h) 시간이 걸린다. 실행 예시는 다음과 같다:

if let node9 = tree.search(9) {
  node9.depth()   // returns 2
}

선행자와 후행자

이진 탐색 트리는 항상 "정렬"된 상태를 유지하지만, 연속된 숫자가 실제로 트리에서 서로 인접해 있는 것은 아니다.

7 바로 앞에 오는 숫자를 찾기 위해 왼쪽 자식 노드만 보는 것은 불가능하다. 왼쪽 자식은 2이며, 5가 아니다. 마찬가지로 7 바로 뒤에 오는 숫자도 단순히 오른쪽 자식 노드만으로는 찾을 수 없다.

predecessor() 함수는 현재 값보다 정렬 순서상 앞에 오는 노드를 반환한다:

public func predecessor() -> BinarySearchTree<T>? {
    if let left = left {
        return left.maximum()
    } else {
        var node = self
        while let parent = node.parent {
            if parent.value < value { return parent }
            node = parent
        }
        return nil
    }
}

왼쪽 서브트리가 존재한다면 간단하다. 이 경우, 바로 앞에 오는 값은 해당 서브트리의 최댓값이다. 위 그림에서 5가 7의 왼쪽 가지에서 가장 큰 값임을 확인할 수 있다.

왼쪽 서브트리가 없다면, 더 작은 값을 가진 부모 노드를 찾을 때까지 부모 노드를 계속 탐색한다. 예를 들어 9의 선행자를 찾으려면, 더 작은 값을 가진 첫 번째 부모 노드인 7을 발견할 때까지 위로 올라간다.

successor() 함수는 동일한 방식으로 작동하지만, 방향이 반대다:

public func successor() -> BinarySearchTree<T>? {
    if let right = right {
        return right.minimum()
    } else {
        var node = self
        while let parent = node.parent {
            if parent.value > value { return parent }
            node = parent
        }
        return nil
    }
}

이 두 메서드 모두 O(h) 시간 복잡도를 가진다.

참고: "스레드" 이진 트리라는 변형이 있다. 이 트리에서는 "사용되지 않는" 왼쪽과 오른쪽 포인터를 재활용해 선행자와 후행자 노드 사이에 직접 연결을 만든다. 매우 영리한 방법이다!

검색 트리가 유효한가?

검색 트리를 고의로 무효화하려면 루트가 아닌 노드에서 insert()를 호출하면 된다. 다음은 그 예시다:

if let node1 = tree.search(1) {
  node1.insert(100)
}

루트 노드의 값은 7이므로 100 값을 가진 노드는 트리의 오른쪽 가지에 위치해야 한다. 하지만 이 경우 루트가 아닌 트리의 왼쪽 가지에 있는 리프 노드에 삽입한다. 따라서 새로운 100 노드는 트리에서 잘못된 위치에 있게 된다!

결과적으로 tree.search(100)을 호출하면 nil이 반환된다.

다음 메서드를 사용해 트리가 유효한 이진 검색 트리인지 확인할 수 있다:

  public func isBST(minValue: T, maxValue: T) -> Bool {
    if value < minValue || value > maxValue { return false }
    let leftBST = left?.isBST(minValue: minValue, maxValue: value) ?? true
    let rightBST = right?.isBST(minValue: value, maxValue: maxValue) ?? true
    return leftBST && rightBST
  }

이 메서드는 왼쪽 가지가 현재 노드의 값보다 작은 값만 포함하고, 오른쪽 가지가 현재 노드의 값보다 큰 값만 포함하는지 검증한다.

다음과 같이 호출한다:

if let node1 = tree.search(1) {
  tree.isBST(minValue: Int.min, maxValue: Int.max)  // true
  node1.insert(100)                                 // EVIL!!!
  tree.search(100)                                  // nil
  tree.isBST(minValue: Int.min, maxValue: Int.max)  // false
}

코드 (해결책 2)

이진 트리 노드를 클래스로 구현했지만, 열거형(enum)을 사용할 수도 있다.

차이점은 참조 의미론과 값 의미론에 있다. 클래스 기반 트리를 변경하면 메모리 내 동일한 인스턴스가 업데이트된다. 반면 열거형 기반 트리는 불변성을 가진다. 삽입이나 삭제를 수행하면 완전히 새로운 트리의 복사본을 얻게 된다. 어떤 방식이 더 나은지는 사용 목적에 따라 달라진다.

다음은 열거형을 사용해 이진 탐색 트리를 만드는 방법이다:

public enum BinarySearchTree<T: Comparable> {
  case Empty
  case Leaf(T)
  indirect case Node(BinarySearchTree, T, BinarySearchTree)
}

이 열거형은 세 가지 케이스로 구성된다:

Empty: 브랜치의 끝을 표시한다 (클래스 기반 버전에서는 nil 참조를 사용했다).
Leaf: 자식이 없는 리프 노드.
Node: 하나 또는 두 개의 자식을 가진 노드. indirect 키워드를 사용해 BinarySearchTree 값을 보유할 수 있다. indirect 없이는 재귀적 열거형을 만들 수 없다.

참고: 이 이진 트리의 노드들은 부모 노드에 대한 참조를 가지고 있지 않다. 큰 문제는 아니지만, 특정 작업을 구현하기가 더 번거로워질 수 있다.

이 구현은 재귀적이며, 열거형의 각 케이스는 다르게 처리된다. 예를 들어, 트리의 노드 수와 트리의 높이를 계산하는 방법은 다음과 같다:

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

  public var height: Int {
    switch self {
    case .Empty: return -1
    case .Leaf: return 0
    case let .Node(left, _, right): return 1 + max(left.height, right.height)
    }
  }

새로운 노드를 삽입하는 방법은 다음과 같다:

  public func insert(newValue: T) -> BinarySearchTree {
    switch self {
    case .Empty:
      return .Leaf(newValue)

    case .Leaf(let value):
      if newValue < value {
        return .Node(.Leaf(newValue), value, .Empty)
      } else {
        return .Node(.Empty, value, .Leaf(newValue))
      }

    case .Node(let left, let value, let right):
      if newValue < value {
        return .Node(left.insert(newValue), value, right)
      } else {
        return .Node(left, value, right.insert(newValue))
      }
    }
  }

플레이그라운드에서 테스트해보자:

var tree = BinarySearchTree.Leaf(7)
tree = tree.insert(2)
tree = tree.insert(5)
tree = tree.insert(10)
tree = tree.insert(9)
tree = tree.insert(1)

각 삽입마다 새로운 트리 객체가 반환되므로, 결과를 tree 변수에 다시 할당해야 한다.

검색 함수는 다음과 같다:

  public func search(x: T) -> BinarySearchTree? {
    switch self {
    case .Empty:
      return nil
    case .Leaf(let y):
      return (x == y) ? self : nil
    case let .Node(left, y, right):
      if x < y {
        return left.search(x)
      } else if y < x {
        return right.search(x)
      } else {
        return self
      }
    }
  }

대부분의 함수는 동일한 구조를 가진다.

플레이그라운드에서 테스트해보자:

tree.search(10)
tree.search(1)
tree.search(11)   // nil

디버깅 목적으로 트리를 출력하려면 다음 메서드를 사용한다:

extension BinarySearchTree: CustomDebugStringConvertible {
  public var debugDescription: String {
    switch self {
    case .Empty: return "."
    case .Leaf(let value): return "\(value)"
    case .Node(let left, let value, let right):
      return "(\(left.debugDescription) <- \(value) -> \(right.debugDescription))"
    }
  }
}

print(tree)를 실행하면 다음과 같이 출력된다:

((1 <- 2 -> 5) <- 7 -> (9 <- 10 -> .))

루트 노드는 가운데에 위치하며, 점(.)은 해당 위치에 자식이 없음을 의미한다.

트리가 불균형해질 때...

이진 탐색 트리는 왼쪽과 오른쪽 서브트리가 같은 수의 노드를 포함할 때 균형을 이룬다. 이 경우 트리의 높이는 *log(n)*이 되며, 여기서 n은 노드의 수다. 이것이 이상적인 상황이다.

한쪽 가지가 다른 쪽보다 훨씬 길어지면 탐색 속도가 매우 느려진다. 필요한 것보다 더 많은 값을 확인하게 된다. 최악의 경우 트리의 높이가 n이 될 수 있다. 이런 트리는 이진 탐색 트리보다 연결 리스트처럼 동작하며, 성능이 **O(n)**으로 떨어진다. 좋지 않은 상황이다!

이진 탐색 트리를 균형 있게 만드는 한 가지 방법은 노드를 완전히 무작위 순서로 삽입하는 것이다. 평균적으로는 트리가 잘 균형을 이룰 가능성이 높지만, 항상 보장되지는 않으며 실용적이지 않을 수도 있다.

다른 해결책은 자동 균형 이진 트리를 사용하는 것이다. 이 자료구조는 노드를 삽입하거나 삭제한 후에도 트리가 균형을 유지하도록 조정한다. 구체적인 예제는 AVL 트리와 레드-블랙 트리를 참고하라.

함께 보기

위키피디아의 이진 탐색 트리

Swift 알고리즘 클럽을 위해 Nicolas Ameghino와 Matthijs Hollemans가 작성