6. Fortgeschrittene Datenstrukturen (12 Punkte)

6.3 · 이진 탐색 트리(BST)가 AVL인지 판정하는 재귀 알고리즘

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

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

자료의 성격과 정확성 경계

문제 문언·배점·후보 그림은 비공식 SoSe 2025 복기 lines 270-295와 연결 이미지에서 가져왔습니다. 정의와 수치 convention은 Lecture 04 pp.3-5, 45-46, p.57, p.114, pp.122-126으로 교차 확인했습니다. Sheet06-Sol은 RB/AVL, Sheet08-Sol은 B-Tree 삽입을 뒷받침하며, 일반 교재의 NIL-inclusive black count를 강의 SH 수치와 섞지 않습니다.

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

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

기호·용어뜻작은 예
항목 (R / rectangle)복기 그림에서 red node를 뜻하는 사각형입니다. 기호를 다른 색 의미로 재정의하지 않습니다.Tree 1의 root 27은 rectangle이므로 red입니다.
항목 (B / circle)복기 그림에서 black node를 뜻하는 원입니다. CSS 색만이 아니라 shape와 R/B label을 함께 읽습니다.Tree 3의 root 13은 black circle입니다.
\(\text{SH}(\text{nil})=0\)SH(nil)=0NIL sentinel은 black으로 모델링하지만 강의 Schwarzhöhe 수치에서는 nil 자체에 1을 더하지 않습니다.Tree 3의 root-to-terminal black 수는 3이지 4가 아닙니다.
\(t=2\)t=2B-Tree의 Grad 또는 minimum degree이며 non-root node의 key 수는 t-1부터 2t-1입니다.\(t=2\)t=2이면 한 node는 1~3 keys를 가집니다.
\(B(v)=\text{hR}-\text{hL}\)B(v)=hR-hL강의의 AVL balance factor로 오른쪽 subtree 높이에서 왼쪽 높이를 뺍니다.\(B(v)=-2\)B(v)=-2이면 이 convention에서는 left-heavy입니다.
실패AVL 검사 중 이미 균형 위반을 찾았다는 별도 반환값이며 유효한 높이 -1과 혼동하지 않습니다.empty tree는 height -1, invalid subtree는 FAIL입니다.

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

AVL Tree는 모든 node에서 왼쪽과 오른쪽 subtree 높이 차이가 최대 1인 BST입니다. 문제는 입력이 이미 BST라고 했으므로 핵심은 모든 node의 balance condition 검사입니다.

초보자 구현은 node마다 height를 새로 계산해 \(O(n^{2})\)O(n²)이 되기 쉽습니다. 더 좋은 방식은 postorder로 한 번만 순회하면서 각 subtree의 높이와 실패 여부를 parent에게 동시에 돌려주는 것입니다.

강의 \(\text{convention} \text{height}(\text{empty})=-1, \text{leaf}=0, B=\text{hR}-\text{hL}\)convention height(empty)=-1, leaf=0, B=hR-hL을 사용합니다. 유효한 높이 -1과 충돌하지 않도록 invalid는 숫자가 아닌 FAIL sentinel로 반환합니다.

필요한 개념을 깊게 배우기

개념 1

0단계 · AVL 정의와 강의 convention

모든 node v에서 \(B(v)=\text{height}(v.\text{right})-\text{height}(v.\text{left})\)B(v)=height(v.right)-height(v.left)이고 \(B(v)\in \{-1,0,+1\}\)B(v)∈{-1,0,+1}이어야 합니다. root만 검사해서는 안 되고 모든 subtree가 자체적으로 AVL이어야 합니다.

강의는 \(\text{empty} \text{tree} \text{height}=-1, \text{leaf} \text{height}=0\)empty tree height=-1, leaf height=0을 사용합니다. invalid는 유효 height -1과 다른 FAIL 값으로 둡니다.

수식으로 정확히 쓰기

\[H(\text{nil})=-1\]H(nil)=-1
\[B(v)=\text{hR}-\text{hL}\]B(v)=hR-hL
\[|B(v)|\le 1\]|B(v)|≤1
개념 2

1단계 · postorder

현재 node의 높이를 알려면 두 child 높이가 먼저 필요하므로 left, right, node 순서의 postorder가 자연스럽습니다.

child가 invalid라고 보고하면 parent는 추가 계산 없이 invalid를 위로 전달합니다.

수식으로 정확히 쓰기

\[\text{height}(v)=1+\max(\text{hL},\text{hR})\]height(v)=1+max(hL,hR)
개념 3

2단계 · FAIL sentinel

