연결 리스트·트리·순회·이진 탐색 트리

이진 탐색 트리와 순회(BSTs and traversals)

1타 강사식 학습 동선

직관 → 조작 → 예시 → 함정 → 답안

오프닝: BST(Binary Search Tree, binärer Suchbaum)는 '정렬된 숫자 그림'이 아니라, 한 번 비교할 때마다 한쪽 subtree(Teilbaum) 전체를 버리게 해 주는 약속입니다. 예를 들어 70을 찾는데 root가 50이면 50 이하가 모인 왼쪽은 볼 필요가 없습니...

트리(tree/Baum), 노드(node/Knoten), 간선(edge/Kante), 루트(root/Wurzel)부모(parent/Elternknoten), 자식(child/Kind), 형제(sibling/Geschwister)잎(leaf/Blatt), 내부 노드(inner node/innerer Knoten), 부분 트리(subtree/Teilbaum)조상(ancestor/Vorfahre), 자손(descendant/Nachkomme)depth(Tiefe): root에서 해당 node까지 내려간 edge 수

연습으로 이동 개인화 순서 보기

01 직관이 개념이 왜 필요한지 한 문장으로 잡기

02 손풀이그래프, 트리, 표, 문자열을 직접 움직이며 확인하기

03 단계별 예제시험 답안처럼 조건과 결론을 연결하기

04 함정 점검자주 틀리는 조건과 반례를 먼저 차단하기

트리(Baum) · 이진 탐색 트리(binärer Suchbaum) · 순회(Traversierung)

BST는 비교 한 번마다 한쪽 부분 트리 전체를 버리는 검색 트리입니다

초보자에게 가장 중요한 직관은 “노드 하나만 비교하는 것이 아니라 부분 트리(subtree) 전체에 대한 범위를 유지한다”입니다. 이진 탐색 트리(Binary Search Tree, BST, binärer Suchbaum)는 모든 노드 v에 대해 왼쪽 부분 트리의 모든 키가 v.key 이하이고 오른쪽 부분 트리의 모든 키가 v.key보다 크다는 불변식(invariant)을 갖습니다. 이 강의에서는 Sheet05의 규칙에 맞춰 중복 키(duplicate)를 왼쪽으로 보냅니다.

순회(traversal, Traversierung)는 트리를 바꾸는 연산이 아니라 같은 트리를 어떤 순서로 읽을지 정하는 규칙입니다. 전위 순회(preorder)는 루트가 처음, 중위 순회(inorder)는 루트가 가운데, 후위 순회(postorder)는 루트가 마지막입니다. 중위 순회 결과가 정렬되는 것은 임의의 이진 트리가 아니라 BST 불변식이 있을 때만 참입니다.

핵심 용어와 공식

부분 트리 전체 불변식, 순회 순서, 높이 h를 분리해서 말하세요

BST 불변식 (invariant)

\[∀ v: \text{keys}(\text{left}(v)) \le v.\text{key} < \text{keys}(\text{right}(v))\]∀ v: keys(left(v)) ≤ v.key < keys(right(v))

바로 아래 자식(immediate child)만 비교하면 부족합니다. 모든 자손(descendant)이 조상(ancestor)이 만든 하한과 상한(lower/upper bound)을 지켜야 합니다.

검색 경로의 누적 경계

\[\text{right}(a) \Rightarrow \text{lower} := a; \text{left}(b) \Rightarrow \text{upper} := b\]right(a) ⇒ lower := a; left(b) ⇒ upper := b

경로 검증(path validation)은 이전 노드만 보는 문제가 아니라 누적 구간(interval)을 계속 갱신하는 문제입니다.

연산 비용

\[\text{search} = \text{insert} = \text{delete} = O(h)\]search = insert = delete = O(h)

일반 BST(plain BST)의 일반 경계는 \(O(h)\)O(h)입니다. h가 log n이면 \(O(\log n)\)O(log n), 한쪽 사슬(chain)이면 \(O(n)\)O(n)입니다.

순회 규칙 (traversal rules)

