이진 검색 트리(Binary Search Tree)

[최종 수정일 : 2017.05.25]

원문 : https://github.com/raywenderlich/swift-algorithm-club/tree/master/Binary%20Search%20Tree

이진 검색 트리(Binary Search Tree)

이진 검색 트리는 트리가 항상 정렬되도록 삽입과 삭제를 수행하는 이진 트리(binary tree)(각 노드가 최대 두명의 자식을 가지는 트리)의 특별한 종류입니다.

트리(tree)에 대한 더 자세한 정보는, 트리(tree)를 먼저 읽어보세요.

항상 정렬된 속성(Always sorted property)

다음은 유효한 이진 검색 트리의 예입니다.

각 왼쪽 자식이 부모 노드보다 작고, 각 오른쪽 자식이 부모 노드보다 크다는 것을 주목(notice)하세요. 이것이 이진 검색 트리의 핵심 기능입니다.

예를 들어, 2는 7보다 작으므로, 왼족으로 이동합니다, 5는 2보다 크므로 오른쪽으로 이동합니다.

새로운 노드 삽입하기(Inserting new nodes)

삽입을 수행할때, 먼저 새로운 값을 루트 노드(root node)와 비교합니다. 새 값이 작다면, 왼쪽(left) 가지(branch)를 가집니다. 크다면, 오른쪽(right) 가지를 가집니다. 새로운 값을 삽입할 빈 자리를 찾을때까지 이 방법으로 트리(tree) 아래로 내려갑니다.

새로운 값 9를 삽입하길 원한다고 가정합시다

• 트리(7로 된 노드)의 루트에서 시작하고 새 값 9와 비교합니다.
• 9 > 7, 그래서 오른쪽 가지로 내려가고 노드 10에서 같은 동작을 반복합니다.
• 9 < 10이기 때문에, 왼쪽 가지로 내려갑니다.
• 더 이상 비교할 필요가 없는 시점에 도달했습니다. 9에 대한 새로운 노드는 해당 위치에 삽입됩니다.

새로운 값 9가 삽입된 후의 트리는 다음과 같습니다.

새 요소를 트리에 삽입할 수 있는 위치는 하나 뿐입니다. 이 장소를 찾는 것이 일반적으로 빠릅니다. 그것은 O(h)시간을 가지며, h는 트리(tree)의 높이(height)입니다.

주의
노드의 높이(height)는 해당 노드에서 가장 낮은 잎(leaf)으로 이동하는데 필요한 단계의 수입니다. 전체 트리(tree)의 높이는 루트(root)에서 가장 낮은 잎(leaf)까지의 거리입니다.

이러한 간단한 규칙에 따르면 - 왼쪽에 작은 값, 오른쪽에 큰 값 - 트리를 정렬된 상태로 유지하므로 쿼리할때마다 값이 트리에 있는지 확인할 수 있습니다.

트리 검색하기

트리에서 값을 찾으려면, 삽입과 동일한 단계를 수행합니다.

• 값이 현재 노드보다 작으면, 왼쪽 가지를 가집니다.
• 값이 현재 노드보다 크면, 오른쪽 가지를 가집니다.
• 값이 현재 노드와 같으면, 찾았습니다.

대부분의 트리 작업과 마찬가지로, 우리가 찾고 있는 것을 찾거나 봐야할 노드가 없을때까지 재귀적으로 수행됩니다.

값 5를 검색하는 예제는 다음과 같습니다.

검색은 트리의 구조를 사용해서 빠릅니다. O(h)시간이 걸립니다. 백만개의 노드가 있는 균형 잡힌 나무가 있다면, 트리에서 아무것도 발견하지 못하는데 20단계가 걸립니다.(그 아이디어는 배열에서 이진 검색(binary search)와 매우 비슷합니다.)

트리 탐색하기(Traversing the tree)

가끔씩 하나의 노드가 아닌 다른 모든 노트드를 봐야할 필요가 있습니다.