\(\text{heightOrFail}(\text{nil})=-1\)heightOrFail(nil)=-1입니다. left 또는 right 결과가 FAIL이면 즉시 FAIL을 위로 전달합니다. 둘 다 정상이어도 \(\text{abs}(\text{right}-\text{left})>1\)abs(right-left)>1이면 FAIL입니다.

그 외에는 실제 course height를 반환합니다. 최종 root 결과가 FAIL이 아니면 AVL입니다.

수식으로 정확히 쓰기

핵심 규칙FAIL≠-1

\[\text{result}\ne \text{FAIL} \Rightarrow \text{AVL}\]result!=FAIL ⇒ AVL
개념 4

3단계 · complexity와 흔한 \(O(n^{2})\)O(n²)

각 node를 최대 한 번 방문하고 constant work만 하므로 \(O(n)\)O(n), valid tree 등 worst case에는 모두 방문해 \(\Theta(n)\)Θ(n)입니다. recursion stack은 \(O(h)\)O(h)입니다.

isBalanced(v) 안에서 별도 height(v.left), height(v.right)를 매 node마다 다시 호출하면 사슬 tree에서 같은 node를 반복 방문해 \(\Theta(n^{2})\)Θ(n²)이 될 수 있습니다.

수식으로 정확히 쓰기

\[\text{worst}-\text{case} \Theta(n)\]worst-case Θ(n)

핵심 규칙stack \(O(h)\)O(h)

\[\text{naive} \Theta(n^{2}), \text{one}-\text{pass} \Theta(n)\]naive Θ(n²), one-pass Θ(n)
초보자용 연결 강의

이 소문제를 왜 배우나

AVL 조건은 root 하나가 아니라 모든 node의 두 subtree height에 걸린 전역 조건입니다. 높이를 계산하는 재귀와 균형 판정을 한 번의 postorder에 합치면 같은 node를 반복 방문하지 않고 정확한 \(O(n)\)O(n) 검사를 만들 수 있습니다.

풀이 전에 꼭 알아야 할 말

height와 balance factor

height는 현재 node에서 가장 깊은 leaf까지 edge 수이며 empty tree는 -1, leaf는0입니다. 강의 balance factor는 right height-left height입니다.

아주 작은 예: left height1, right height-1이면 \(B=-2\)B=-2라 left-heavy invalid입니다.

후위 순회 재귀 (postorder recursion)

parent 값을 계산하려면 두 child 결과가 먼저 필요하므로 left, right, node 순서로 호출이 돌아옵니다. 각 호출은 자기 subtree 요약 하나를 parent에게 반환합니다.

아주 작은 예: leaf2가 height0을 반환한 뒤 parent5가 height1을 계산합니다.

핵심 학습 항목 (FAIL sentinel)

유효한 course height에는 -1도 포함되므로 invalid를 -1로 표현하면 empty tree와 충돌합니다. 숫자가 아닌 FAIL을 별도 결과로 사용합니다.

아주 작은 예: nil returns -1, unbalanced node10 returns FAIL입니다.

수식이 포함된 학습 항목: recursion stack \(O(h)\)O(h)

동시에 활성화된 호출 수는 root에서 현재 node까지 path 길이에 비례합니다. 입력이 invalid한 skewed BST면 h가 n에 가까울 수도 있습니다.

아주 작은 예: 한쪽 사슬 tree에서는 stack이 \(O(n)\)O(n)까지 커질 수 있습니다.

부하 보고서를 한 번만 받는 조직

각 직원은 왼쪽·오른쪽 팀의 보고를 받은 뒤 자기 조직 높이를 숫자로 올립니다. 어느 팀에서 사고가 나면 숫자 대신 FAIL 딱지를 올리고, 상사는 전체 조직에 다시 전화하지 않고 그 딱지를 그대로 전달합니다.

두 부하의 보고를 먼저 받음
↔
postorder child-first call
정상 조직 규모 요약 숫자
↔
height return
사고 딱지를 상위 조직으로 즉시 전달
↔
FAIL propagation
각 직원에게 한 번만 보고 요청
↔
one visit per node

비유의 한계: 실제 조직 높이는 직원 수와 다르지만 tree height는 가장 긴 edge path입니다. 또한 조기 FAIL은 일부 node를 방문하지 않을 수 있어 \(O(n)\)O(n)은 upper bound이고 worst-case에 \(\Theta(n)\)Θ(n)입니다.

\(2\to 5\to 10\)2→5→10으로 올라오는 postorder return

node 2: return 0nil children -1,-1에서 \(B=0\)B=0이고 leaf height0입니다.
node 5: return 1\(\text{hL}=0,\text{hR}=-1,B=-1\)hL=0,hR=-1,B=-1이 허용되어 height1입니다.
node 10: FAIL\(\text{hL}=1,\text{hR}=-1,B=-2\)hL=1,hR=-1,B=-2라 AVL condition을 위반합니다.

