프로그래밍 면접 문제 26: Trim Binary Search Tree

이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.

이전글 – 프로그래밍 면접 문제 25: Remove Duplicate Characters in String

이진 탐색 트리의 루트(root)와 최소, 최대 2개의 숫자가 주어지면, 모든 값이주어진 최소 값과 최대 값 사이의(최소, 최대 값을 포함) 값으로 새로운 트리를 만드는 문제입니다. 결과로 생성된 트리 역시 유효한 이진 탐색 트리여야 합니다. 따라서 다음과 같은 트리가 입력받았고,

최소 값이 5, 최대 값이 13인 경우, 다음과 같은 이진 탐색 트리를 결과로 얻을 수 있습니다:

최소와 최대 값의 범위를 벗어나는 노드는 모두 제거해야 합니다. 이를 트리의 후위 순회(post-order traversal)를 통해서 처리할 수 있습니다. 먼저 왼쬑 자식 노드를 처리하고, 그런 다음 오른쪽 자식 노드, 마지막으로 해당 노드를 처리합니다. 따라서 바닥에서 위로, 잎에서 시작해서 루트(root)로 가면서 새 트리를 형성합니다. 결과적으로 노드 자신을 처리하는 동안 왼쪽과 오른쪽 하위 트리가 유효하게 정리된 이진 탐색 트리가 됩니다 (NULL이 될수도 있습니다).

각 노드에서 노드의 값을 기반으로 참조(reference)를 반환하며, 이 값은 현재 노드가 부모의 왼쪽 자식 노드인지 오른쪽 자식 노드인지에 따라 부모의 왼쪽 또는 오른쪽 자식 노드 포인터에 할당됩니다. 현재 노드의 값이 최소와 최대 값 사이의 값인 경우(최소 <= 노드 <= 최대) 어떤 조치를 취할 필요가 없으므로, 현재 노드의 참조를 반환합니다. 현재 노드의 값이 최소 값보다 작은 경우 이 노드의 오른쪽 하위 트리의 참조를 반환하고, 왼쪽 하위 트리는 버립니다. 이진 탐색 트리를 이용하므로 특정 노드의 값이 최소 값보다 작으면 왼쪽 자식 노드의 값 역시 최소 값보다 작습니다. 하지만 오른쪽 자식 노드의 값은 최소 값보다 작을지, 작지 않을지 확신할 수 없기 때문에 오른쪽 자식 노드의 값을 반환합니다. 아래에서 위로 후위 순회(post order traversal)를 수행하고 있기 때문에 오른쪽 하위트리는 이미 유효한 이진 탐색 트리이며(NULL일 수도 있음) 왼쪽 하위 트리는 확실히 최소 값보다 작고 후위 순회 과정에서 제거되었기 때문에 분명히 NULL 입니다. 후위 순회에서는 자식 노드를 모두 처리한 다음 마지막으로 현재 노드를 처리한다는 것을 명심합니다.

노드의 값이 최대 값보다 큰 경우에도 비슷한 상황이 연출되며, 이때는 왼쪽 하위트리의 참조를 반환합니다. 특정 노드의 값이 최대 값보다 큰 경우에는 오른쪽 하위트리의 값은 분명히 최대 값보다 클 것입니다. 하지만 왼쪽 자식 노드의 값은 최대 값보다 클수도, 크지 않을 수도 있습니다. 따라서 오른쪽 하위트리는 삭제하고 이미 유효한 왼쪽 하위트리에 대한 참조를 반환합니다. 크드를 살펴보면 이해가 훨씬 쉬울 것입니다:

def trimBST(tree, minVal, maxVal):
    if not tree:
        return
    tree.left = trimBST(tree.left, minVal, maxVal)
    tree.right = trimBST(tree.right, minVal, maxVal)
    if minVal <= tree.val <= maxVal:
        return tree
    if tree.val < minVal: return tree.right if tree.val > maxVal:
        return tree.left

이 알고리즘의 복잡도는 O(N)이며, 여기에서 N은 트리의 노드의 수 입니다. 기본적으로 트리의 후위 순회를 수행하기 때문에 각 노드를 모두 한번씩 확인합니다. 모든 노드를 적어도 한번씩은 확인해야 하기 때문에 이 방법은 최적의 방법입니다. 이 문제는 트리에서 재귀의 효과를 보여주는 매우 훌륭한 문제라고 할 수 있습니다.

다음글 – 프로그래밍 면접 문제 27: Squareroot of a Number