이진 트리를 탐색(traverse) 방법은 세가지가 있습니다.

1. 중위(In-order) (또는 첫번째 깊이) : 먼저 노드의 왼쪽 자식을 보고 노드 자체를 보고 마지막으로 오른쪽 자식을 봅니다.
2. 전위(Pre-order) : 노드를 먼저 보고 왼쪽과 오른쪽 자식을 봅니다.
3. 후위(Post-order) : 먼저 왼쪽과 오른쪽 자식을 보고 노드 자체를 마지막으로 처리 합니다.

트리 탐색(traversing)하는 것은 재귀적으로 발생합니다.

이진 검색 트리를 순서대로 탐색하는 경우, 모든 노드를 낮은 곳에서 높은곳으로 정렬된 것으로 보입니다. 트리 예제에 대해서, 1, 2, 5, 7, 9, 10을 출력합니다.

노드 삭제하기(Deleting nodes)

노드를 제거하는 것은 쉽습니다. 노드를 제거한 후에, 노드를 왼쪽에서 가장 큰 자식 또는 오른쪽에서 가장 작은 자식으로 바꿉니다. 그런식으로 제거된 후에도 트리는 정렬되어 있습니다. 다음 예제 처럼, 10은 제거되고 9(그림2) 또는 11(그림3)로 교체 됩니다.

노드가 최소한 하나의 자식을 가질때 교체가 필요하다는 것을 주의합니다. 자식이 없다면, 부모와의 연결을 끊습니다.

코드(해결책 1)

이론(theory)은 충분합니다. Swift에서 이진 검색 트리 구현하는 방법을 봅시다. 여러가지 접근 방법이 있습니다. 첫번째로, 클래스 기반 버전을 만드는 방법을 보여줄것이지만, 열거형을 사용해서 만드는 방법도 볼것입니다.

