스레드 이진 트리

스레드 이진 트리는 특수한 형태의 이진 트리이다. 각 노드가 최대 두 개의 자식을 가지는 이진 트리에 몇 가지 추가 변수를 포함해 중위 순회를 빠르고 효율적으로 수행할 수 있도록 설계했다. 이번 장에서는 스레드 이진 트리의 일반적인 구조와 Swift로 구현한 완전한 기능을 갖춘 스레드 이진 트리에 대해 알아본다.

트리의 개념이나 용도에 대해 잘 모른다면 이 글을 먼저 읽어보자.

순차 순회(In-order traversal)

스레드 이진 트리를 더 간단하고 작은 표준 이진 트리 대신 사용하는 주요 이유는 트리의 순차 순회 속도를 높이기 위해서다. 이진 트리의 순차 순회는 노드가 저장된 순서대로 방문하며, 이는 이진 탐색 트리의 기본 정렬과 일치한다. 즉, 대부분의 스레드 이진 트리는 이진 탐색 트리이기도 하다. 순차 순회는 먼저 노드의 왼쪽 자식을 방문하고, 노드 자체를 방문한 후 마지막으로 오른쪽 자식을 방문한다.

일반적으로 이진 트리의 순차 순회는 다음과 같이 진행된다(Swift 구문 사용):

func traverse(n: Node?) {
  if (n == nil) { return
  } else {
    traverse(n.left)
    visit(n)
    traverse(n.right)
  }
}

여기서 n은 트리의 노드(또는 nil)를 나타내며, 각 노드는 자식을 left와 right로 저장한다. "방문"은 노드에 대해 원하는 작업을 수행하는 것을 의미한다. 이 함수를 호출할 때는 순회하려는 트리의 루트를 전달한다.

이 알고리즘은 단순하고 이해하기 쉽지만, 재귀적 특성 때문에 트리의 높이에 비례하는 스택 공간을 사용한다. 트리에 n개의 노드가 있을 때, 이 사용량은 상당히 균형 잡힌 트리의 경우 **O(log n)**에서 매우 불균형한 트리의 경우 **O(n)**까지 다양할 수 있다.

스레드 이진 트리는 이 문제를 해결한다.

순차 순회에 대한 더 자세한 정보는 여기를 참고한다.

선행 노드와 후행 노드

트리를 중위 순회하면 노드들이 선형으로 정렬된다. 따라서 각 노드는 **선행 노드(predecessor)**와 **후행 노드(successor)**를 모두 갖는다. 단, 첫 번째 노드는 후행 노드만, 마지막 노드는 선행 노드만 갖는다. 스레드 이진 트리에서는 일반적으로 nil이 되는 왼쪽 자식 대신 선행 노드를 저장하고, nil이 되는 오른쪽 자식 대신 후행 노드를 저장한다. 이 점이 일반 이진 트리와 스레드 이진 트리를 구분 짓는다.

스레드 이진 트리는 두 가지 유형이 있다: 단일 스레드 트리와 이중 스레드 트리:

단일 스레드 트리는 중위 순회 시 선행 노드 또는 후행 노드 중 하나만 추적한다(왼쪽 또는 오른쪽).
이중 스레드 트리는 중위 순회 시 선행 노드와 후행 노드 모두를 추적한다(왼쪽과 오른쪽).

단일 또는 이중 스레드 트리를 사용할지는 목적에 따라 결정한다. 트리를 한 방향으로만 순회할 필요가 있다면(앞으로 또는 뒤로) 단일 스레드 트리를 사용한다. 양방향으로 순회해야 한다면 이중 스레드 트리를 사용한다.

각 노드는 선행 노드 또는 왼쪽 자식 중 하나를, 후행 노드 또는 오른쪽 자식 중 하나를 저장한다. 노드가 두 가지를 모두 추적할 필요는 없다. 예를 들어, 이중 스레드 트리에서 노드에 오른쪽 자식은 있지만 왼쪽 자식이 없다면, 왼쪽 자식 대신 선행 노드를 추적한다.

다음은 유효한 "완전한" 스레드 이진 트리의 예시다:

반면, 다음 스레드 이진 트리는 "완전하지" 않지만 여전히 유효하다. 트리의 구조는 이진 탐색 트리의 정의만 따르면 상관없다:

