트리 순회 변환 및 트리 재구성

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

트리의 순회 정보를 받아서 다른 순회 정보를 출력하는 문제가 종종 있다. 2가지의 순회 정보가 있으면 다른 순회 정보를 알 수 있는데 그와 관련해서 다뤄보고자 한다.

전위, 중위 순회 정보에서 후위 순회 구현 / 변환

전위는 항상 루트 노드가 앞에 위치하고 그 값을 중위 순회에서 찾으면 양 쪽이 해당 노드의 서브트리 노드들임을 알 수 있다.

이후 left로 탐색을 진행하면 root는 2가 된다.

in order의 root 우측 값이 없으므로 right subtree가 존재하지 않음을 알 수 있다.

right로 탐색하여 root가 3인 경우를 고려하면 아래 그림과 같다.

in order의 root 우측으로 각각 4, 5가 있어 양쪽 자식 노드가 모두 존재함을 알 수 있다.

전위, 중위로 후위 구현 python 코드

def pre_in_to_post(pre_list, in_list):
    if pre_list:
        root = pre_list[0]
        mid = in_list.index(root)
        pre_in_to_post(pre_list[1:mid + 1], in_list[:mid])
        pre_in_to_post(pre_list[mid + 1:], in_list[mid + 1:])
        print(root, end=" ") # 후위이므로 탐색 끝나고 출력
pre_order = [1, 2, 4, 7, 3, 5, 6]
in_order = [4, 7, 2, 1, 5, 3, 6]
pre_in_to_post(pre_order, in_order)

중위, 후위 순회 정보에서 전위 순회 출력 / 변환

전위와는 달리 후위는 루트노드가 항상 뒤에 존재함을 숙지해야 한다.

이후 left로 탐색하여 root가 2가 된 경우는 아래 그림과 같다.

만약 right를 탐색하여 root가 3이 된 경우는 아래 그림과 같다.

중위, 후위로 전위 출력 python 코드

def in_post_to_pre(in_list, post_list):
    if post_list:
        root = post_list[-1]
        mid = in_list.index(root)
        print(root, end=" ") # 전위이므로 탐색 전에 출력
        in_post_to_pre(in_list[:mid], post_list[:mid])
        in_post_to_pre(in_list[mid + 1:], post_list[mid:-1])
in_order = [4, 7, 2, 1, 5, 3, 6]
post_order = [7, 4, 2, 5, 6, 3, 1]
in_post_to_pre(in_order, post_order)

순회 변환 코드 공간 복잡도 개선

위의 코드들은 좌, 우측 서브트리를 넘겨줄 때 슬라이싱 작업을 수행함으로써 생성된 신규 리스트를 재귀함수에 전달한다. 그러나 이 방법은 입력값의 규모가 거대해지면 메모리 제한이 있는 문제의 경우 에러를 출력한다. 이를 해결하기 위해 슬라이싱하지 않고 좌, 우측 서브트리를 나타내는 양 끝점의 좌표값을 넘겨줌으로써 해결해야 한다. 관련 문제로는 BOJ #2263. 트리의 순회가 있다.

개선된 python 코드

pre_order = [1, 2, 4, 7, 3, 5, 6]
in_order = [4, 7, 2, 1, 5, 3, 6]
post_order = [7, 4, 2, 5, 6, 3, 1]
N = len(in_order)
pos = [0] * (N + 1)
for i in range(N):
    pos[in_order[i]] = i

def pre_in_to_post(pre_l, pre_r, in_l, in_r):
    if pre_l > pre_r or in_l > in_r:
        return
    root = pre_order[pre_l]
    mid = pos[root] # in order에서의 root 좌표값
    # mid = in_order.index(root)
    left = mid - in_l # 좌측 서브트리 노드 개수
    right = in_r - mid # 우측 서브트리 노드 개수
    pre_in_to_post(pre_l + 1, pre_l + left, in_l, in_l + left - 1)
    pre_in_to_post(pre_r - right + 1, pre_r, in_r - right + 1, in_r)
    print(root, end=" ")

def in_post_to_pre(in_l, in_r, post_l, post_r):
    if in_l > in_r or post_l > post_r:
        return
    root = post_order[post_r]
    mid = pos[root]
    # mid = in_order.index(root)
    left = mid - in_l
    right = in_r - mid
    print(root, end=" ")
    in_post_to_pre(in_l, in_l + left - 1, post_l, post_l + left - 1)
    in_post_to_pre(in_r - right + 1, in_r, post_r - right, post_r - 1)

pre_in_to_post(0, N - 1, 0, N - 1)
print()
in_post_to_pre(0, N - 1, 0, N - 1)

전위, 후위에서 중위 구현?

오류가 발생한다. 위 그림의 트리는 서로 다르지만 전위, 중위 탐색 결과는 서로 같기 때문이다. 따라서 구현 시 제약 조건이 주어지거나 두 갈래의 케이스 모두에 대해 정답 처리를 해야 하므로 코딩테스트보다는 면접에서나 나올법한 질문이다.

전위, 중위 or 중위, 후위 순회 정보로 트리 재구성

위에서 정리하였듯이 전위 순회로 전환하는 데 성공했으므로 각 출력되는 값을 리턴받아 노드로 바꿔주면 되겠다.

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_pre_in(cur, pre_l, pre_r, in_l, in_r):  # 전위, 중위로 트리 재구성
    if pre_l > pre_r or in_l > in_r:
        return
    root = pre_order[pre_l]
    cur = TreeNode(root)
    mid = pos[root]  # in order에서의 root 좌표값
    # mid = in_order.index(root)
    left = mid - in_l  # 좌측 서브트리 노드 개수
    right = in_r - mid  # 우측 서브트리 노드 개수
    cur.left = build_pre_in(cur.left, pre_l + 1, pre_l + left,
                            in_l, in_l + left - 1)
    cur.right = build_pre_in(cur.right, pre_r - right + 1, pre_r,
                             in_r - right + 1, in_r)
    return cur


