이진 탐색 트리(BST)의 높이와 순회

BST(이진 탐색 트리, binary search tree, binärer Suchbaum)는 모든 노드 v에서 '왼쪽 부분 트리 <= \(v.\text{key} \le \)v.key ≤또는 < 오른쪽 부분 트리' 조건을 부분 트리 전체에 대해 지키는 이진트리다. 탐색·삽입·삭제는 한 경로만 내려가므로 \(O(h)\)O(h)이고, h가 균형 잡혀 있으면 \(O(\log n)\)O(log n), 퇴화한 사슬이면 \(O(n)\)O(n)이다. 순회(traversal)는 같은 트리를 읽는 순서다. 전위는 루트가 처음, 중위는 루트가 가운데, 후위는 루트가 마지막이며, BST에서는 중위 순회만 오름차순 출력을 보장한다.

깊이 d인 층에는 노드가 최대 \(2^{d}\)2^d개 있다. 일반 BST 연산은 \(O(h)\)O(h), 가장 균형 잡힌 높이는 \(\Theta(\log n)\)Θ(log n), 퇴화한 최악 높이는 \(\Theta(n)\)Θ(n)이다. 강의의 간선 기준 규약에서는 \(h = n - 1\)h = n - 1이다.

`immer`, `jede`, 정확한 수를 뜻하는 `gleich`, 최선·최악 경우(best/worst case), 순회 이름을 보면 먼저 작은 반례와 규약을 확인한다.

• I-4
• I-5

섹션 I에서는 네 문장 가운데 정확히 하나(exactly one)가 옳다고 명시한다.

정답 위치를 외우는 대신 각 선택지를 BST 불변식, 층별 노드 수 상한, 높이 규약, 순회 순서로 바꾸어 독립적으로 판정한다.

기억 복원 자료(Gedächtnisprotokoll)는 재구성한 시험 문구이며 공식 정답지가 아니다. 아래 판정은 2026년 여름학기 강의와 Sheet05 자료로 대조했다.

I-4 선택지 C에 대해 강의는 간선 기준 최악 높이를 \(h = n - 1\)h = n - 1로 제시하지만, Sheet05 그룹 풀이에서는 정렬 입력의 높이를 비형식적으로 n이라 표현한다. 객관식의 의도는 최악 높이가 선형이라는 것이며, 정확한 문구 'gleich n'에는 1 차이(off-by-one)와 강의 규약의 모호성이 있다.

BST는 정렬된 전화번호부의 절반을 계속 버리며 찾는 것과 비슷하다. 찾는 값이 현재 노드보다 작으면 오른쪽 부분 트리 전체를 버리고, 크면 왼쪽 부분 트리 전체를 버린다. 따라서 비용은 전체 노드 수 n을 무조건 다 보는 것이 아니라 내려간 경로 길이, 즉 높이(height) h에 묶인다.

이진 탐색 트리(Binary search tree, BST, binärer Suchbaum)는 모든 노드 z에서 왼쪽 부분 트리(Teilbaum)의 모든 x가 \(x.\text{key} \le z.\text{key}\)x.key ≤ z.key이고 오른쪽 부분 트리의 모든 y가 \(y.\text{key} \ge z.\text{key}\)y.key ≥ z.key인 이진트리다. 중위 순회(Inorder-Traversierung)는 왼쪽-루트-오른쪽 순서로 읽으며, BST 불변식 덕분에 키가 오름차순으로 나온다.

• 트리 용어: 루트(Wurzel/root), 리프(Blatt/leaf), 노드(Knoten/node), 부분 트리(Teilbaum/subtree)
• 깊이(Tiefe/depth)는 루트에서 내려간 거리이며 Sheet05에서는 0부터 시작한다.
• 높이(Höhe/height)는 루트에서 가장 깊은 리프까지의 길이이며, 강의 p.81은 간선 기준 최악의 경우 \(h = n - 1\)h = n - 1을 사용한다.
• 전위·중위·후위 순회(preorder, inorder, postorder)는 트리를 바꾸는 연산이 아니라 방문 순서다.

핵심 불변식은 바로 아래 자식 하나만 비교하는 것이 아니라 부분 트리 전체에 적용되는 순서 조건이다. 깊이 d인 이진트리 층에는 최대 \(2^{d}\)2^d개의 노드가 있으므로 `weniger als \(2^{d}\)2^d`는 엄격 부등식(strict inequality)을 사용했다는 점에서 틀린다.

일반 BST의 탐색·삽입·삭제는 \(O(h)\)O(h)이다. 완전하거나 균형 잡힌 모양의 BST는 \(h = \Theta(\log n)\)h = Θ(log n)이므로 연산도 \(O(\log n)\)O(log n)이다. 정렬된 삽입 순서는 \(h = \Theta(n)\)h = Θ(n)인 퇴화 선형 목록을 만들 수 있으므로 연산이 \(O(n)\)O(n)이 될 수 있다. 모든 노드 순회는 \(\Theta(n)\)Θ(n) 시간이며, 재귀 구현에서는 \(O(h)\)O(h)의 재귀 스택을 사용한다.

노드 하나인 트리는 루트 깊이가 0이고, 간선 기준 높이 규약에서는 높이도 0이다. 한 트리의 리프가 서로 다른 깊이에 있을 수 있지만 `모든 층에 리프가 있다(leaves on every level)`는 문구는 모호하다. 층 0이 리프인 경우는 노드가 하나뿐일 때뿐이기 때문이다. 중위 순회의 정렬성은 트리가 BST라는 전제를 필요로 하며, 임의의 이진트리는 중위 순회가 정렬된다고 보장하지 않는다.

• genau eine
• immer
• weniger als
• gleich n
• best case
• worst case
• aufsteigend sortiert
• Preorder
• Inorder
• Postorder
• Höhe versus Tiefe

BST는 부분 트리 전체의 순서 불변식을 지킨다. BST의 중위 순회(왼쪽-루트-오른쪽)는 정렬되지만, 전위·후위 순회는 일반적으로 정렬되지 않는다.

깊이 d에는 노드가 최대 \(2^{d}\)2^d개 있다. 탐색·삽입·삭제는 \(O(h)\)O(h)이다. 균형 높이는 \(\Theta(\log n)\)Θ(log n), 퇴화 높이는 \(\Theta(n)\)Θ(n)이며 강의의 정확한 최악 높이는 \(h = n - 1\)h = n - 1이다.

노드 하나와 완전 트리 예제로 리프·층 문구를 검사하고, 오른쪽 사슬로 최악 높이를 검사한다. 루트 2와 자식 1·3으로 순회 함정을 잡는다.

모든 객관식 보기에서 수량 표현을 해석하고 규약을 확인한 뒤 가장 작은 트리를 그린다. 해당하면 \(O(h)\)O(h) 또는 중위 순회를 근거로 든다.