[백준]-이진 검색 트리

이정연·2022년 10월 14일

백준 이진 검색 트리 재귀

CodingTest

목록 보기

33/165

🌳 이진 검색 트리

solved_ac[Class4][이진 검색 트리](https://www.acmicpc.net/problem/5639)

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

예제 출력 1

📖 자료구조

⭐️ [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)