\[\text{preorder} = \text{루트}-\text{left}-\text{right}; \text{inorder} = \text{left}-\text{루트}-\text{right}; \text{postorder} = \text{left}-\text{right}-\text{루트}\]preorder = root-left-right; inorder = left-root-right; postorder = left-right-root

이름보다 루트(root) 위치를 기억하세요. pre는 루트가 처음, in은 가운데, post는 마지막입니다.

자식이 둘인 노드 삭제

\[\text{successor}(v) = \min(\text{right} \text{subtree}), \text{predecessor}(v) = \max(\text{left} \text{subtree})\]successor(v) = min(right subtree), predecessor(v) = max(left subtree)

아무 잎(leaf)이나 올리면 불변식이 깨질 수 있습니다. 바로 다음 또는 바로 이전 키(key)를 씁니다.

순회의 실행 시간

\[T_{\text{traversal}}(n) = \Theta(n)\]T(traversal)(n) = Θ(n)

순회는 가지치기(pruning)하지 않고 모든 노드를 한 번씩 방문합니다. 검색처럼 \(O(h)\)O(h)가 아닙니다.

그림으로 보는 Sheet05 트리, 검색 경로, 순회 순서

\(50 \to 80 \to 60 \to 70\)50 → 80 → 60 → 70 50 30 15 20 80 60 70 90 70 > 50: 오른쪽 70 <= 80: 왼쪽 70 > 60: 오른쪽 누적되는 값의 경계 시작 \((-\text{inf},+\text{inf}) \to 50\)(-inf,+inf) → 50뒤 (50,+inf) 80 뒤 \((50,80) \to 60\)(50,80) → 60뒤 (60,80) 순회 순서 전위 순회: 루트가 먼저 50, 30, 15, 20, 80, 60, 70, 90 중위 순회: 루트가 가운데, BST에서만 정렬됨 15, 20, 30, 50, 60, 70, 80, 90 후위 순회: 루트가 마지막 20, 15, 30, 70, 60, 90, 80, 50 균형 상태 \(h = \Theta(\log n)\)h = Θ(log n) \(O(h)=O(\log n)\)O(h)=O(log n) 한쪽으로 치우친 사슬 \(h = \Theta(n)\)h = Θ(n) \(O(h)=O(n)\)O(h)=O(n)

중위 순회(inorder)가 정렬되는 이유는 순회 규칙만이 아니라 BST 불변식과 결합되기 때문입니다.

연산별 알고리즘 단계

검색(Search)

루트에서 시작해 \(k = \text{key}\)k == key이면 성공, \(k \le \text{key}\)k ≤ key이면 왼쪽, \(k > \text{key}\)k > key이면 오른쪽으로 갑니다. 매 비교마다 반대쪽 부분 트리 전체를 버립니다.

삽입(Insert)

실패한 검색이 끝나는 nil 위치에 새 잎을 붙입니다. 균형을 자동으로 맞추지 않는 일반 BST에서는 삽입 순서가 높이를 망칠 수 있습니다.

삭제(Delete)

잎 삭제, 자식 하나 우회(one-child bypass), 자식 둘 대체(two-child replacement)로 나눕니다. 자식이 둘이면 후속자(successor) 또는 선행자(predecessor)로 키를 교체합니다.

순회(Traversal)

전위·중위·후위 순회는 모두 \(\Theta(n)\)Θ(n)입니다. 레벨 순회(level-order)는 큐(queue)를 쓰는 BFS식 방문입니다.

시험 핵심, 오개념, 객관식 함정

함정: 자식만 비교하면 된다

거짓입니다. BST 성질은 부분 트리 전체에 대한 조건이므로 조상이 만든 경계(ancestor bounds)를 누적해야 합니다.

함정: 모든 중위 순회는 정렬된다

거짓입니다. BST에서만 중위 순회가 정렬 순서(sorted order)를 보장합니다.

함정: BST 검색은 항상 \(O(\log n)\)`O(log n)`이다

거짓입니다. 일반 BST의 경계는 \(O(h)\)O(h)이고 h는 \(\Theta(n)\)Θ(n)까지 커질 수 있습니다.

