트리, 순회, BST를 한 번도 배우지 않은 학습자를 대상으로 합니다. 먼저 그림의 부품 이름을 익히고, 작은 예제로 비교 방향을 연습한 뒤, 실제 시험 숫자를 한 단계씩 따라가며 마지막에는 입력 sequence와 BST invariant로 답을 검산합니다.
용어부터 읽기
node·edge·root·child·leaf·subtree·nil을 먼저 확인합니다. 모르는 말을 건너뛰면 이후의 left/right 경로가 단순 암기로 보입니다.
작은 예제 손으로 재생
각 소문항의 실제 숫자를 보기 전에 세 개 정도의 key로 된 micro example을 종이에 그려 비교와 순회의 뜻을 확인합니다.
시험 문제를 한 줄씩 풀기
각 비교에서 왜 반대쪽 subtree를 버릴 수 있는지 말한 뒤 다음 node로 이동합니다. 정답 그림보다 판단 근거가 먼저입니다.
두 방식으로 검산
완성 tree를 traversal로 다시 읽거나 inorder가 정렬되는지 확인하고, search는 equality 또는 nil에서 정확히 멈췄는지 확인합니다.
먼저 익힐 기호와 용어
노드(node / Knoten)
키(key) 하나와 왼쪽·오른쪽 자식 연결을 담는 트리의 한 칸입니다.
이 페이지의 예: 37이 전체 트리의 루트 노드입니다.
간선(edge / Kante)
부모와 자식 사이를 잇는 선이며 왼쪽 간선과 오른쪽 간선은 서로 다른 의미를 가집니다.
이 페이지의 예: 37에서 15로 가는 선은 왼쪽 간선입니다.
빈 포인터(nil)
그 방향에 자식 노드가 없다는 뜻입니다. 값 0이나 실제 키가 아닙니다.
이 페이지의 예:\(56.\text{left}=\text{nil}\)56.left=nil이므로 search(50)는 그 자리에서 실패합니다.
왼쪽/오른쪽(L / R)
현재 키와 목표를 비교한 뒤 각각 왼쪽 또는 오른쪽 자식으로 이동한다는 경로 표기입니다.
이 페이지의 예: 23의 경로는 \(37(L)\to 15(R)\to 29(L)\)37(L)→15(R)→29(L)입니다.
이진 탐색 트리(BST)
모든 노드에서 왼쪽 부분 트리의 키는 더 작고 오른쪽 부분 트리의 키는 더 큰 트리입니다.
이 페이지의 예: 15의 왼쪽에는 7, 오른쪽에는 29가 놓입니다.
전위/중위 순회(Pre / In)
전위 순회(Preorder)는 root-left-right, 중위 순회(Inorder)는 left-root-right 순서로 같은 트리를 읽는 규칙입니다.
이 페이지의 예: 루트 37은 전위 순회의 첫 값이고 중위 순회의 가운데 분할점입니다.
정확성 범위
시험 문언과 숫자·배점은 비공식 복기 자료 lines 246-268에서 가져왔습니다. 정의와 알고리즘은 현재 강의 Lecture 03 pp.46-51, 66-71, 80-81 및 Sheet05-GrpSol pp.7-12로 교차 확인했습니다. 이 문제의 key는 모두 서로 다르며, duplicate가 있는 일반 BST에서는 강의나 구현이 정한 equality 방향을 먼저 밝혀야 합니다.
배점: 1점
5(a) · 전위 순회(Preorder)와 중위 순회(Inorder)로 BST를 유일하게 복원하기
Preorder [37,15,7,29,56,85]와 Inorder [7,15,29,37,56,85]에 대응하는 BST를 그리시오.
독립 학습 안내: 앞 소문항을 읽지 않았어도 이 절의 입력 그림과 개념 설명부터 따라갈 수 있습니다.
이 소문항의 입력
아직 트리 그림은 주어지지 않습니다. 아래 두 순회 결과만으로 원래 트리를 복원해야 합니다.
해설을 읽기 전에 루트 또는 첫 비교 한 줄을 종이에 적으세요. 정답보다 판단 이유를 말하는 것이 목표입니다.
먼저 문제의 정체부터
Preorder는 root를 가장 먼저 알려 주고, Inorder는 root를 기준으로 왼쪽 subtree와 오른쪽 subtree의 원소 집합을 나눠 줍니다. 두 정보를 번갈아 사용하면 트리를 재귀적으로 복원할 수 있습니다.
이 문제의 key는 모두 서로 다릅니다. 따라서 Inorder에서 root 위치가 하나로 정해지고, 왼쪽·오른쪽 구간도 모호하지 않아 결과 트리가 유일합니다.
BST의 Inorder는 원래 오름차순이므로 주어진 Inorder가 BST 조건과 일치하는지도 먼저 확인할 수 있습니다.
이 소문항만 읽어도 되는 연결 강의
왜 이 개념이 필요한가
서로 다른 두 sequence가 어떻게 하나의 tree 그림을 결정하는지 이해하면 traversal을 단순 암기하지 않고, root와 subtree라는 재귀 구조를 실제로 읽을 수 있습니다. 이후 BST 복원·직렬화 문제의 기본 도구가 됩니다.
이 절을 읽고 나면 다음을 할 수 있어야 합니다.
Preorder와 Inorder에서 root가 나타나는 위치가 서로 다른 이유를 말할 수 있습니다.
각 재귀 단계에서 왼쪽·오른쪽 subtree의 원소와 Preorder 구간을 정확히 분리할 수 있습니다.
일반 binary tree의 Preorder+Inorder 복원과 unique-key BST의 Preorder 단독 복원을 구분할 수 있습니다.
풀이 전에 꼭 알아야 할 말
트리(tree)의 부품
노드(node)는 키(key)를 담는 칸, 간선(edge)은 두 노드를 잇는 선, 루트(root)는 부모가 없는 시작 노드, 자식이 없는 노드는 잎(leaf)입니다. 어떤 노드 아래의 전체 묶음이 부분 트리(subtree)이고 빈 자식 자리는 nil입니다.
아주 작은 예: 루트 10의 왼쪽 자식이 5라면 5와 그 아래 모든 노드가 10의 왼쪽 부분 트리입니다.
이진 트리(binary tree)와 이진 탐색 트리(BST)
이진 트리는 노드마다 왼쪽·오른쪽 자식을 최대 하나씩 갖습니다. 이진 탐색 트리는 여기에 모든 왼쪽 부분 트리 키가 작고 모든 오른쪽 부분 트리 키가 크다는 전역 약속을 더합니다.
아주 작은 예: 10의 오른쪽 부분 트리 어디에도 10보다 작은 7이 올 수 없습니다.
순회(Traversal)
트리를 바꾸는 연산이 아니라 같은 트리의 노드를 어느 순서로 읽을지 정한 규칙입니다. 전위 순회는 root-left-right, 중위 순회는 left-root-right입니다.
아주 작은 예: 루트 10, 자식 5와 20이면 \(\text{Pre}=[10,5,20], \text{In}=[5,10,20]\)Pre=[10,5,20], In=[5,10,20]입니다.
서로 다른 키(key) 전제
같은 숫자가 중복되지 않으므로 중위 순회에서 루트의 위치가 하나뿐입니다. 중복 키가 있으면 같은 값을 어느 쪽에 둘지 규칙이 추가로 필요합니다.
아주 작은 예: 이 문제에서 37은 중위 순회에 정확히 한 번만 나옵니다.
비유로 잡기 · 책 목차를 두 방식으로 읽기
전위 순회(Preorder)는 장 제목을 먼저 읽고 그 아래 절을 읽는 목차이며, 중위 순회(Inorder)는 왼쪽 절을 읽은 뒤 장 제목을 만나고 오른쪽 절을 읽는 목록이라고 생각합니다. 같은 장 제목을 두 목록에서 맞추면 양쪽 절 묶음이 드러납니다.
비유와 실제 개념의 연결: 가장 먼저 적힌 장 제목는 실제로 전위 순회의 첫 키인 부분 트리 루트에 대응합니다. 장 제목 앞뒤에 놓인 두 절 묶음는 실제로 중위 순회에서 루트 왼쪽·오른쪽 구간에 대응합니다. 각 절 안에서 같은 목차 규칙을 반복는 실제로 재귀적으로 작은 subtree 복원에 대응합니다.
비유의 한계: 실제 목차는 제목이 중복될 수 있지만 이 문제의 key는 모두 다릅니다. 비유는 방문 순서와 분할만 설명하며 BST의 수치 대소 관계 자체를 대신하지 않습니다.
두 순회열(sequence)을 같은 루트에서 자르는 세 단계
전위 순회: [37 | 15,7,29 | 56,85]
37이 전체 루트이고 뒤의 세 값과 두 값이 왼쪽·오른쪽 부분 트리의 전위 순회입니다.
중위 순회: [7,15,29 | 37 | 56,85]
37의 위치가 왼쪽 원소 세 개와 오른쪽 원소 두 개를 정확히 분리합니다.
작은 문제 반복
왼쪽은 root 15, 오른쪽은 root 56으로 같은 분할 규칙을 다시 적용합니다.
각 프레임은 Preorder 첫 값을 root로 표시하고 Inorder의 같은 값 양옆을 subtree로 나눕니다. 원소 수가 정해지면 Preorder의 다음 구간 길이도 자동으로 정해집니다.
작은 예제로 먼저 연습 · 세 노드(node) [10,5,20] 복원
Preorder [10,5,20], Inorder [5,10,20]인 서로 다른 key 세 개를 먼저 복원해 봅니다.
root 10 선택
Preorder는 root를 가장 먼저 출력하므로 첫 값 10이 전체 root입니다.
이 단계의 상태:\(\text{루트}=10\)root=10
Inorder를 10에서 분할
10 왼쪽의 5는 left subtree, 오른쪽의 20은 right subtree 원소입니다.
이 단계의 상태:\(L=[5], R=[20]\)L=[5], R=[20]
두 leaf 연결
각 구간에 원소가 하나뿐이므로 5와 20은 더 분할할 child가 없는 leaf입니다.
이 단계의 상태: 5 ← \(10 \to 20\)10 → 20
작은 예제의 결론: Preorder가 root를 알려 주고 Inorder가 양쪽 원소 집합을 알려 주면 각 작은 subtree에서도 같은 절차를 반복할 수 있습니다.
각 edge에서 왼쪽 child와 그 descendants는 ancestor보다 작고 오른쪽 descendants는 더 큰지 확인합니다.
30초 자가점검
일반 binary tree에서 Preorder 하나만 주어지면 항상 shape가 유일한가?
힌트: root 위치만 알고 left subtree의 크기를 아는지 생각합니다.
정답: 아닙니다. 일반 binary tree는 Preorder 하나만으로 left/right 구간 경계를 알 수 없어 여러 shape가 가능합니다.
unique-key BST에서는 왜 Preorder 하나만으로도 복원 가능한가?
힌트: root보다 작은 값과 큰 값은 갈 수 있는 방향이 정해집니다.
정답: BST 대소 관계가 Preorder 뒤 원소를 left와 right subtree로 나누므로 각 구간에서 재귀적으로 root를 정할 수 있습니다.
시험 답안 템플릿
37을 root로 둔다. Inorder에서 37 왼쪽 [7,15,29], 오른쪽 [56,85]로 나눈다. 왼쪽 subtree root는 15이고 children은 7,29이다. 오른쪽 subtree root는 56이고 right child는 85이다.
초보자가 자주 틀리는 지점
Inorder의 첫 값을 root로 선택한다.
Preorder 구간을 subtree 원소 수와 무관하게 반으로 자른다.
56의 왼쪽에 85를 둔다.
트리를 그린 뒤 두 traversal로 검산하지 않는다.
Preorder 하나만으로 일반 binary tree가 항상 유일하다고 생각한다.
배점: 2점
5(b) · 23과 60을 차례로 삽입하기
5(a)의 트리에 23과 60을 순서대로 삽입하고 각 삽입 뒤 트리를 그리시오.
독립 학습 안내: 앞 소문항을 읽지 않았어도 이 절의 입력 그림과 개념 설명부터 따라갈 수 있습니다.
이 소문항의 입력
이 소문항의 시작 상태 · 5(a)에서 복원한 원래 이진 탐색 트리
37
15
7
29
56
nil
85
먼저 90초 도전
해설을 읽기 전에 루트 또는 첫 비교 한 줄을 종이에 적으세요. 정답보다 판단 이유를 말하는 것이 목표입니다.
먼저 문제의 정체부터
BST 삽입은 root부터 한 번의 search path를 따라 nil 자리를 찾는 과정입니다. 새 key가 현재 node보다 작으면 왼쪽, 크면 오른쪽으로 갑니다.
두 값을 'nacheinander(차례로)' 넣으므로 60은 23이 들어간 결과에서 시작합니다. 다만 두 search path가 서로 다른 가지라 23이 60의 위치에는 영향을 주지 않습니다.
각 삽입 뒤 트리를 따로 그려야 2점의 단계 점수를 지킬 수 있습니다.
이 소문항만 읽어도 되는 연결 강의
왜 이 개념이 필요한가
BST insertion은 새 값을 아무 빈 곳에 붙이는 그림 문제가 아니라, search가 실패한 정확한 nil 자리를 찾는 알고리즘입니다. 비교 한 번마다 반대쪽 subtree 전체를 버리는 이유를 이해하면 위치를 외우지 않고 재현할 수 있습니다.
이 절을 읽고 나면 다음을 할 수 있어야 합니다.
현재 node와 새 key를 비교해 left 또는 right 한 방향만 선택할 수 있습니다.
두 key를 nacheinander, 즉 첫 삽입 결과에 이어서 순서대로 삽입하고 중간 tree를 보존할 수 있습니다.
삽입 뒤 inorder와 허용 범위로 BST invariant가 유지되는지 검산할 수 있습니다.
풀이 전에 꼭 알아야 할 말
이진 탐색 트리의 순서 규칙(BST invariant)
어떤 노드 하나만이 아니라 그 노드의 왼쪽 부분 트리 전체가 더 작고 오른쪽 부분 트리 전체가 더 커야 한다는 약속입니다. 이 전역 약속 때문에 한 비교로 반대쪽을 버릴 수 있습니다.
아주 작은 예:\(23<29\)23<29이면 29의 오른쪽 부분 트리는 모두 29보다 커서 23의 후보가 아닙니다.
실패한 검색(search)과 빈 자리(nil)
삽입은 루트에서 검색과 같은 비교를 반복하다가 자식이 없는 nil 방향을 처음 만난 곳에 새 잎을 연결합니다. 기존 노드나 간선을 덮어쓰지 않습니다.
아주 작은 예:\(29.\text{left}=\text{nil}\)29.left=nil에서 멈추면 새 노드 23이 바로 29.left가 됩니다.
순차 삽입
두 값을 차례로 넣으라는 말은 첫 번째 결과 tree가 두 번째 입력 상태가 된다는 뜻입니다. 각 삽입 뒤의 그림이 채점 대상입니다.
아주 작은 예: 23을 그린 뒤 그 tree에서 다시 root 37부터 60을 비교합니다.
비유로 잡기 · 주소 표지판을 따라 빈 방 찾기
각 node를 번호가 적힌 갈림길로 생각합니다. 새 번호가 표지판보다 작으면 왼쪽 복도, 크면 오른쪽 복도로 가며, 처음 만난 빈 방 nil에 입주합니다. 이미 사람이 있는 방이나 복도 중간을 밀어내지는 않습니다.
비유와 실제 개념의 연결: 갈림길 표지 번호와 내 번호 비교는 실제로 현재 node.key와 새 key 비교에 대응합니다. 작은 번호 복도와 큰 번호 복도는 실제로 left/right child 선택에 대응합니다. 처음 발견한 빈 방에 입주는 실제로 nil에 새 leaf 연결에 대응합니다.
비유의 한계: 실제 건물에서는 지름길이나 방 재배치가 가능하지만 plain BST insertion은 한 root-to-nil path만 따르고 자동 rotation이나 균형 조정을 하지 않습니다.
비교 표와 색칠된 path를 함께 읽기
\(23<37 \to L\)23<37 → L
허용 상한이 37이 되고 15로 이동합니다.
\(23>15 \to R\)23>15 → R
허용 구간이 (15,37)로 좁아지고 29로 이동합니다.
\(23<29 \to \)23<29 →왼쪽 빈 자리(nil)
최종 구간 (15,29)에 23이 들어가 29.left가 됩니다.
60: 오른쪽-오른쪽-왼쪽
37,56,85를 거쳐 85.left nil에 연결됩니다.
표의 한 행이 tree 위의 화살표 하나와 대응합니다. 녹색 끝 node는 새로 삽입된 key이며, 기존 node와 edge는 그대로 유지됩니다.
작은 예제로 먼저 연습 · 10, 5가 있는 BST에 7 삽입
root 10의 left child가 5이고 다른 child가 모두 nil인 작은 tree에 key 7을 넣습니다.
7과 10 비교
\(7<10\)7<10이므로 BST invariant상 7이 있다면 left subtree에만 있을 수 있습니다.
이 단계의 상태:\(10 --L\to 5\)10 --L→ 5
7과 5 비교
\(7>5\)7>5이므로 5의 right subtree로 가야 하며 반대쪽 left는 후보가 아닙니다.
이 단계의 상태:\(5 --R\to \text{nil}\)5 --R→ nil
빈 child에 연결
5.right가 첫 nil이므로 기존 edge를 바꾸지 않고 새 leaf 7을 붙입니다.
이 단계의 상태:\(5.\text{right}=7\)5.right=7
작은 예제의 결론: 삽입 위치는 숫자의 전체 정렬 위치를 눈대중으로 고르는 것이 아니라 root에서 시작한 실패 search path가 결정합니다.
독립 학습 안내: 앞 소문항을 읽지 않았어도 이 절의 입력 그림과 개념 설명부터 따라갈 수 있습니다.
이 소문항의 입력
이 소문항의 시작 상태 · 23과 60 삽입이 끝난 이진 탐색 트리
37
15
7
29
23
nil
56
nil
85
60
nil
먼저 90초 도전
해설을 읽기 전에 루트 또는 첫 비교 한 줄을 종이에 적으세요. 정답보다 판단 이유를 말하는 것이 목표입니다.
먼저 문제의 정체부터
BST search는 현재 key와 목표 k를 비교해 한쪽 subtree만 선택합니다. equality면 성공하고 nil에 도착하면 실패입니다.
29는 37보다 작고 15보다 커서 [37,15,29]에서 성공합니다. 50은 37보다 크지만 56보다 작아 \(56.\text{left}=\text{nil}\)56.left=nil로 내려가 실패합니다.
실패 검색도 방문한 실제 node와 마지막 nil 방향을 적어야 합니다. 50과 가까운 47 같은 값이 없다는 이유로 임의 경로를 만들면 안 됩니다.
이 소문항만 읽어도 되는 연결 강의
왜 이 개념이 필요한가
BST search의 핵심은 모든 node를 훑지 않고 비교할 때마다 한쪽 subtree 전체를 안전하게 제외하는 것입니다. 성공뿐 아니라 실패도 nil이라는 명확한 증거로 끝난다는 사실을 이해해야 검색 경로를 정확히 그릴 수 있습니다.
이 절을 읽고 나면 다음을 할 수 있어야 합니다.
목표 key와 현재 key의 비교를 근거로 방문 node와 L/R 방향을 순서대로 기록할 수 있습니다.
성공은 equality에서 즉시 멈추고 실패는 선택한 child가 nil일 때 멈춘다는 차이를 설명할 수 있습니다.
실제 방문 node와 마지막 nil을 구분해 tree 위에 두 검색 경로를 표시할 수 있습니다.
풀이 전에 꼭 알아야 할 말
검색 경로(search path)
루트에서 시작해 매 비교마다 선택한 자식으로 이어지는 한 줄 경로입니다. 이진 탐색 트리의 순서 규칙 때문에 선택하지 않은 부분 트리는 목표를 포함할 수 없습니다.
아주 작은 예:\(k<37\)k<37이면 37의 오른쪽 부분 트리 전체를 방문하지 않습니다.
성공 종료
현재 node.key가 목표와 같아지는 즉시 그 node를 반환하고 search를 끝냅니다. 목표 node의 child는 더 방문하지 않습니다.
아주 작은 예: 29에 도착하면 29.left의 23을 보지 않습니다.
실패 종료와 nil
목표가 가야 할 방향에 child가 없으면 그 BST에는 목표 key가 없습니다. nil은 방문한 key가 아니라 빈 포인터이지만 경로의 마지막 증거로 표시합니다.
아주 작은 예: 56에서 \(50<56\)50<56인데 \(\text{left}=\text{nil}\)left=nil이면 search(50)는 실패입니다.
비유로 잡기 · 정렬된 전화번호부의 범위를 지우기
현재 펼친 기준 번호보다 목표가 작으면 뒤쪽 절반을, 크면 앞쪽 절반을 통째로 후보에서 지운다고 생각합니다. 정확한 번호를 만나면 성공하고, 남은 페이지가 없으면 nil이라 실패합니다.
비유와 실제 개념의 연결: 현재 펼친 기준 번호 확인는 실제로 현재 node와 비교에 대응합니다. 가능하지 않은 절반의 페이지를 통째로 지우기는 실제로 반대 subtree 제외에 대응합니다. 정확한 번호 발견 또는 남은 페이지 없음는 실제로 equality 또는 nil 종료에 대응합니다.
비유의 한계: 전화번호부는 물리적으로 중간을 펼치지만 BST search 비용은 숫자 간 거리가 아니라 실제 tree shape와 root-to-child edge 수가 결정합니다.
성공 path와 실패 path를 별도 색으로 겹쳐 보기
29 검색(search): \(37\to 15\to 29\)37→15→29
왼쪽, 오른쪽 두 비교 뒤 \(29=29\)29=29에서 즉시 찾음(FOUND)입니다.
50 검색(search): \(37\to 56\)37→56
오른쪽으로 이동한 뒤 \(50<56\)50<56이므로 왼쪽 방향을 선택합니다.
\(56.\text{left}=\text{nil}\)56.left=nil
더 비교할 node가 없으므로 NOT FOUND이며 85 쪽은 방문하지 않습니다.
초록 path는 29에서 equality로 끝나고, 주황 path는 56의 왼쪽 nil까지 갑니다. nil은 실제 key node와 다른 점선 원으로 표시합니다.
작은 예제로 먼저 연습 · 10-5-20 tree에서 5와 7 찾기
루트 10, 왼쪽 자식 5, 오른쪽 자식 20인 트리에서 성공 검색(search(5))과 실패 검색(search(7))을 비교합니다.
5 검색(search(5))
\(5<10\)5<10이라 왼쪽으로 가고 \(5=5\)5=5이므로 그 자리에서 성공 종료합니다.
이 단계의 상태:\(10 \to L 5 (\)10 →L 5 (찾음)
search(7)의 첫 두 비교
\(7<10\)7<10이라 5로, \(7>5\)7>5라 5.right 방향을 선택합니다.
이 단계의 상태:\(10 \to L 5 \to R\)10 →L 5 →R
nil에서 실패
5.right에 node가 없으므로 7이 존재할 수 있는 유일한 구간이 비어 있습니다.
이 단계의 상태:\(5.\text{right}=\text{nil} (\text{NOT} \text{FOUND})\)5.right=nil (NOT FOUND)
작은 예제의 결론: 성공과 실패 모두 한 path만 따르며, 성공은 같은 key, 실패는 반드시 선택 방향의 nil이라는 종료 근거를 갖습니다.
독립 학습 안내: 앞 소문항을 읽지 않았어도 이 절의 입력 그림과 개념 설명부터 따라갈 수 있습니다.
이 소문항의 입력
이 소문항이 다시 만들어야 하는 목표 이진 탐색 트리
37
15
7
29
56
nil
85
먼저 90초 도전
해설을 읽기 전에 루트 또는 첫 비교 한 줄을 종이에 적으세요. 정답보다 판단 이유를 말하는 것이 목표입니다.
먼저 문제의 정체부터
빈 BST의 첫 삽입 key는 root가 되므로 37이 반드시 첫 번째입니다. 이후 어떤 node가 자신의 자손보다 먼저 삽입되어야 그 자손이 올바른 parent 아래에 도달합니다.
가장 안전한 정답은 원래 트리의 Preorder입니다. parent를 자식보다 먼저 방문하기 때문에 같은 BST를 재구성합니다.
따라서 [37,15,7,29,56,85]는 즉시 사용할 수 있는 정답입니다. 이 문제의 23과 60은 5(b)에서 추가된 값이므로 원래 순서에 넣으면 안 됩니다.
이 소문항만 읽어도 되는 연결 강의
왜 이 개념이 필요한가
같은 key 집합도 삽입 순서에 따라 BST shape가 크게 달라집니다. 완성 tree를 보고 가능한 과거 순서를 구성하는 문제는 parent가 먼저 존재해야 descendant가 올바른 자리에 도달한다는 인과 관계를 이해하는 훈련입니다.
이 절을 읽고 나면 다음을 할 수 있어야 합니다.
빈 BST의 첫 삽입 key가 root가 된다는 사실로 순서의 첫 원소를 결정할 수 있습니다.
모든 ancestor가 descendant보다 먼저 삽입되어야 한다는 dependency를 tree에서 읽을 수 있습니다.
제안한 순서를 실제로 재생해 원래 edge와 shape를 복원하는지 검산할 수 있습니다.
풀이 전에 꼭 알아야 할 말
조상(ancestor)과 자손(descendant)
어떤 노드에서 자식 간선을 한 번 이상 따라 내려가 만나는 노드가 자손이고, 위쪽 노드는 조상입니다. 부모-자식보다 넓은 관계입니다.
아주 작은 예: 37은 15의 부모이면서 7과 29의 조상입니다.
빈 이진 탐색 트리(BST)의 첫 삽입
비교할 노드가 전혀 없으므로 첫 키가 루트가 됩니다. 일반 이진 탐색 트리에는 나중에 루트를 자동 교체하는 회전(rotation)이 없습니다.
아주 작은 예: 원래 루트가 37이면 가능한 순서는 반드시 37로 시작합니다.
전위 순회(Preorder)의 부모 우선 성질
전위 순회는 각 부분 트리 루트를 먼저 출력한 뒤 그 자손을 출력합니다. 그래서 키가 중복되지 않는 이진 탐색 트리의 전위 순회는 같은 모양을 만드는 안전한 삽입 순서입니다.
아주 작은 예: [37,15,7]에서는 37과 15가 7보다 먼저 준비됩니다.
비유로 잡기 · 조직도 등록 순서
빈 인사 시스템에서 대표가 먼저 등록되어야 부서장이 그 아래에 들어가고, 부서장이 먼저 있어야 팀원이 올바른 부서에 연결됩니다. 서로 다른 부서의 등록은 섞어도 되지만 자기 부서의 상사는 먼저 있어야 합니다.
비유와 실제 개념의 연결: 대표를 가장 먼저 등록는 실제로 루트 37이 먼저에 대응합니다. 부서장 계정을 팀원보다 먼저 생성는 실제로 ancestor before descendant에 대응합니다. 서로 다른 부서 등록 작업은 사이에 섞을 수 있음는 실제로 left/right subtree 독립에 대응합니다.
비유의 한계: 실제 조직 시스템은 나중에 상사를 바꿀 수 있지만 plain BST insertion은 기존 node를 재배치하지 않습니다. 여기서는 insertion만 허용됩니다.
먼저 와야 하는 관계를 화살표로 보기
\(37 \to 15, 56\)37 → 15, 56
root가 두 subtree root보다 먼저 존재해야 합니다.
\(15 \to 7, 29\)15 → 7, 29
15가 먼저 있어야 7과 29가 37의 직접 child가 되지 않습니다.
\(56 \to 85\)56 → 85
56이 먼저 있어야 85가 37.right를 차지하지 않습니다.
화살표 \(A\to B\)A→B는 A가 B보다 먼저 삽입되어야 한다는 뜻입니다. 이 DAG의 화살표 방향을 거스르지 않는 한 줄 순서 하나가 답입니다.
작은 예제로 먼저 연습 · 10의 children 5,20을 만드는 순서
원하는 tree가 root 10, left child 5, right child 20인 경우 가능한 삽입 순서를 구성합니다.
10을 첫 번째로 둔다
빈 tree의 첫 key가 root이므로 다른 key로 시작하면 root shape가 달라집니다.
이 단계의 상태: [10]
5를 삽입한다
\(5<10\)5<10이므로 10.left에 연결됩니다. 아직 다른 node가 경로를 가로막지 않습니다.
이 단계의 상태: [10,5]
20을 삽입한다
\(20>10\)20>10이므로 10.right에 연결되어 목표 tree가 완성됩니다.
이 단계의 상태: [10,5,20]
작은 예제의 결론: Preorder [10,5,20]은 root와 parent를 children보다 먼저 보장하므로 원래 shape를 재현합니다.
원래 tree의 root 37입니다. 15나 56이 먼저 들어가면 그 key가 root가 되어 원래 tree를 만들 수 없습니다.
왼쪽 subtree에서 강제되는 순서는 무엇인가?
15가 7과 29보다 먼저여야 합니다. 7과 29 사이에는 ancestor 관계가 없어 둘의 상대 순서는 자유롭습니다.
오른쪽 subtree에서 강제되는 순서는 무엇인가?
56이 85보다 먼저여야 85가 37의 직접 right child를 차지하지 않고 56.right에 도달합니다.
안전한 순서 하나는 어떻게 즉시 얻는가?
원래 tree의 Preorder [37,15,7,29,56,85]를 사용합니다. 모든 subtree에서 root가 descendants보다 먼저 나옵니다.
제안 순서를 어떻게 검산하는가?
빈 tree에서 여섯 insertion을 실제로 재생해 \(\text{dependency} \text{edge} 37\to 15/56, 15\to 7/29, 56\to 85\)dependency edge 37→15/56, 15→7/29, 56→85가 모두 생기는지 확인합니다.
가능한 순서 하나
\[\langle 37,15,7,29,56,85\rangle\]
조상이 자손보다 먼저 나오도록 구성한 삽입 순서입니다.
37이 먼저; 15가 7보다 먼저; 15가 29보다 먼저; 56이 85보다 먼저
조상 의존 관계 그래프(DAG) · 화살표 출발 키가 먼저
Preorder 한 답을 빈 BST에서 재생
순서
키
생기는 위치
1
37
빈 tree의 root가 된다.
2
15
\(15<37\)15<37이므로 37.left가 된다.
3
7
\(7<37, 7<15\)7<37, 7<15이므로 15.left가 된다.
4
29
\(29<37, 29>15\)29<37, 29>15이므로 15.right가 된다.
5
56
\(56>37\)56>37이므로 37.right가 된다.
6
85
\(85>37, 85>56\)85>37, 85>56이므로 56.right가 된다.
5(d)에서 확인한 이진 탐색 트리
37
15
7
29
56
nil
85
실제 풀이를 마친 뒤
답이 맞는지 스스로 검산
재생 후 root가 37이고 edge 집합이 {(37,15),(37,56),(15,7),(15,29),(56,85)}인지 비교합니다.
최종 inorder가 [7,15,29,37,56,85]로 정렬되고 node 수가 여섯인지 확인합니다.
5(b)에서 나중에 추가한 23과 60이 원래 tree 순서에 섞이지 않았는지 확인합니다.
30초 자가점검
정렬된 Inorder [7,15,29,37,56,85]를 삽입하면 같은 tree인가?
힌트: 첫 key가 무엇이 되는지부터 봅니다.
정답: 아닙니다. 첫 key 7이 root가 되고 계속 큰 값이 right로 붙어 오른쪽 사슬에 가까운 다른 shape가 됩니다.
7과 29 중 어느 것이 먼저여야 하는가?
힌트: 둘 사이에 ancestor 관계가 있는지 확인합니다.
정답: 15가 먼저라는 조건만 지키면 7과 29의 상대 순서는 어느 쪽도 가능합니다. 둘은 서로 독립인 sibling입니다.
시험 답안 템플릿
한 가능한 순서는 Preorder 그대로 [37,15,7,29,56,85]이다. parent가 자손보다 먼저 삽입되므로 동일한 tree shape가 재현된다.
초보자가 자주 틀리는 지점
23과 60을 원래 tree의 key로 포함한다.
37 이외의 key로 시작한다.
7을 15보다 먼저 넣어 7이 37의 직접 왼쪽 자식이 되게 한다.
85를 56보다 먼저 넣어 85가 37의 직접 오른쪽 자식이 되게 한다.
정렬된 Inorder 순서를 넣으면 같은 균형 트리가 된다고 생각한다. 실제로는 오른쪽 사슬이 됩니다.
배점: 1점
5(e) · 다른 삽입 순서가 존재하는 이유와 전체 조건
5(d)의 답 외에도 같은 원래 BST를 만드는 다른 삽입 순서가 있는가? 이유를 설명하시오.
독립 학습 안내: 앞 소문항을 읽지 않았어도 이 절의 입력 그림과 개념 설명부터 따라갈 수 있습니다.
이 소문항의 입력
이 소문항이 다시 만들어야 하는 같은 목표 이진 탐색 트리
37
15
7
29
56
nil
85
먼저 90초 도전
해설을 읽기 전에 루트 또는 첫 비교 한 줄을 종이에 적으세요. 정답보다 판단 이유를 말하는 것이 목표입니다.
먼저 문제의 정체부터
네, 많이 있습니다. 동일 subtree 안에서는 parent가 descendant보다 먼저라는 제약을 지켜야 하지만, 왼쪽 subtree와 오른쪽 subtree의 원소는 서로 interleave할 수 있습니다.
예를 들어 [37,56,15,85,29,7]도 같은 트리를 만듭니다. 37이 먼저이고, 15가 7·29보다 먼저이며, 56이 85보다 먼저라는 핵심 제약을 모두 만족합니다.
이 문제는 아무 permutation이나 된다는 뜻이 아닙니다. tree가 정의하는 ancestor partial order를 보존하는 순서만 가능합니다.
이 소문항만 읽어도 되는 연결 강의
왜 이 개념이 필요한가
BST insertion 순서는 하나의 고정된 history가 아니라 ancestor 제약을 만족하는 여러 가능한 history입니다. 강제되는 관계와 자유롭게 섞을 수 있는 관계를 구분하면 ‘다른 순서가 있는가’에 예시와 이유를 함께 답할 수 있습니다.
이 절을 읽고 나면 다음을 할 수 있어야 합니다.
같은 tree를 만드는 순서에서 반드시 지켜야 하는 ancestor-before-descendant 제약을 열거할 수 있습니다.
서로 다른 left/right subtree 작업은 내부 순서를 보존한 채 interleave할 수 있음을 설명할 수 있습니다.
대안 순서를 실제로 삽입 재생하고, 선택 심화인 20개 계산을 필수 답안과 구분할 수 있습니다.
풀이 전에 꼭 알아야 할 말
부분 순서(partial order)
모든 두 원소의 순서를 강제하지 않고 일부 선행 관계만 정하는 규칙입니다. 이 트리에서는 37이 먼저, 15가 7과 29보다 먼저, 56이 85보다 먼저라는 관계만 강제됩니다.
아주 작은 예: 15와 56 사이에는 어느 쪽이 먼저라는 화살표가 없습니다.
순서 보존 끼워 넣기(interleaving)
두 순회열 각각의 내부 순서는 유지하면서 한 줄로 섞는 것입니다. 서로 다른 부분 트리는 루트에서 즉시 분리되므로 이렇게 섞어도 상대 구조가 변하지 않습니다.
아주 작은 예: [15,7]과 [56,85]를 [56,15,85,7]처럼 섞을 수 있습니다.
조합 \(\binom{n}{k}\)
n개의 위치 중 k개를 고르는 방법 수입니다. 이 문제에서는 루트 뒤 다섯 위치 중 왼쪽 부분 트리 세 위치를 선택할 때만 선택 심화로 사용합니다.
아주 작은 예:\(C(5,3)=10\)C(5,3)=10이며 원문 정답에는 이 계산이 필수가 아닙니다.
비유로 잡기 · 선수과목이 있는 시간표
어떤 과목은 선수과목 뒤에만 들을 수 있지만 서로 독립인 과목은 어느 학기에 먼저 배치해도 됩니다. BST의 ancestor가 선수과목이고 descendant가 후속 과목이며, left와 right subtree는 독립 트랙입니다.
비유와 실제 개념의 연결: 선수과목을 먼저 수강는 실제로 ancestor-before-descendant에 대응합니다. 서로 독립인 전공 트랙 과목을 섞어 배치는 실제로 left/right subtree interleaving에 대응합니다. 선수과목 전에 후속 과목을 신청한 시간표는 실제로 invalid permutation에 대응합니다.
비유의 한계: 실제 수강에는 학기 수나 동시 수강 조건이 있지만 BST에는 오직 insertion 순서와 비교 path만 있습니다. 조합 개수는 설명용 심화이며 시험 문언의 필수 요구가 아닙니다.
dependency DAG와 대안 순서 재생
강제: 37 먼저
root가 첫 key가 아니면 같은 tree가 될 수 없습니다.
강제: \(15\to 7,29 / 56\to 85\)15→7,29 / 56→85
각 subtree의 parent가 descendants보다 먼저입니다.
자유: 왼쪽과 오른쪽 부분 트리 섞기
15·7·29 작업과 56·85 작업의 상대 위치는 순서를 보존하며 끼워 넣을 수 있습니다.
대안: 37,56,15,85,29,7
강제 화살표를 모두 지키면서 Preorder와 다른 한 줄 순서를 만듭니다.
DAG 화살표는 강제 관계이고 화살표가 없는 sibling·다른 subtree 사이는 자유입니다. 아래 대안 sequence를 한 칸씩 재생하면 원래 edge가 그대로 만들어집니다.
작은 예제로 먼저 연습 · 10-root tree의 두 대안 순서
root 10, left child 5, right child 20인 tree에서 [10,5,20] 외의 순서를 찾습니다.
10을 먼저 고정
root dependency는 자유가 아니므로 두 valid sequence 모두 10으로 시작합니다.
이 단계의 상태: 10
right 20을 먼저 삽입
5와 20은 서로 ancestor가 아니어서 20을 5보다 먼저 넣어도 됩니다.
이 단계의 상태: 10,20
left 5 삽입
\(5<10\)5<10이라 10.left로 가며 이미 있는 right subtree 20의 구조에 영향을 주지 않습니다.
이 단계의 상태: 10,20,5
작은 예제의 결론: [10,20,5]도 같은 tree를 만들므로 Preorder는 안전한 한 답이지 유일한 history가 아닙니다.