connector는 child에서 parent 방향의 반환을 나타내며 먼저 그립니다. node box에는 hL, hR, B, return을 짧게 표시하고 10의 FAIL을 risk color로 강조합니다.

먼저 작은 예제로 연습 · root10과 leaves5·15인 valid AVL

root10의 left leaf5와 right leaf15가 있는 BST를 course height convention으로 검사합니다.

두 leaf 계산

각 leaf의 children은 nil height-1이라 \(B=0,\)B=0,반환 height는0입니다.

\(\text{return}(5)=0, \text{return}(15)=0\)return(5)=0, return(15)=0
root balance 계산

\(\text{hR}0-\text{hL}0=0\)hR0-hL0=0은 허용 집합 {-1,0,1}에 있습니다.

\(B(10)=0\)B(10)=0
root height와 verdict

\(1+\max(0,0)=1\)1+max(0,0)=1을 반환하며 FAIL이 아니므로 전체 tree는 AVL입니다.

\(\text{height}=1, \text{isAVL}=\text{true}\)height=1, isAVL=true

작은 예제의 결론: child height와 validity를 한 결과로 올리면 parent에서 균형과 실제 height를 동시에 정확히 결정할 수 있습니다.

이제 실제 시험 문제에 연결

왜 입력 BST order를 다시 검사하지 않는가?

문언이 이미 binärer Suchbaum 인스턴스라고 보장하므로 이 알고리즘의 과제는 모든 node의 AVL balance 검사입니다.

base case는 무엇을 반환하는가?

empty subtree nil은 강의 convention의 실제 height -1을 반환하며 이것은 정상 결과입니다.

node2와 node5는 무엇을 반환하는가?

node2는 \(\text{hL}=\text{hR}=-1\)hL=hR=-1이라0, node5는 \(\text{hL}0,\text{hR}-1,B=-1\)hL0,hR-1,B=-1이라 height1을 반환합니다.

node10에서 왜 FAIL인가?

hL1,hR-1이므로 \(B(10)=-2\)B(10)=-2이고 절댓값2가 1을 넘습니다. 따라서 숫자 height 대신 FAIL을 반환합니다.

최종 호출과 runtime은 어떻게 쓰는가?

\(\text{answer}=\text{isAVL}(T)\)answer=isAVL(T)를 명시합니다. 각 node를 최대 한 번 방문해 \(O(n)\)O(n), valid tree 등 worst-case \(\Theta(n)\)Θ(n), stack \(O(h)\)O(h)입니다.

답이 맞는지 스스로 검산

  • \(\text{trace}_{\text{rows}}\)trace(rows)의 모든 balance가 hR-hL과 일치하고 return이 course height 또는 FAIL인지 재계산합니다.
  • pseudocode에서 \(\text{nil}=-1\)nil=-1과 \(\text{invalid}=\text{FAIL}\)invalid=FAIL이 서로 다른 token이며 isAVL(T)가 FAIL과 비교하는지 확인합니다.
  • helper 안에서 별도 height 재귀를 다시 호출하지 않아 각 node가 최대 한 번 방문되는지 call structure를 확인합니다.

30초 자가점검

invalid sentinel로 -1을 쓰면 왜 강의 convention과 충돌하는가?

힌트: empty subtree의 정상 height를 확인합니다.

정답: 강의에서 empty tree의 유효한 height가 이미 -1이므로 invalid와 구분할 수 없습니다. 별도 FAIL이 필요합니다.

root balance만 0이면 전체 tree가 AVL인가?

힌트: AVL definition이 어느 node에 적용되는지 봅니다.

정답: 아닙니다. 모든 descendant node의 subtree도 AVL이어야 하므로 postorder로 각 node를 검사하고 failure를 전파해야 합니다.

마지막에 쓰는 시험 답안 틀

Postorder helper가 course height 또는 FAIL을 반환한다. \(\text{nil}\to -1, \text{child} \text{FAIL}\to \text{FAIL}, |\text{hR}-\text{hL}|>1\to \text{FAIL},\)nil→-1, child FAIL→FAIL, |hR-hL|>1→FAIL,아니면 1+max. isAVL(T)는 \(\text{helper}(T)\ne \text{FAIL}.\)helper(T)!=FAIL.각 node를 최대 한 번 방문하므로 \(O(n)\)O(n), worst-case \(\Theta(n)\)Θ(n), stack \(O(h)\)O(h).

자주 하는 실수

근거와 정확성 범위

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

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