함정: 순회는 \(O(h)\)`O(h)`이다

거짓입니다. 전체 순회(full traversal)는 모든 노드를 방문하므로 \(\Theta(n)\)Θ(n)입니다.

함정: 전위와 후위 순회는 서로 역순이다

거짓입니다. 루트 위치가 다를 뿐 일반적으로 서로 역순(reverse)이 아닙니다.

함정: 삭제할 때 아무 잎이나 올릴 수 있다

거짓입니다. 자식이 둘인 노드 삭제에는 \(\text{successor}=\min(\text{right})\)successor=min(right) 또는 \(\text{predecessor}=\max(\text{left})\)predecessor=max(left)를 씁니다.

구두 답안 예시

BST는 binary tree에 ordering invariant를 붙인 자료구조입니다. 모든 node v에 대해 left subtree의 모든 key는 v.key 이하이고 right subtree의 모든 key는 v.key보다 큽니다. Search는 root에서 비교하며 한 방향 subtree만 선택하므로 \(O(h)\)O(h)입니다. Insert도 실패한 search 위치에 붙이므로 \(O(h)\)O(h), delete도 node나 replacement를 찾는 데 height가 지배합니다. Traversal은 읽는 순서입니다. Preorder는 root-left-right, inorder는 left-root-right, postorder는 left-right-root이고, BST에서 inorder는 sorted order를 줍니다. 하지만 plain BST는 균형 보장이 없어서 h가 \(\Theta(\log n)\)Θ(log n)이면 \(O(\log n)\)O(log n), degenerate chain이면 \(O(n)\)O(n)입니다.

능동 회상

Tree(Baum), root(Wurzel), leaf(Blatt), subtree(Teilbaum), depth(Tiefe), height(Höhe)를 정의하세요.
BST invariant를 duplicate convention까지 포함해 말하세요.
Search(70)이 50 -> 80 -> 60 -> 70으로 가는 비교를 설명하세요.
Preorder, inorder, postorder의 root 위치를 말하고 위 tree의 sequence를 계산하세요.
왜 inorder sorted는 arbitrary binary tree에서는 false인가요?
\(O(h)\)O(h), \(O(\log n)\)O(log n), \(O(n)\)O(n)의 관계를 balanced와 degenerate height로 설명하세요.
Two-child delete에서 successor와 predecessor가 무엇인지 말하세요.

강의 자료에 근거한 참고 사항

Vorlesung\03BasicDataStructures.pdf 45~57쪽: 트리 용어와 순회 순서.
Vorlesung\03BasicDataStructures.pdf 64~81쪽: BST 조건, 검색, 삽입, 삭제, \(O(h)\)O(h) 비용 표.
Übung\AuD26_Sheet05.pdf, Übung\AuD26_Sheet05-Sol.pdf, Übung\AuD26_Sheet05-GrpSol.pdf: 삽입 순서, 순회 결과, 삭제 경우, 검색 경로 경계, BST 정렬 실행 시간.
AuD Gedächtnisprotokoll SoSe 2025: 순회와 BST 높이에 관한 객관식 함정.

바로 사용하는 AI 학습 프롬프트

Vorlesung/03BasicDataStructures.pdf, Übung/AuD26_Sheet05.pdf, Übung/AuD26_Sheet05-Sol.pdf, Übung/AuD26_Sheet05-GrpSol.pdf를 첨부합니다. AUD 시험용 BST와 순회를 한국어로 가르쳐 주세요. 트리(Baum), 노드(Knoten), 루트(Wurzel), 잎(Blatt), 부분 트리(Teilbaum), 깊이(Tiefe), 높이(Höhe), 이진 탐색 트리(binärer Suchbaum), 순회(Traversierung)는 함께 표시하세요. 삽입 순서 50, 30, 15, 80, 20, 60, 90, 70을 사용해 트리를 그리고, Search(70), 중위·전위·후위 순회, 15/70/80 삭제, 누적 검색 경로 경계, BST 정렬의 최선·최악 실행 시간을 계산하세요. 능동 회상 문제를 한 번에 하나씩 묻고 엄격하게 채점해 주세요.

