🌳 이진 검색 트리

17 Jul 2022 in Algorithm on Binary search tree, Recursion

백준 Class4 Gold5

solved_ac[Class4] 이진 검색 트리

문제

---

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

---

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력

---

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

50
30
24
5
28
45
98
52
60

예제 출력 1

5
28
24
45
30
60
52
98
50

📖 자료구조

⭐️ [BST는 데이터 탐색 속도를 높이고 싶을 때 사용한다.] ⭐️

Binary Search Tree

이진 트리는 기본적으로 비선형 구조에 속한다.

예를 들어 위와 같은 트리에서 “24”를 찾고 싶다고 가정하자.

그렇다면 루트 노드인 “50”을 확인해보았을 때, “24 < 50”이므로 오른쪽 서브 트리는 더 이상 확인 안해도 되므로 가지치기를 할 수 있다.

그렇게 되면 연산량이 절반으로 줄어들고 따라서 BST의 시간복잡도는 O(logN)이다.

선형 구조인 리스트의 탐색 속도가 O(N)이므로 데이터 탐색 속도가 훨씬 빠르다고 할 수 있다.

그러나 최악의 경우(왼쪽 서브 트리만 존재하는 경우 OR 오른쪽 서브 트리만 존재하는 경우) 시간복잡도가 동일하게 O(N)으로 수행될 수 있다.

후위 순회

이 문제에서는 Binary Tree가 주어졌을 때 후위 순회 함수 구현을 요구한다.

일종의 공식처럼 외워도 되겠지만 장기 기억을 하기 위하여 하나씩 차근차근 이해해보자.

• 시작 노드와 끝 노드를 정한다.
• 시작 노드가 끝 노드를 앞질러가면 종료한다.
• 후위 순회의 포인트는 <왼쪽 👉🏻 오른쪽 👉🏻 루트 노드> 이다.
• 따라서 루트 노드를 기준으로 왼쪽과 오른쪽의 Sub Tree를 구분한다.

<왼쪽 👉🏻 오른쪽 👉🏻 루트 노드> “재귀를 이용하여 구현”

• 구분한 구분점을 가지고 왼쪽 Sub Tree를 탐색
• 오른쪽 Sub Tree 탐색
• 루트 노드 출력

👨🏻‍💻 CODE

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

### 문제 조건 ###
binary_tree = []
while True:
    try:
        binary_tree.append(int(input()))
    except:
        break
### ###

# BST 후위 순회
def post_order(start,end):
    if start > end:
        return
    root = end+1 # 오른쪽 Sub Tree가 없을 경우를 대비

    for i in range(start+1,end+1):
        # 오른쪽 Sub Tree 발견
        if binary_tree[i] > binary_tree[start]:
            root = i
            break
    
    post_order(start+1,root-1) # 왼쪽 Sub Tree Traverse
    post_order(root,end) # 오른쪽 Sub Tree Traverse

    print(binary_tree[start])

post_order(0,len(binary_tree)-1)

재귀 제한 걸어주는 것 유의