실선은 부모와 자식 간의 연결을 나타내고, 점선은 "스레드"를 나타낸다. 자식과 스레드 간의 상호작용을 주의 깊게 살펴봐야 한다. 루트를 제외한 모든 노드는 하나의 진입 간선(부모로부터)과 두 개의 진출 간선을 갖는다. 하나는 왼쪽으로, 다른 하나는 오른쪽으로 나간다. 왼쪽 진출 간선은 왼쪽 자식이 있으면 왼쪽 자식으로, 없으면 중위 순회 선행 노드로 연결된다. 오른쪽 진출 간선은 오른쪽 자식이 있으면 오른쪽 자식으로, 없으면 중위 순회 후행 노드로 연결된다. 단, 가장 왼쪽 노드는 선행 노드가 없고, 가장 오른쪽 노드는 후행 노드가 없다.

표현

스레드 이진 트리의 메서드를 자세히 살펴보기 전에, 먼저 트리 자체가 어떻게 표현되는지 설명한다. 이 데이터 구조의 핵심은 ThreadedBinaryTree<T: Comparable> 클래스다. 이 클래스의 각 인스턴스는 value, parent, left, right, leftThread, rightThread라는 여섯 개의 멤버 변수를 가진 노드를 나타낸다. 이 중 value만 필수이며, 나머지 다섯 개는 Swift의 옵셔널 타입이다(값이 nil일 수 있다).

value: T는 이 노드의 값을 나타낸다(예: 1, 2, A, B 등).
parent: ThreadedBinaryTree?는 이 노드의 부모 노드를 가리킨다.
left: ThreadedBinaryTree?는 이 노드의 왼쪽 자식 노드를 가리킨다.
right: ThreadedBinaryTree?는 이 노드의 오른쪽 자식 노드를 가리킨다.
leftThread: ThreadedBinaryTree?는 이 노드의 중위 순회 선행자를 가리킨다.
rightThread: ThreadedBinaryTree?는 이 노드의 중위 순회 후행자를 가리킨다.

leftThread와 rightThread를 모두 저장하기 때문에, 이는 이중 스레드 트리다. 이제 ThreadedBinaryTree 클래스의 몇 가지 멤버 함수를 살펴볼 준비가 되었다.

순회 알고리즘

스레드 이진 트리를 사용하는 주된 이유부터 살펴보자. 이제 트리 내 어떤 노드의 중위 순회 선행자(predecessor)와 후행자(successor)를 쉽게 찾을 수 있다. 노드가 left/right 자식을 갖지 않으면, 단순히 노드의 leftThread/rightThread를 반환한다. 그렇지 않으면 트리를 따라 내려가 올바른 노드를 찾는 것은 간단하다.

  func predecessor() -> ThreadedBinaryTree<T>? {
    if let left = left {
      return left.maximum()
    } else {
      return leftThread
    }
  }

  func successor() -> ThreadedBinaryTree<T>? {
    if let right = right {
      return right.minimum()
    } else {
      return rightThread
    }
  }

참고: maximum()과 minimum()은 ThreadedBinaryTree의 메서드로, 주어진 서브트리에서 가장 큰/작은 노드를 반환한다. 자세한 내용은 구현 코드를 참고한다.

이 메서드들은 ThreadedBinaryTree의 메서드이므로, node.predecessor() 또는 node.successor()를 호출해 어떤 node의 선행자나 후행자를 얻을 수 있다. 단, node는 ThreadedBinaryTree 객체여야 한다.

선행자와 후행자를 추적하기 때문에, 스레드 이진 트리의 중위 순회는 위에서 설명한 재귀 알고리즘보다 훨씬 효율적이다. 이 새로운 알고리즘에서 선행자/후행자 속성을 활용해 순방향과 역방향 순회를 모두 효과적으로 수행한다.

    public func traverseInOrderForward(_ visit: (T) -> Void) {
        var n: ThreadedBinaryTree
        n = minimum()
        while true {
            visit(n.value)
            if let successor = n.successor() {
                n = successor
            } else {
                break
            }
        }
    }

    public func traverseInOrderBackward(_ visit: (T) -> Void) {
        var n: ThreadedBinaryTree
        n = maximum()
        while true {
            visit(n.value)
            if let predecessor = n.predecessor() {
                n = predecessor
            } else {
                break
            }
        }
    }