수식 표기

읽는 순서가 보이는 핵심 공식

정의, 수식, 시험 판정 문장을 분리해서 공식이 답안에서 어떻게 쓰이는지 바로 확인합니다.

BST 불변식: 부분 트리 전체의 순서

BST 조건은 immediate child 비교가 아니라 subtree 전체에 걸리는 범위 조건입니다.

\[\text{forall} v: \max(\text{left} \text{subtree} \text{of} v) \le v.\text{key} < \min(\text{right} \text{subtree} \text{of} v)\]forall v: max(left subtree of v) ≤ v.key < min(right subtree of v)

v: 현재 node
left subtree: v의 왼쪽 아래에 매달린 모든 node
right subtree: v의 오른쪽 아래에 매달린 모든 node
이 페이지 convention: duplicate는 왼쪽으로 보냅니다

시험 답안에는 반드시 'left child'가 아니라 'left subtree의 모든 key'라고 말하세요.

검색 경로의 누적 경계(Search-path bounds)

Search path가 가능한지 검사할 때는 모든 ancestor가 만든 bound를 누적합니다.

\[\text{go} \text{right} \text{at} a \Rightarrow \text{lower} = a; \text{go} \text{left} \text{at} b \Rightarrow \text{upper} = b\]go right at a => lower = a; go left at b => upper = b

lower bound: 지금 이후 key가 반드시 더 커야 하는 값
upper bound: 지금 이후 key가 반드시 작거나 같아야 하는 값
Sheet05 G5는 이 interval을 계속 갱신하는 문제입니다

153에서 left로 갔으면 이후 값은 모두 <= 153이어야 하므로 마지막 156은 불가능합니다.

BST 연산 비용

Search, insert, delete는 모두 먼저 root-to-leaf 방향 path를 따라갑니다.

\[T_{\text{search}} = T_{\text{insert}} = T_{\text{delete}} = O(h)\]T(search) = T(insert) = T(delete) = O(h)

h: 트리 높이(tree height)
n: 노드 수(node count)
\(O(h)\)O(h)는 plain BST의 일반 bound입니다

\(O(\log n)\)O(log n)이라고 쓰려면 \(h = \Theta(\log n)\)h = Θ(log n)이라는 balance 조건이 있어야 합니다.

균형 높이와 퇴화 높이의 비교

Plain BST는 자동으로 균형을 맞추지 않습니다.

\[h = \Theta(\log n) \Rightarrow O(\log n), \text{while} h = \Theta(n) \Rightarrow O(n)\]h = Θ(log n) => O(log n), while h = Θ(n) => O(n)

balanced: 높이가 로그 수준
degenerate: 한 줄 chain처럼 된 tree
sorted insertion은 degenerate worst case를 만들 수 있습니다

Sheet05 G6(b)의 \(\text{BST}-\text{sort} \text{worst} \text{case} \Theta(n^{2})\)BST-sort worst case Θ(n²)는 insert 비용 합이 커지기 때문입니다.

순회 규칙(Traversal rules)

Pre/in/post는 root를 언제 print하느냐로 구분합니다.

\[\text{preorder} = \text{루트}-\text{left}-\text{right}; \text{inorder} = \text{left}-\text{루트}-\text{right}; \text{postorder} = \text{left}-\text{right}-\text{루트}\]preorder = root-left-right; inorder = left-root-right; postorder = left-right-root

전위 순회(preorder): 루트가 처음
중위 순회(inorder): 루트가 가운데
후위 순회(postorder): 루트가 마지막
level-order: queue로 depth 순서 방문

BST에서만 inorder가 sorted order입니다. 일반 binary tree에는 적용하면 안 됩니다.

순회 실행 시간

Traversal은 pruning 없이 모든 node를 읽습니다.

\[T_{\text{traversal}}(n) = \Theta(n)\]T(traversal)(n) = Θ(n)

