[Python] 백준 / gold / 5639 : 이진 검색 트리

문제 링크 : https://www.acmicpc.net/problem/5639

이진 검색 트리 + 재귀 문제. 얻어가는게 많았던 좋은 문젠거 같다. 이런 흐름으로 문제를 풀었다.

1. 이진 검색 트리를 만들고, 거기서 후위 순회를 돌려야겠다는 생각을 했다.
   • 그런데 이 문제에서 N = O(10^6) 이고, 불균형 이진 검색 트리일 경우는 트리 생성만해도 시간 초과가 나게 된다 -> 그렇게하면 안되겠다고 생각.

2. 트리 생성 과정을 거치지 말고 (전위 순회) -> (후위 순회)로 단번에 변환해주는 함수를 만들어야겠다고 생각했다.

3. 재귀의 개념을 이용해서 솔루션 함수를 작성했다.
   • 이진 검색 트리에서, 모든 서브 트리가 이진 검색 트리를 만족한다. (재귀적)
   • 전위 순회한 결과는 크게 [root / left / right] 서브 트리로 분할 할 수 있다.
   • 후위 순회한 결과는 크게 [left / right / root] 서브 트리로 분할 할 수 있다.
   • [ 50 / 30 24 5 28 45 / 98 52 60 ] 에서, 서브 트리인 [ 30 24 5 28 45 ] 또한 이진 검색 트리를 만족한다.
     -> [ 30 / 24 5 28 / 45 ] -> [ 24 / 5 / 28 ]
   • 이 생각들을 종합해서 [root / left / right] 의 순서를 [left / right / root] 의 순서로 변환하도록 함수를 작성했다.

기억할 것

1. 이진 검색 트리에선, 루트 노드만 알게 된다면 트리 전체 모양을 결정할 수 있다.

2. 이진 검색 트리가 균형한지 불균형한지에 따라 연산의 시간복잡도는 달라질 수 있다.

3. 이진 검색 트리에서 중위 순회 (in-order traversal) 을 하면 정렬된 값을 구할 수 있다.

4. 트리에서는 전체트리와 서브트리의 관계를 잘 고려하는게 좋다.

파이썬 코드

import sys
sys.setrecursionlimit(10**6)
arr = []
answer = []

while True:
    try:
        x = int(sys.stdin.readline())
        arr.append(x)
    except:
        break


def preorder_to_postorder(tree):
    if len(tree) == 0:
        return
    if len(tree) == 1:
        answer.append(tree[0])
        return

    root = tree[0]
    pivot = len(tree)
    for i in range(1, len(tree)):
        if root < tree[i]:
            pivot = i
            break

    preorder_to_postorder(tree[1:pivot])
    preorder_to_postorder(tree[pivot:])
    answer.append(root)


preorder_to_postorder(arr)
for x in answer:
    print(x)

이진 검색 트리 - insert 함수 구현 연습

• 이진 검색 트리를 생성하는 연습도 해봤다.
• insert 의 시간복잡도
  • 균형 트리일 경우 - O(log N)
  • 불균형 트리일 경우 - O(N)

import sys
arr = []

while True:
    try:
        x = int(sys.stdin.readline())
        arr.append(x)
    except:
        break

# [left, right]
tree = dict()
root = arr[0]


def insert(node, a):
    # node 의 자식이 없다면
    if node not in tree:
        if node > a:
            tree[node] = [a, 0]
        else:
            tree[node] = [0, a]
        return
    # node 의 자식이 있다면
    else:
        if node > a:
            if tree[node][0] == 0:
                tree[node][0] = a
            else:
                insert(tree[node][0], a)
        else:
            if tree[node][1] == 0:
                tree[node][1] = a
            else:
                insert(tree[node][1], a)
        return


for x in arr[1:]:
    insert(root, x)

print(tree)

'''
입력
50
30
24
5
28
45
98
52
60

출력 결과
{50: [30, 98], 30: [24, 45], 24: [5, 28], 98: [52, 0], 52: [0, 60]}
'''