이 메서드 역시 ThreadedBinaryTree의 메서드이므로, node.traverseInorderForward(visitFunction)과 같이 호출한다. 각 노드를 방문할 때 실행할 함수를 지정할 수 있다. 이 함수는 노드 값의 타입인 T를 인자로 받고 반환 값이 없기만 하면 어떤 함수든 사용 가능하다.

트리의 순방향 순회를 직접 따라가며 컴퓨터가 어떻게 동작하는지 이해해보자. 예를 들어, 다음과 같은 간단한 스레드 트리가 있다고 가정한다.

트리의 루트인 9에서 시작한다. 아직 visit(9)를 호출하지 않는다. 여기서 트리의 minimum() 노드로 이동한다. 이 경우 2가 된다. 그런 다음 visit(2)를 호출하고, 이 노드가 rightThread를 가지고 있음을 확인한다. 따라서 즉시 successor()가 무엇인지 알 수 있다. 스레드를 따라 5로 이동한다. 이 노드는 나가는 스레드가 없다. 따라서 visit(5)를 호출한 후, right 서브트리의 minimum() 노드인 7로 이동한다. 그런 다음 visit(7)을 호출하고, 이 노드가 rightThread를 가지고 있음을 확인한다. 이 스레드를 따라 다시 9로 돌아온다. 이제 visit(9)를 호출하고, 이 노드가 rightThread를 가지고 있지 않음을 확인한다. 따라서 right 서브트리의 minimum() 노드인 12로 이동한다. 이 노드는 nil로 연결된 rightThread를 가지고 있으므로 순회가 완료되었음을 알린다! 노드를 2, 5, 7, 9, 12 순서로 방문했는데, 이는 직관적으로 자연스러운 증가 순서이다.

역방향 순회도 매우 유사하지만, right, rightThread, minimum(), successor()를 각각 left, leftThread, maximum(), predecessor()로 바꾸면 된다.

노드 삽입과 삭제

스레드 이진 트리가 제공하는 빠른 순회 기능은 작은 대가를 요구한다. 노드를 삽입하거나 삭제할 때 leftThread와 rightThread 변수를 지속적으로 관리해야 하기 때문에 복잡해진다. 지루한 코드를 보는 대신 예제를 통해 설명하는 것이 가장 좋다 (더 자세한 내용을 알고 싶다면 구현 코드를 참고하길 바란다). 이 내용을 이해하려면 이진 탐색 트리에 대한 지식이 필요하므로, 먼저 이진 탐색 트리를 읽어보길 권한다.

참고: 이 스레드 이진 트리 구현에서는 중복된 노드를 허용한다. 중복된 경우 기본적으로 오른쪽에 삽입한다.

순회 예제에서 사용했던 동일한 트리로 시작해보자:

이 트리에 10을 삽입한다고 가정하자. 변경된 부분을 빨간색으로 표시한 결과는 다음과 같다:

이진 탐색 트리에 익숙하다면 이 노드의 위치가 놀라울 리 없다. 새로운 점은 노드 간 스레드를 유지하는 방법이다. 10을 12의 left 자식으로 삽입하려고 한다. 먼저 12의 left 자식을 10으로 설정하고, 10의 parent를 12로 설정한다. 10이 left에 삽입되고 자식이 없으므로, 10의 rightThread를 부모인 12로 안전하게 설정할 수 있다. 10의 leftThread는 어떻게 처리할까? 10 < 12이고, 10이 12의 유일한 left 자식이므로, 10의 leftThread를 12의 (이제는 더 이상 사용되지 않는) leftThread로 설정할 수 있다. 마지막으로 12의 leftThread를 nil로 설정한다. 이제 12는 left 자식을 가지기 때문이다.

이제 4를 트리에 삽입해보자:

4를 right 자식으로 삽입하지만, 위와 동일한 과정을 거친다. 다만 left와 right가 바뀌었다. 완성을 위해 마지막으로 15를 삽입한다:

이제 트리가 꽉 차 있으니, 몇 개의 노드를 삭제해보자. 삽입에 비해 삭제는 조금 더 복잡하다. 먼저 7처럼 자식이 없는 간단한 노드를 삭제해보자:

