5. Grundlegende Datenstrukturen (7 Punkte)

5(c) · 29와 50 검색 경로 — 성공과 실패를 모두 끝까지 기록하기

선행지식이 전혀 없어도 이 페이지 하나에서 용어를 배우고, 작은 예제를 거쳐 실제 시험 풀이와 검산까지 따라가도록 구성했습니다.

  1. 용어: 기호와 전제
  2. 직관: 비유와 작은 예
  3. 풀이: 실제 상태 변화
  4. 확인: 검산과 자가점검

자료의 성격과 정확성 경계

시험 문언과 숫자·배점은 비공식 복기 자료 lines 246-268에서 가져왔습니다. 정의와 알고리즘은 현재 강의 Lecture 03 pp.46-51, 66-71, 80-81 및 Sheet05-GrpSol pp.7-12로 교차 확인했습니다. 이 문제의 key는 모두 서로 다르며, duplicate가 있는 일반 BST에서는 강의나 구현이 정한 equality 방향을 먼저 밝혀야 합니다.

문제를 읽기 전에 알아둘 기호와 용어

기호를 모른 채 풀이를 외우지 않도록, 이 문제에서 실제로 쓰는 뜻과 작은 예를 먼저 확인합니다.

기호·용어뜻작은 예
노드(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은 전위 순회의 첫 값이고 중위 순회의 가운데 분할점입니다.

먼저 문제의 정체를 줄글로 이해하기

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 같은 값이 없다는 이유로 임의 경로를 만들면 안 됩니다.

필요한 개념을 깊게 배우기

개념 1

0단계 · 검색(search) 의사코드

x가 빈 자리(nil)이거나 \(x.\text{key}=k\)x.key=k이면 반환합니다. 그렇지 않고 \(k<x.\text{key}\)k<x.key면 왼쪽, \(k>x.\text{key}\)k>x.key면 오른쪽으로 이동합니다.

이진 탐색 트리의 순서 규칙 때문에 선택하지 않은 반대 부분 트리에는 k가 있을 수 없어 버려도 안전합니다.

수식으로 정확히 쓰기

핵심 규칙x=\varnothing\ \lor\ \(k=x.\)k=x.\mathrm{key}\;\Longrightarrow\;\mathrm{stop}

핵심 규칙\(k<x.\)k<x.\mathrm{key}\;\Longrightarrow\;\mathrm{left}

핵심 규칙\(k>x.\)k>x.\mathrm{key}\;\Longrightarrow\;\mathrm{right}

개념 2

1단계 · 29 검색(search)

37에서 \(29<37\)29<37이므로 왼쪽 15, 15에서 \(29>15\)29>15이므로 오른쪽 29로 갑니다. 값이 같으므로 즉시 성공합니다.

29의 자식 23까지 내려가면 안 됩니다. 목표를 찾은 순간 검색은 종료합니다.

수식으로 정확히 쓰기

핵심 규칙37\to15\to29\quad(29=29,\;\text{성공})

개념 3

2단계 · 50 검색(search)

37에서 \(50>37\)50>37이므로 오른쪽 56으로 갑니다. 56에서 \(50<56\)50<56이므로 왼쪽으로 가야 하지만 \(\text{left}=\text{nil}\)left=nil입니다.

따라서 방문 키는 [37,56]이고 경로 표기에는 그 뒤 \(\text{left}\to \text{nil}\)left→nil을 붙입니다.

수식으로 정확히 쓰기

핵심 규칙37\to56\to\varnothing\quad(\text{실패})

개념 4

3단계 · 검색 비용

방문 노드 수는 경로 길이에 비례하고 최악 \(O(h)\)O(h)입니다. 찾는 키의 수치가 루트와 가깝다는 사실은 중요하지 않고 트리 모양이 결정합니다.

성공과 실패 모두 잎 방향 한 경로만 조사합니다.

수식으로 정확히 쓰기

\[T_{\text{검색}}(h)=O(h)\]T_{\text{검색}}(h)=O(h)
초보자용 연결 강의

이 소문제를 왜 배우나

BST search의 핵심은 모든 node를 훑지 않고 비교할 때마다 한쪽 subtree 전체를 안전하게 제외하는 것입니다. 성공뿐 아니라 실패도 nil이라는 명확한 증거로 끝난다는 사실을 이해해야 검색 경로를 정확히 그릴 수 있습니다.

풀이 전에 꼭 알아야 할 말

검색 경로(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이라는 종료 근거를 갖습니다.

이제 실제 시험 문제에 연결

어느 tree에서 검색을 시작해야 하는가?

문언이 5(b)의 resulting tree를 요구하므로 23과 60이 모두 들어간 최종 tree에서 root 37부터 시작합니다.

29는 어떤 비교를 거치는가?

\(29<37\)29<37이라 \(\text{left} 15, 29>15\)left 15, 29>15라 right 29로 갑니다. \(29=29\)29=29이므로 visited는 [37,15,29]이고 성공입니다.

왜 29 아래의 23은 방문하지 않는가?

현재 key가 목표와 같아진 순간 알고리즘이 반환하기 때문입니다. child 탐색은 equality가 아닐 때만 수행합니다.

50은 왜 85 방향으로 가지 않는가?

\(50>37\)50>37이라 56에 왔지만 \(50<56\)50<56입니다. 따라서 반드시 56.left를 선택하며 그 자리가 nil이라 즉시 실패합니다.

답안에 무엇을 그려야 하는가?

각 target마다 방문 node를 순서대로 연결하고 edge에 L/R을 표시합니다. 실패 path에는 마지막 \(\text{left}\to \text{nil}\)left→nil도 포함하되 nil을 visited key 목록에는 넣지 않습니다.

답이 맞는지 스스로 검산

  • search(29)의 모든 이동은 \(29<37, 29>15, 29=29\)29<37, 29>15, 29=29와 일치하며 equality 뒤 추가 edge가 없어야 합니다.
  • search(50)의 허용 범위는 \(37<50<56\)37<50<56이고 56.left가 비어 있으므로 다른 subtree에 50이 있을 가능성이 없습니다.
  • visited key 목록은 각각 [37,15,29]와 [37,56]이고, nil은 두 번째 경로 그림의 terminal일 뿐 목록의 key가 아닙니다.

30초 자가점검

search(29)가 23까지 내려가면 첫 오류는 무엇인가?

힌트: search의 base case를 떠올립니다.

정답: \(29=\)29=목표를 확인하고도 종료하지 않은 것이 첫 오류입니다. equality에서는 즉시 29를 반환해야 합니다.

search(50)에서 56 다음에 85를 방문할 수 있는가?

힌트: 50과 56의 대소를 비교합니다.

정답: 없습니다. \(50<56\)50<56이므로 left만 가능하고 \(\text{left}=\text{nil}\)left=nil입니다. 85는 right subtree라 후보에서 제외됩니다.

마지막에 쓰는 시험 답안 틀

29 검색(search): [37,15,29]를 방문해 \(29=29\)29=29에서 찾음(FOUND). 50 검색(search): [37,56]을 방문하고 \(56.\text{left}=\text{nil}\)56.left=nil이므로 없음(NOT FOUND).

자주 하는 실수

근거와 정확성 범위

복기 문언, 강의 정의, 공식 연습 풀이, 추가 유도를 구분해 표시합니다.

마지막 생성: 2026-08-02 08:51