다음은 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` 순서로 작성할수 있지만, 간결(concise)하지는 않습니다.

노드 삽입하기

자체적으로 트리노드는 쓸모없으며, 다음은 트리에 새 노드를 추가하는 방법입니다.

  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()를 호출하는 init 메소드를 추가해 봅시다.

  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)

루트 노드는 중간에 있습니다. 약간의 상상력을 가지고, 실제로 다음 트리에 해당하는 것을 알아야 합니다.

중복된 항목들을 삽입할때 어떤 일이 발생하는지 궁금할 것입니다. 우리는 항상 그것들을 오른쪽 가지에 삽입합니다. 시도해 보세요!

검색하기(Searching)

우리가 트리에 어떤 값을 가지고 있을때 무엇을 해야 하나요? 당연히 검색합니다! 이진 검색트리의 주 목적은 항목들을 빨리 찾는 것입니다.

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  // found it!
    }
  }

로직이 명확하길 바랍니다 : 현재 노드(일반적으로 루트)에서 시작하고 값을 비교합니다. 검색 값은 노드의 값보다 작으며, 왼쪽 가지에서 계속 검색합니다. : 검색 값보다 크면, 오른쪽 가지로 갑니다.

봐야할 노드가 더 이상 없다면 - left또는 right가 nil일때 - 검색 값이 트리에 없을 나타내기 위해 nil을 반환합니다.

주의
Swift에서, 옵셔널 체이닝을 사용하면 편리합니다. left?.search(value)를 작성할때 left가 nil이면 자동으로 nil을 반환합니다. if문을 사용해서 명시적으로 확인할 필요가 없습니다.

검색은 재귀 처리이지만, 대신에 단순한 반복문으로 구현할 수 있습니다.

  public func search(value: T) -> BinarySearchTree? {
    var node: BinarySearchTree? = self
    while case 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

첫번째 3줄은 해당하는 BinaryTreeNode 객체를 반환합니다. 값 6을 가진 노드가 없기 때문에, 마지막 줄은 nil을 반환합니다.

주의
트리에서 항목들이 중복되면, search()는 가장 높은 노드를 반환합니다. 루프에서 아래쪽으로 검색하기 때문에 의미가 있습니다.

탐색(Traversal)

트리에서 모든 노드들을 보는 3가지 다른 방법이 있다는 것을 기억하시나요? 그것들은 다음과 같습니다.

  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) }

이것은 다음과 같이 출력됩니다.

1
2
5
7
9
10

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()은 중위(in-order)로 트리를 탐색하여 동작합니다.

map()의 사용법에 대한 간단한 예입니다. :

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

트리의 내용을 정렬된 배열로 바뀝니다. 플레이그라운드에서 시도해 보세요.

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

연습에서, filter와 reduce 구현할 수 있는지 보세요.

노드 삭제하기

도움을 주는 함수를 정의해서 코드를 더 쉽게 읽을 수 있습니다.

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

트리를 변경하려면 parent와 left, right 포인터를 변경해야 합니다. 이 함수는 구현에 도움을 줍니다. 현재 모드의 부모를 가지고 - self입니다 - self의 자식 중 하나로 다른 노드에 접속합니다.

노드의 최소값과 최대값은 반환하는 함수가 필요합니다.

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

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

나머지 코드는 자명합니다(self-explanatory).

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

    // Replacement for current node can be either biggest one on the left or
    // smallest one on the right, whichever is not nil
    if let right = right {
      replacement = right.minimum()
    } else if let left = left {
      replacement = left.maximum()
    } else {
      replacement = nil
    }

    replacement?.remove()

    // Place the replacement on current node's position
    replacement?.right = right
    replacement?.left = left
    right?.parent = replacement
    left?.parent = replacement
    reconnectParentTo(node:replacement)

    // The current node is no longer part of the tree, so clean it up.
    parent = nil
    left = nil
    right = nil

    return replacement
  }

깊이와 높이(Depth and height)

노드의 높이는 가장 낮은 잎까지의 거리라는 것을 기억합니다. 다음 함수로 그것을 계산 할 수 있습니다.

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

왼쪽과 오른쪽 가지의 높이에서 가장 높은 값을 가져옵니다. 또다시, 이것은 재귀 방식입니다. 노드의 모든 자식노드를 보게 되므로, 성능은 O(n)입니다.

주의
Swift의 null 결합 연산자는 left나 right가 nil을 가리킬때 간단하게 사용됩니다. if let으로 작성할수 있지만, 이것이 더 간단합니다.

이렇게 해보세요. :

tree.height()  // 2

루트와의 거리를 노드의 깊이(depth)를 계산할수 있습니다. 코드는 다음과 같습니다.

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

루트 노드(parent가 nil)에 도달할때까지 parent 포인터 다음에 트리를 위로 이동합니다. 여기에서 O(h)시간이 걸립니다. 예제는 다음과 같습니다.

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

선임자와 후임자(Predecessor and successor)

이진 검색 트리는 항상 정렬되어 있지만, 실제 트리에서 
연속적인 숫자가 옆에 있는것을 의미하는 것은 아닙니다.

왼쪽 자식노드만 보고 7이전에 오는 숫자를 찾을수 없는 것을 주의합니다. 왼족 자식은 5가 아니라 2입니다. 7 이후에 오는 숫자도 마찬가지(likewise) 입니다.

predecessor()함수는 정렬된 순서로 현재값 앞에 오는 노드를 반환합니다.

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

그것이 왼쪽 서브트리에 있으면 쉽습니다. 이 경우에, 바로 선임자(predecessor)는 서브트리에서 최대값입니다. 위의 그림에서 5가 실제로 7의 왼쪽 가지에서 최대 값임을 확인 할 수 있습니다.

왼쪽 서브트리가 없다면, 더 작은 값을 찾을때까지 부모 노드를 봐야합니다. 노드 9의 선임자가 무엇인지 알고 있다면, 첫번째 부모가 더 작은 값을 찾을때까지 계속 올라가며 이 값은 7입니다.

successor()의 코드는 같은 방식으로 동작하지만 미러링됩니다.

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

두가지 방법 모두 O(h) 시간에 실행됩니다.

주의 
선임자 노드와 후임자 노드 사이를 직접연결하기 위해 사용되지 않는 왼쪽과 오른쪽 위치를 다른 목적으로 이용하는 것을 다른말로 스레드 이진 트리(threaded binary tree) 라고 합니다. 매우 영리합니다!

검색 트리가 유효하나요?

루트 노트가 아닌 곳에서 insert()호출로 의도적으로 방해하려한다면 이진 검색 트리를 유효하지 않는 트리로 바꿀수 있습니다.

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

루트 노드의 값이 7이므로 값 100인 노드는 트리의 오른쪽 가지에 있어야 합니다. 하지만, 루트에 삽입하지 않고 트리의 왼쪽 가지에 있는 잎(leaf) 노드에 삽입합니다. 새로운 100노드는 트리에서 잘못된 위치에 있습니다.

결과적으로, tree.search(100)은 nil이 반환됩니다.

다음 메소드로 트리가 유효한 이진 검색트리인지 확인 할수 있습니다.

  public func isBST(minValue 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)

이진 트리 노드를 클래스로 구현했지만, 열거형을 사용해서도 가능합니다.

차이점은 참조 의미 대 값 의미입니다. 클래스 기반의 트리를 변경하면 메모리에서 같은 인스턴스가 업데이트 될것이지만, 열거형 기반의 트리는 변하지 않습니다 – 모든 삽입 또는 삭제는 완전히 새로운 트리 복사본을 제공합니다. 어느쪽이 가장 좋은지는 어떤 것을 사용하길 원하는지에 달려있습니다.

다음은 열거형으로 이진 검색 트리를 만드는 방법입니다.

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

열거형에는 3가지 경우가 있습니다.

• 가지(branch)의 끝을 표시하기 위해 Empty를 사용(클래스 기반 버전에서는 nil참조를 사용했습니다)
• 자식(child)이 없는 잎(leaf) 노드에 대해 Leaf를 사용
• 노드가 하나 또는 두개의 자식을 가지는 노드에 대해 Node를 사용. BinarySearchTree 값을 보유할 수 있도록 indirect로 표시됩니다. 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 0
    case .Leaf: return 1
    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 -> .))

루트 노드가 중간에 있고, 점은 그 위치에 자식이 없는 것을 의미합니다.

트리의 균형이 깨질때…(When the tree becomes unbalanced…)

이진 검색 트리는 왼쪽과 오른쪽 서브트리에 동일한 노드의 수가 포함될때 균형(balanced)을 이룹니다. 이 경우에, 트리의 높이는 log(n)이며, n은 노드의 숫자 입니다. 그것은 이상적인 상황입니다.

가지 하나가 다른 곳보다 매우 길면, 검색은 매우 느려집니다. 필요로 하는 것보다 더 많은 값을 확인 하게 됩니다. 최악의 경우, 트리의 높이가 n이 될수 있습니다. 이러한 트리는 이진 검색 트리보다 성능이 O(n)으로 저하되는 연결 리스트(linked list)처럼 동작합니다. 좋지 않습니다!

이진 검색 트리를 균형있게 만드는 한가지 방법은 임의의 순서로 노드를 삽입합니다. 평균적으로 트리의 균형이 잡혀야 하지만 보장되지 않으며, 언제나 실용적이지 않습니다.

다른 해결책은 스스로 균형잡힌(self-balancing) 이진 트리를 사용하는 것입니다. 이러한 타입의 데이터 구조는 노드를 삽입하거나 삭제를 한후에 균형을 유지하도록 트리를 조정합니다. 예를 보려면, AVL tree와 red-black tree를 확인하세요.

이것도 보세요(See also)

위키피디아에 있는 이진 검색트리(Binary Search Tree on Wikipedia)