각 node는 한 번 방문됩니다
search처럼 한쪽 subtree를 버리는 과정이 아닙니다

Traversal을 \(O(h)\)O(h)라고 쓰는 것은 MC 함정입니다.

자식이 둘인 노드의 삭제 대체값

두 child가 있는 node를 지울 때는 정렬 순서에서 바로 이웃한 값을 올려야 합니다.

\[\text{successor}(v) = \min(v.\text{right}); \text{predecessor}(v) = \max(v.\text{left})\]successor(v) = min(v.right); predecessor(v) = max(v.left)

successor: 오른쪽 subtree에서 가장 작은 key
predecessor: 왼쪽 subtree에서 가장 큰 key

아무 leaf나 올리면 BST invariant가 깨질 수 있습니다.

높이가 BST 정렬에 미치는 영향

BST로 sort하려면 n개를 insert한 뒤 inorder로 출력합니다.

\[\sum_{i} O(h_{i}) + \Theta(n)\]sumᵢ O(hᵢ) + Θ(n)

\(h_{i}\)hᵢ: i번째 insert 시점의 height
inorder 출력은 \(\Theta(n)\)Θ(n)
height가 커지면 build 단계가 병목입니다

\(\text{Best} \text{case} O(n \log n), \text{sorted}-\text{입력} \text{worst} \text{case} \Theta(n^{2})\)Best case O(n log n), sorted-input worst case Θ(n²)입니다.

선수 개념과 필수 용어 (Prerequisites and Vocabulary)

트리 용어: 루트(root/Wurzel), 노드(node/Knoten), 간선(edge/Kante), 잎(leaf/Blatt), 부분 트리(subtree/Teilbaum).
깊이(depth/Tiefe)와 높이(height/Höhe), 그리고 빈 트리 높이를 -1로 두는 강의 표기.
이진 트리의 왼쪽·오른쪽 자식 자리와 트리 모양·순회 순서의 차이.
기초 점근 표기: \(O(h)\)O(h)는 트리 높이에 의존하고 전체 순회는 \(\Theta(n)\)Θ(n)이라는 사실.

핵심 학습 항목 (Active Recall With Hints)

1

Tree(Baum), binary tree(binärer Baum), and BST(binärer Suchbaum)를 각각 한 문장으로 정의하세요.

2

Depth(Tiefe)와 height(Höhe)를 root 기준 방향으로 구분해서 말해 보세요. Empty tree height convention은 무엇인가요?

3

BST invariant를 duplicate convention까지 포함해서 말하세요: \(\text{left} \text{subtree} \text{keys} \le v.\text{key} < \text{right} \text{subtree} \text{keys}.\)left subtree keys ≤ v.key < right subtree keys.

4

왜 BST invariant가 immediate child 비교가 아니라 subtree-wide condition인지 반례 하나로 설명하세요.

5

Sheet05 G4 tree에서 Search(70)의 비교를 50, 80, 60 순서로 말하고 방향을 붙이세요.

6

같은 tree에서 preorder, inorder, postorder를 root 위치 기준으로 다시 계산하세요.

7

왜 inorder가 sorted인지 BST invariant로 설명하고, 왜 일반 binary tree에는 해당하지 않는지 말하세요.

8

Delete 15, 70, 80은 각각 어떤 delete case인가요? Replacement가 invariant를 어떻게 보존하나요?

9

Path 124,153,131,148,142,156이 왜 불가능한지 upper bound로 설명하세요.

10

Path 512,203,407,302,248,281,239가 왜 불가능한지 lower bound로 설명하세요.

11

BST search/insert/delete의 general runtime을 \(O(h)\)O(h)로 말하고, h가 \(\Theta(\log n)\)Θ(log n)일 때와 \(\Theta(n)\)Θ(n)일 때를 비교하세요.

12

BST-sort의 best case \(O(n \log n)\)O(n log n)과 \(\text{worst} \text{case} \Theta(n^{2})\)worst case Θ(n²)를 insert height 합으로 설명하세요.

다음 튜터 프롬프트

마지막 생성: 2026-08-03 03:24