def build_in_post(cur, in_l, in_r, post_l, post_r):
    if in_l > in_r or post_l > post_r:
        return
    root = post_order[post_r]
    cur = TreeNode(root)
    mid = pos[root]
    # mid = in_order.index(root)
    left = mid - in_l
    right = in_r - mid
    cur.left = build_in_post(cur.left, in_l, in_l + left - 1,
                             post_l, post_l + left - 1)
    cur.right = build_in_post(cur.right, in_r - right + 1, in_r,
                              post_r - right, post_r - 1)
    return cur


def get_post(t, result):
    if t:
        get_post(t.left, result)
        get_post(t.right, result)
        result.append(t.val)
    return result


def get_pre(t, result):
    if t:
        result.append(t.val)
        get_pre(t.left, result)
        get_pre(t.right, result)
    return result


pre_order = [1, 2, 4, 7, 3, 5, 6]
in_order = [4, 7, 2, 1, 5, 3, 6]
post_order = [7, 4, 2, 5, 6, 3, 1]
N = len(in_order)
pos = [0] * (N + 1)
for i in range(N):
    pos[in_order[i]] = i
t1, t2 = None, None
t1 = build_pre_in(t1, 0, N - 1, 0, N - 1)
t2 = build_in_post(t2, 0, N - 1, 0, N - 1)
print(f'post_order: {get_post(t1, [])}')
print(f'pre_order: {get_pre(t2, [])}')

BST 전위 순회 정보로 후위 순회 출력

BST는 대소 관계가 분명하기 때문에 각 자식 서브트리의 루트 노드를 탐색으로 알아낼 수 있다. 따라서 전위든 후위든 하나만 주어져도 반대의 경우를 출력할 수 있다.

위의 그림에서 root 노드는 전위 순회이므로 항상 앞에 오는데 문제는 중위 탐색이 주어지지 않아 우측 서브트리의 루트 노드를 알 수 없다는 점이다. 다만 전위 탐색의 특성을 참고하여 처음 만나는 root보다 큰 값을 가진 좌표가 우측 서브 트리의 루트 노드임을 알 수 있다. 그렇다면 더 큰 값을 발견하지 못하는 경우도 있을 것이다. 아래 그림을 참고하자.

98이 루트 노드일 때 이후의 값들에 대해 탐색을 진행하여도 루트 노드보다 큰 값은 존재하지 않는다. 따라서, 우측 노드에 대해서는 탐색할 필요가 없으므로 종결 조건에 걸리게끔 범위를 조정하면 된다.

BST 전위 순회를 후위로 출력 python 코드

def bst_pre_to_post(l, r):
    if l > r:
        return
    root = pre_order[l]
    idx = None
    for i, v in enumerate(pre_order[l + 1:], l + 1):
        if v > root:
            idx = i
            break
    if idx is None:
        idx = r + 1
    bst_pre_to_post(l + 1, idx - 1)
    bst_pre_to_post(idx, r)
    print(root, end=" ")

pre_order = [50, 30, 24, 5, 28, 45, 98, 52, 60]
bst_pre_to_post(0, len(pre_order) - 1)

BST 후위 순회 정보로 전위 순회 출력

전위 순회와는 달리 루트 노드가 항상 순회 정보의 뒤에 있으며 우측 자식 트리의 루트 노드는 루트의 다음에 있지만 좌측 자식 트리의 루트 노드 좌표값을 알아내야 한다.

위 그림을 보면 전위 순회 결과에서 우측 서브트리의 루트 노드를 찾듯이 처음 마주치는 루트 값보다 작은 값을 갖는 좌표가 좌측 서브트리의 루트 노드임을 알 수 있다, 이를 바탕으로 코드를 작성하자.

BST 후위 순회를 전위로 출력 python 코드

def bst_post_to_pre(l, r):
    if l > r:
        return
    root = post_order[r]
    idx = None
    for i in range(r - 1, -1, -1):
        if post_order[i] < root:
            idx = i
            break
    if idx is None:
        idx = l - 1
    print(root, end=" ")
    bst_post_to_pre(l, idx)
    bst_post_to_pre(idx + 1, r - 1)

post_list = [5, 28, 24, 45, 30, 60, 52, 98, 50]
solve(0, len(post_list) - 1)

BST 구현한 뒤 전위 or 후위 순회 삽입?

BST를 생성하고 삽입 기능을 수행하는 함수를 구현한 뒤 탐색을 진행해도 "정답"은 달라지지 않는다. 그러나 문제는 시간 제한이 걸린 경우, 자가 균형 트리가 아니므로 최악의 경우 삽입 과정에서 $O(N)$이 발생할 수 있고 N개의 노드에 대해 적용하면 $O(N^2)$까지는 아니더라도 그에 근접할 수 있다. 흔히 BST의 탐색의 시간 복잡도가 $O(log\ n)$이라 알고 있는 경우 발생하기 쉬운 실수이다. 전위 순회를 차례대로 삽입해서 후위 탐색을 하거나 후위 순회를 역순으로 삽입해서 전위 탐색을 하면 된다. 관련 문제는 BOJ #5639. 이진 탐색 트리가 있다.