I-4 BST 높이 — 완벽한 트리와 한쪽 사슬, 두 극단으로 판정하기
먼저 이 문제의 정체부터
출처부터 구분합니다. 문제 문구는 2025년 시험의 공식 원문이나 공식 해답이 아니라 수험생이 기억을 바탕으로 적은 비공식 복기(Gedächtnisprotokoll)입니다. 아래의 BST 정의와 높이 공식은 현재 강의·공식 연습해답으로 검증하고, 복기 문구의 '항상'과 높이 표기에서 생기는 애매성은 따로 표시합니다.
이 문제는 BST의 값을 검색하는 규칙과 트리의 모양을 구분해야 합니다. BST(binary search tree, binärer Suchbaum)는 각 노드에서 왼쪽 부분트리의 키≤현재 키≤오른쪽 부분트리의 키라는 순서 규칙만 강제할 뿐, 자동으로 균형을 맞추지는 않습니다. 여기서 노드(node)는 값을 담은 점, 키(key)는 비교에 쓰는 값, 부분트리(subtree)는 어떤 노드 아래를 다시 하나의 트리로 본 것입니다. 그래서 같은 n개 키라도 균형 잡힐 수도, 한쪽으로 길게 늘어질 수도 있습니다.
높이(Höhe)는 교재마다 루트에서 가장 깊은 leaf까지의 간선 수 또는 경로상의 노드 수로 정의합니다. n개 노드의 사슬은 간선 기준 n-1, 노드 기준 n입니다. 복기 선택지의 'worst case gleich n'은 정확한 off-by-one보다 최악 높이가 선형일 수 있다는 강의 의도를 묻는 것으로 판정합니다.
선택지의 immer(항상), weniger als(엄밀히 작다), gleich(정확히 같다)를 표시하세요. 트리 명제는 작은 반례 하나로 쉽게 깰 수 있습니다. root 2와 children 1,3인 3노드 perfect BST가 특히 유용합니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · BST가 보장하는 것
BST의 각 노드 x에서 왼쪽 subtree의 키는 x보다 작거나 같고 오른쪽 subtree의 키는 x보다 크거나 같습니다. 이 규칙은 search 방향을 결정하지만 높이를 제한하지 않습니다.
AVL tree나 red-black tree처럼 별도 균형 규칙이 있어야 logarithmic height가 보장됩니다. plain BST는 입력 순서가 나쁘면 선형 높이가 됩니다.
수식으로 정확히 쓰기
핵심 규칙\forall x\in L:\;key(x)\le key(r),\qquad \forall y\in R:\;key(r)\le key(y)
핵심 규칙\text{plain BST에는 balance invariant가 없다}
이 절에서 꼭 기억할 것
- 순서 속성≠균형 속성
- BST라고 항상 \(\Theta(\log n)\)
Θ(log n)search가 아니다.
개념 2 · 깊이와 높이
노드의 깊이(Tiefe)는 루트에서 그 노드까지 얼마나 내려왔는지 나타냅니다. 루트 깊이를 0으로 두면 depth d의 레벨까지 d개의 간선을 지납니다.
트리 높이는 최대 깊이로 정의할 수 있습니다. 어떤 자료는 노드 수로 세어 한 칸 차이가 나므로 정확한 n과 n-1보다 \(\Theta(n)\)Θ(n), \(\Theta(\log n)\)Θ(log n) 같은 성장급을 먼저 구분해야 합니다.
수식으로 정확히 쓰기
핵심 규칙\(h_{\text{edge}}(\text{루트만 있는 트리})=0,\)h(edge)(\text{루트만 있는 트리})=0,\qquad \(h_{\text{node}}(\text{루트만 있는 트리})=1\)h(node)(\text{루트만 있는 트리})=1
핵심 규칙\(h_{\text{edge}}(\text{노드 }n\text{개의 사슬})=n-1,\)h(edge)(\text{노드 }n\text{개의 사슬})=n-1,\\(\text{qquad} h_{\text{node}}=n\)qquad h(node)=n
이 절에서 꼭 기억할 것
- 높이 계산 규약(convention)을 명시한다.
- 1 차이(off-by-one)가 점근적 성장급을 바꾸지 않는다.
개념 3 · 한 레벨의 최대 노드 수
이진 트리에서 각 노드는 자식을 최대 두 개 가집니다. 루트 depth 0에는 최대 \(1=2^{0}\)1=2⁰개, depth 1에는 최대 \(2=2^{1}\)2=2¹개, depth d에는 최대 \(2^{d}\)2^d개가 있을 수 있습니다. depth(깊이)는 루트에서 그 노드까지 지난 간선 수입니다.
가장 작은 시각 예시는 level 0:{2}, level 1:{1,3}, edges:{2-1,2-3}입니다. level 1에는 정확히 \(2=2^{1}\)2=2¹개가 있으므로 '항상 \(2^{d}\)2^d보다 적다(<)'는 깨집니다. 올바른 문장은 'at most \(2^{d}\)2^d', 즉 ≤\(2^{d}\)2^d입니다.
수식으로 정확히 쓰기
N_d\le 2^{d}\text{perfect level에서는 }N_d=2^{d}이 절에서 꼭 기억할 것
- \(\text{weniger} \text{als}(<)\)
weniger als(<)와 hö\(\text{chstens}(\le )\)chstens(≤)를 구분한다. - 경계값 equality가 반례가 된다.
개념 4 · 최악의 BST 높이
시험 크기보다 먼저 \(n=4\)n=4를 실행해 봅니다. 1을 root로 두고 2를 넣으면 edge (1,2), 3을 넣으면 edge (2,3), 4를 넣으면 edge (3,4)가 생깁니다. 시각 상태는 level 0:{1}, level 1:{2}, level 2:{3}, level 3:{4}이며 모든 간선이 오른쪽으로 이어집니다.
일반적으로 키를 1,2,3,...,n 순서로 삽입하면 새 키는 오른쪽 끝에 붙습니다. 간선 기준 높이는 n-1, 노드 기준은 n이므로 worst-case height는 \(\Theta(n)\)Θ(n)입니다. search, insert, delete도 이 경로를 따라가면 최악 \(\Theta(n)\)Θ(n)이 됩니다.
수식으로 정확히 쓰기
핵심 규칙1<2<\cdots<n\quad\Longrightarrow\quad1\rightarrow2\rightarrow\cdots\rightarrow n
h(worst)=n-1=\Θ(n)\;\text{(간선 기준)}이 절에서 꼭 기억할 것
- 일반 BST는 자동 회전하지 않는다.
- 최악의 경우를 보이려면 가능한 입력 하나면 충분하다.
개념 5 · 최선의 BST 높이
가장 낮은 높이는 노드가 가능한 한 균등하게 양쪽에 채워진 complete/balanced 모양에서 나옵니다. 높이 h까지 담을 수 있는 최대 노드 수는 \(1+2+...+2^{h}=2^{h+1}-1\)1+2+...+2^h=2^(h+1)-1입니다.
이를 뒤집으면 h는 대략 \(\log_{2}n\)log₂n입니다. 하지만 정확한 식에는 floor/ceil과 convention이 붙습니다. 따라서 'best case height가 정확히 \(\log_{10}n\)log₁₀n'이라는 문장은 일반적으로 틀리고, 올바른 점근 표현은 \(\Theta(\log n)\)Θ(log n)입니다.
수식으로 정확히 쓰기
n\le1+2+\cdots+2^{h}=2^{h+1}-1h(best)=\Θ(\log₂ n)=\Θ(\log n)이 절에서 꼭 기억할 것
- 로그 밑은 Θ에서는 상수배 차이
- exact equality에서는 밑·반올림·높이 convention이 중요
개념 6 · leaf 문장의 애매성
'Blaetter auf jeder Ebene auftreten'를 '모든 레벨에 leaf가 반드시 있다'로 읽으면 거짓입니다. 3노드 perfect BST에는 depth 1에만 leaves가 있고 root level에는 leaf가 없습니다.
반대로 'leaf가 여러 가능한 레벨 중 어느 곳에서도 나타날 수 있다'는 존재 가능성으로 읽으면 불균형 BST를 만들어 참처럼 들릴 수 있습니다. 복기 문언은 공식 원문이 아니므로 Study Hub에서는 문언 그대로의 엄격 판정과 강의 의도를 구분해 표시해야 합니다.
수식으로 정확히 쓰기
핵심 규칙\forall d\;\exists\text{ leaf at depth }d\quad\not\equiv\quad\exists d\;\exists\text{ leaf at depth }d
이 절에서 꼭 기억할 것
- 복기 문구의 quantifier를 확인한다.
- 애매해도 다른 명확한 정답 C의 근거는 유지된다.
1. 시험장에서 따라 할 풀이 순서
일반 BST는 순서 조건만 있고 균형 조건은 없다.
\(\text{chain} \text{height}=n-1 \text{or} n\)chain height=n-1 or n
2 / \ 1 3
문언 그대로 모든 경우를 뜻하면 \(A=\)A=거짓
plain BST인지 확인한다
AVL/red-black 같은 balance 조건이 없으므로 선형 높이가 가능합니다.
핵심 규칙일반 BST는 순서 조건만 있고 균형 조건은 없다.
높이 convention을 메모한다
간선 기준 n-1, 노드 기준 n이지만 둘 다 \(\Theta(n)\)
Θ(n)입니다.\[\text{chain} \text{height}=n-1 \text{or} n\]chain height=n-1 or n작은 perfect BST를 그린다
root 2, children 1과 3을 그려 leaf/level/strict bound 반례로 씁니다.
\[2 / \ 1 3\]2 / \ 1 3A를 양화사로 읽는다
모든 레벨에 leaf가 반드시 있다는 뜻이면 반례가 있어 거짓이며, 복기 문구의 가능성 해석은 별도 애매성으로 기록합니다.
핵심 규칙문언 그대로 모든 경우를 뜻하면 \(A=\)
A=거짓B의 strict inequality를 깬다
depth 1에 정확히 \(2=2^{1}\)
2=2¹개 노드가 가능한 BST가 있으므로 '<\(2^{d}\)2^dalways'는 거짓입니다.correct bound
\[\le 2^{d}\]≤2^dC에 정렬 순서 삽입을 적용한다
1,2,...,n을 넣으면 사슬이 되어 높이가 선형입니다. 시험 의도상 참입니다.
\[C=참, h=\Theta(n)\]C=참, h=Θ(n)D의 정확한 로그 표현을 검사한다
최선 높이는 \(\Theta(\log_{2}n)\)
Θ(log₂n)이지만 정확히 \(\log_{10}n\)log₁₀n은 아닙니다. \(n=7\)n=7이면 간선 기준 높이 2인데 \(\log_{10}7\)log₁₀7≈0.845입니다.\[D=거짓\]D=거짓정답과 단서를 함께 쓴다
C를 선택하고 높이 계산 규약에 따라 n 또는 n-1이며 핵심은 선형인 최악 높이라고 적습니다.
핵심 규칙정답 C (의도: 최악 높이는 선형)
2. 이 문제를 실제로 끝까지 풀기
작은 예부터 확인합니다. BST 2에 왼쪽 child 1, 오른쪽 child 3을 연결하면 \(\text{level} 0=\{2\}, \text{level} 1=\{1,3\}, \text{edges}=\{2-1,2-3\}\)level 0={2}, level 1={1,3}, edges={2-1,2-3}입니다. 이 한 그림에서 level 1의 노드 수가 \(2^{1}\)2¹과 같고, leaf는 level 1에만 있다는 두 사실을 읽을 수 있습니다.
먼저 plain BST에는 균형 조건이 없다는 사실을 고정합니다. 1,2,3,...,n을 순서대로 삽입하면 각 새 키가 오른쪽 끝에 붙어 n개 노드의 사슬이 됩니다. 높이는 간선 기준 n-1, 노드 기준 n이며 \(\Theta(n)\)Θ(n)입니다. 따라서 C는 강의 의도상 참입니다.
B는 depth d에 항상 \(2^{d}\)2^d보다 적은 노드가 있다고 주장합니다. 하지만 root 2에 children 1,3이 있는 BST는 depth 1에 정확히 \(2=2^{1}\)2=2¹개 노드를 가집니다. 올바른 상한은 <가 아니라 ≤이므로 B는 거짓입니다.
D는 best-case height를 정확히 \(\log_{10}n\)log₁₀n이라고 합니다. 균형 잡힌 이진 트리의 높이가 \(\Theta(\log n)\)Θ(log n)이라는 점근 명제는 맞지만, exact height는 밑 2의 수용량 계산과 floor/ceil, 그리고 간선/노드 convention에 좌우됩니다. \(n=7 \text{perfect} \text{BST}\)n=7 perfect BST의 간선 높이는 2라서 \(\log_{10}7\)log₁₀7과 같지 않습니다.
A는 복기 문구가 애매합니다. '모든 레벨에 leaf가 있다'는 필수 성질로 읽으면 perfect BST가 반례입니다. 'leaf가 임의 깊이에 나타날 수 있다'는 가능성으로 읽으면 참일 수 있습니다. 정확히 하나 정답이라는 구조와 강의의 핵심 명제를 고려하면 C를 의도 정답으로 두되 A의 문언 애매성을 숨기지 않아야 합니다.
따라서 시험 풀이에서는 C를 고르고 'sorted insertion gives a chain; worst height is linear'라고 근거를 붙입니다. 동시에 높이를 n이라고 쓰는지 n-1이라고 쓰는지는 정의 convention 때문이라는 점을 알고 있어야 합니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A거짓
문언을 '모든 depth level에 반드시 leaf가 존재한다'로 읽으면 거짓입니다. perfect BST는 leaves가 마지막 level에만 있습니다. 다만 '어떤 depth에서도 leaf가 나타날 수 있다'는 가능성 해석은 참일 수 있어 복기 문구의 애매성을 별도로 기록합니다.
빠른 확인법: 3노드 perfect BST에서 root level에는 leaf가 없습니다.
-
B거짓
depth d의 최대 노드 수는 \(2^{d}\)
2^d이며 equality가 가능합니다. 'weniger als'라는 strict bound가 잘못되었습니다.빠른 확인법: depth 1에 children 두 개면 \(2=2^{1}\)
2=2¹입니다. -
C참 — 정답 후보
정렬된 순서로 삽입하면 한쪽 사슬이 생겨 worst height가 \(\Theta(n)\)
Θ(n)입니다. 간선 기준 정확히 n-1이어도 선택지의 의도는 linear worst case입니다.빠른 확인법: \(1\to 2\to 3\to ...\to n\)
1→2→3→...→n사슬을 그립니다. -
D거짓
best height는 \(\Theta(\log n)\)
Θ(log n)이지만 정확히 \(\log_{10}n\)log₁₀n은 아닙니다. exact equality에는 밑 2, 반올림, height convention이 필요합니다.빠른 확인법: \(n=7\)
n=7이면 perfect BST edge-height=2≠\(\log_{10}7\)log₁₀7입니다.
4. 초보자가 가장 자주 틀리는 이유
- BST라는 이유만으로 항상 balanced라고 생각한다.
- worst height를 무조건 n 또는 n-1 중 하나로만 외워 convention 차이를 오류로 본다.
- depth d의 최대 \(2^{d}\)
2^d를 엄밀히 작은 <\(2^{d}\)2^d로 잘못 기억한다. - best-case \(\Theta(\log n)\)
Θ(log n)을 \(\text{exact} \log_{10}n\)exact log₁₀n과 동일시한다. - 로그 밑이 Θ에는 중요하지 않다는 사실을 exact equality에도 잘못 적용한다.
- leaf와 internal node의 정의를 혼동한다.
- 복기 문구의 quantifier 애매성을 숨기고 단정한다.
5. 시험 답안 템플릿
Plain BST는 balance를 보장하지 않는다. 정렬된 키 1,2,...,n을 삽입하면 한쪽 사슬이 되어 높이는 edge convention에서 n-1, node convention에서 n, 즉 \(\Theta(n)\)Θ(n)이다. 따라서 의도 정답은 C이다. B의 올바른 bound는 depth d에서 ≤\(2^{d}\)2^d이고, D는 \(\text{exact} \log_{10}n\)exact log₁₀n이 아니라 best-case \(\Theta(\log n)\)Θ(log n)이다. A는 복기 문언의 quantifier가 애매하나 universal reading에서는 거짓이다.
6. 스스로 이해했는지 확인
plain BST가 자동으로 균형을 맞추는가?
정답: 힌트: BST 정의에 높이 조건이 있는지 찾아보세요. 정답: 아닙니다. 별도 balance invariant가 없습니다.
정렬된 n개 키 삽입 후 높이는?
정답: 힌트: 1,2,3,4를 직접 넣어 오른쪽 사슬을 그리세요. 정답: 간선 기준 n-1, 노드 기준 n이며 \(\Theta(n)\)Θ(n)입니다.
depth d의 최대 노드 수는?
정답: 힌트: 한 레벨마다 최대 두 배가 됩니다. 정답: \(2^{d}\)2^d개이며 equality가 가능합니다.
best-case height의 안전한 점근 표현은?
정답: 힌트: 높이 h까지 최대 \(2^{h+1}-1\)2^{h+1}-1개를 담습니다. 정답: \(\Theta(\log n)\)Θ(log n)입니다.
\(n=7 \text{perfect} \text{BST}\)n=7 perfect BST의 edge-height는?
정답: 힌트: level 0,1,2의 수용량 1+2+4를 더하세요. 정답: 2입니다.
I-4의 의도 정답은?
정답: 힌트: 정렬 삽입으로 선형 높이를 만들 수 있는 선택지를 찾으세요. 정답: C, worst-case linear height입니다.
근거 자료
AuD Gedächtnisprotokoll SoSe 2025.md· Multiple Choice I.4
복기된 문제 문언과 선택지; 공식 답안지가 아님Vorlesung\03BasicDataStructures.pdf· p. 81
BST best/worst height와 sorted insertion 사슬Übung\AuD26_Sheet05-GrpSol.pdf· pp. 5-7 and p. 13
BST 구조·높이·레벨 공식 풀이