7을 그냥 제거하기 전에 몇 가지 정리 작업을 해야 한다. 7이 right 자식이고 자식이 없으므로, 7의 부모(5)의 rightThread를 7의 (이제는 더 이상 사용되지 않는) rightThread로 설정할 수 있다. 그런 다음 7의 parent, left, right, leftThread, rightThread를 모두 nil로 설정해 트리에서 완전히 제거한다. 또한 부모의 rightChild를 nil로 설정해 이 right 자식의 삭제를 완료한다.

이제 조금 더 복잡한 경우를 시도해보자. 트리에서 5를 삭제한다고 가정하자:

이 경우는 5가 처리해야 할 자식을 가지고 있으므로 조금 더 까다롭다. 핵심 아이디어는 5를 첫 번째 자식인 2로 대체하는 것이다. 이를 위해 2의 parent를 9로 설정하고, 9의 left 자식을 2로 설정한다. 4의 rightThread가 원래 5였지만, 5를 제거하므로 이를 변경해야 한다. 이제 스레드 이진 트리의 두 가지 중요한 속성을 이해하는 것이 중요하다:

어떤 노드 n의 left 서브트리에서 가장 오른쪽 노드 m의 rightThread는 n이다.
어떤 노드 n의 right 서브트리에서 가장 왼쪽 노드 m의 leftThread는 n이다.

5를 제거하기 전에 이 속성이 어떻게 유지되었는지 주목하라. 4가 5의 left 서브트리에서 가장 오른쪽 노드였다. 이 속성을 유지하기 위해 4의 rightThread를 9로 설정해야 한다. 이제 4는 9의 left 서브트리에서 가장 오른쪽 노드가 되기 때문이다. 5를 완전히 제거하려면 5의 parent, left, right, leftThread, rightThread를 모두 nil로 설정하면 된다.

이제 조금 더 복잡한 경우를 시도해보자. 루트 노드인 9를 제거하면 어떻게 될까? 결과 트리는 다음과 같다:

두 개의 자식을 가진 노드를 제거할 때는 위의 예제와 약간 다른 접근 방식을 취한다. 기본 아이디어는 제거하려는 노드를 right 서브트리에서 가장 왼쪽 노드로 대체하는 것이다. 이 노드를 대체 노드라고 부른다.

참고: left 서브트리에서 가장 오른쪽 노드로 대체할 수도 있다. left 또는 right를 선택하는 것은 대부분 임의의 결정이다.

대체 노드(10)를 찾으면 위에서 설명한 알고리즘을 사용해 트리에서 제거한다. 이렇게 하면 right 서브트리의 엣지가 올바르게 유지된다. 그런 다음 9를 10으로 대체하는 것은 쉽다. 10에서 나가는 엣지만 업데이트하면 된다. 이제 위에서 설명한 두 속성을 유지하기 위해 스레드를 조정하기만 하면 된다. 이 경우, 12의 leftThread는 이제 10이 된다. 9는 더 이상 필요하지 않으므로, 모든 변수를 nil로 설정해 제거 과정을 완료한다.

right 자식만 있는 노드를 제거하는 방법을 설명하기 위해 마지막으로 12를 제거해보자:

12를 제거하는 과정은 5를 제거하는 과정과 동일하지만, left와 right가 바뀌었다. 5는 left 자식을 가지고 있었고, 12는 right 자식을 가지고 있지만, 핵심 알고리즘은 동일하다.

이것으로 끝이다! 이 예제는 스레드 이진 트리에서 노드를 삽입하고 삭제하는 방법을 빠르게 살펴본 것이다. 이 예제를 이해했다면, 원하는 트리에서 어떤 노드든 삽입하거나 삭제할 수 있을 것이다. 더 자세한 내용은 구현 코드에서 확인할 수 있다.

기타 메서드

스레드 이진 트리는 다양한 작은 연산을 수행할 수 있다. 트리 내 특정 노드를 searching()으로 찾거나, 노드의 depth()와 height()를 계산하는 등의 기능이 포함된다. 전체적인 기술적 세부사항은 구현 코드를 참고하면 된다. 이 메서드 중 상당수는 이진 탐색 트리에서도 기본적으로 제공하는 기능이므로, 추가 문서에서 더 자세한 내용을 확인할 수 있다.

더 알아보기

위키백과의 스레드 이진 트리(Threaded Binary Tree)

Swift 알고리즘 클럽을 위해 Jayson Tung이 작성
Swift 3으로 마이그레이션: Jaap Wijnen

이미지 제작: www.draw.io