방송대 자료구조 11강: 이진 탐색 트리와 균형 전략
같은 키를 저장한 이진 탐색 트리도 한쪽으로 길게 늘어서면 탐색 경로가 길어진다. 그렇다면 정렬 규칙을 지키면서 자주 쓰는 노드를 올리거나, 높이 또는 무게의 불균형을 제한하려면 무엇을 확인해야 할까? 이 글은 기본 탐색·삽입·삭제부터 Splay·AVL·BB 트리의 서로 다른 재구성 기준까지 하나의 비교 틀로 연결한다.
같은 키 집합도 트리 모양에 따라 탐색 비용이 달라진다
키 18, 27, 39, 52를 18부터 차례로 삽입하면 모든 새 키가 오른쪽으로 이어져 네 노드를 찾는 데 긴 경로를 따라야 한다. 반면 39를 루트 근처에 두고 18·27을 왼쪽, 52를 오른쪽에 배치하면 같은 키를 더 짧은 경로로 찾을 수 있다. 이 차이는 키의 종류가 아니라 트리의 구조에서 생긴다.
이진 탐색 트리는 어떤 노드의 왼쪽 서브트리에는 더 작은 키, 오른쪽 서브트리에는 더 큰 키가 오도록 제한한다. 이 순서 규칙은 탐색 방향을 결정하지만 트리의 높이까지 자동으로 낮춰 주지는 않는다. Splay·AVL·BB 트리는 이 공통 규칙 위에서 서로 다른 방식으로 좋지 않은 구조를 줄인다.
비교의 출발점: 네 트리 모두 키의 대소 관계로 왼쪽과 오른쪽을 나눈다. 차이는 “어떤 노드를 어디까지 움직이며, 무엇을 균형의 기준으로 삼는가”에 있다.
이진 탐색 트리의 불변 조건이 모든 연산의 방향을 정한다
노드 v의 키를 k라고 하면 왼쪽 서브트리의 모든 키는 k보다 작고, 오른쪽 서브트리의 모든 키는 k보다 크다. 강의 구현에서는 중복 키를 허용하지 않는다. 이 조건이 모든 노드에서 성립해야 중간 서브트리로 내려가도 같은 판단을 반복할 수 있다.
다음 코드는 강의의 탐색 흐름을 학습용으로 간결하게 정리한 C 예다. 현재 노드와 키가 같으면 그 노드를 돌려주고, 작으면 왼쪽, 크면 오른쪽으로 재귀 호출한다. 널 포인터에 도달하면 해당 키가 없다는 뜻이다.
#include <stddef.h>
typedef struct bst_node {
struct bst_node *left;
char key;
struct bst_node *right;
} bst_node;
bst_node *search_bst(bst_node *root, char key) {
if (root == NULL || root->key == key) return root;
if (key < root->key)
return search_bst(root->left, key);
return search_bst(root->right, key);
}이 코드는 한 단계에서 두 서브트리를 모두 뒤지지 않는다. 비교 결과가 반대편 서브트리에 목표 키가 있을 가능성을 없애므로 한 방향만 선택한다. 중위 순회를 수행하면 키가 오름차순으로 출력되는 것도 같은 불변 조건의 결과다.
탐색과 삽입은 같은 경로를 공유하되 끝에서 행동이 갈린다
탐색은 키를 찾으면 성공으로 끝나고 널 포인터를 만나면 실패한다. 삽입도 같은 비교 경로를 내려가지만, 널 포인터를 만난 자리에 새 노드를 연결한다. 새 키가 현재 키보다 작으면 왼쪽, 크면 오른쪽으로 이동하며, 같으면 중복이므로 강의 구현은 삽입하지 않는다.
직접 구성한 경로 추적
루트가 45이고 왼쪽 자식이 26, 오른쪽 자식이 68이며 26의 오른쪽 자식이 34라고 가정하자. 키 31을 삽입하면 31<45이므로 왼쪽, 31>26이므로 오른쪽, 31<34이므로 34의 왼쪽으로 간다. 그 자리가 비어 있으므로 31을 연결한다. 마지막에는 26<31<34 관계가 유지되는지 위아래 이웃과 검산한다.
오개념 교정: 삽입할 키가 루트보다 작다는 사실만으로 루트의 바로 왼쪽 자식이 되는 것은 아니다. 내려간 각 노드에서 다시 비교하며, 처음 만난 빈 자식 위치에 연결해야 서브트리 전체의 대소 관계가 유지된다.
삭제는 자식 수를 세면 세 가지 처리로 정리된다
삭제는 목표 노드를 찾는 것보다 그 자리를 어떻게 메우는지가 어렵다. 삭제 노드의 자식 수를 먼저 세면 연결 갱신을 세 경우로 나눌 수 있다. 부모 포인터를 함께 추적해야 부모가 삭제 노드를 가리키던 링크를 새 목적지로 바꿀 수 있다.
| 삭제 노드의 자식 수 | 새로 연결할 대상 | 핵심 처리 | 경계 사례 |
|---|---|---|---|
| 0개 | 널 포인터 | 부모의 해당 링크를 비운다. | 삭제 대상이 루트면 트리가 빈다. |
| 1개 | 유일한 자식 | 부모가 그 자식을 직접 가리키게 한다. | 루트 삭제면 자식이 새 루트가 된다. |
| 2개 | 왼쪽 최대 또는 오른쪽 최소 키 | 대체 키를 복사하고 대체 노드를 제거한다. | 대체 노드의 남은 한 자식도 연결한다. |
강의 코드는 두 자식이 있을 때 왼쪽 서브트리에서 가장 오른쪽 노드를 찾아 삭제 위치의 키로 옮긴다. 이는 삭제 키보다 작은 값 중 가장 큰 중위 선행자다. 대체 노드는 오른쪽 자식이 없으므로 결국 자식 0개 또는 1개인 더 단순한 삭제로 바뀐다.
삭제 판단 순서: 목표와 부모 찾기 → 자식 수 세기 → 대체 연결 결정 → 키 순서 검산의 순서로 본다. 두 자식인 경우에도 실제로 제거되는 노드는 대체 키를 제공한 선행자 또는 후속자다.
기본 BST의 약점은 정렬 실패가 아니라 높이의 불확실성이다
이진 탐색 조건을 완벽히 만족해도 트리가 한쪽으로 치우칠 수 있다. 어떤 키가 앞으로 자주 탐색될지, 삽입 순서가 어떤 모양을 만들지 미리 알 수 없다면 최적 구조를 처음부터 결정하기 어렵다. 루트에서 목표 노드까지 비교 횟수는 그 노드의 깊이에 좌우되므로 트리 높이가 길어질수록 최악의 탐색 경로도 길어진다.
강의는 이를 보완하는 두 방향을 제시한다. 하나는 최근 또는 자주 접근한 노드를 루트 가까이 옮기는 Splay 방식이고, 다른 하나는 트리의 균형이 일정 범위를 넘지 않도록 제한하는 AVL·BB 방식이다. 모두 회전으로 부모·자식 관계를 바꾸지만 중위 순서, 즉 키의 정렬 관계는 보존한다.
Splay·AVL·BB는 서로 다른 질문에 답한다
| 구조 | 먼저 묻는 질문 | 재구성 기준 | 학습 시 주의점 |
|---|---|---|---|
| Splay 트리 | 방금 접근한 노드는 어디에 있는가? | 그 노드를 회전시켜 루트까지 올림 | 항상 높이 균형을 보장하는 규칙은 아님 |
| AVL 트리 | 왼쪽과 오른쪽 높이 차가 얼마인가? | 모든 노드에서 높이 차를 최대 1로 제한 | 노드 수가 비슷해도 높이 차를 따로 계산 |
| BB 트리 | 양쪽 서브트리의 무게 비율은 얼마인가? | β가 정한 무게 범위 안에 유지 | 높이가 아니라 강의에서 정의한 무게를 비교 |
따라서 “어느 트리가 가장 균형 잡혔는가?”라는 질문만으로는 충분하지 않다. 접근 지역성을 활용할 것인지, 높이 차를 엄격히 제한할 것인지, 양쪽 무게의 비율을 관리할 것인지에 따라 판단 기준이 달라진다.
Splay 회전은 x·부모 p·조부모 g의 방향 관계로 고른다
Splay 연산은 최근 접근한 노드 x를 루트까지 올린다. p는 x의 부모, g는 조부모다. 한 번의 이름을 외우기보다 x와 p가 같은 방향에 있는지, 반대 방향에 있는지를 먼저 그리면 회전 종류를 판별하기 쉽다.
| 상태 | 관계 | 회전 흐름 | 한 단계 뒤의 중심 |
|---|---|---|---|
| Zig | p가 루트 | p와 x 사이를 한 번 회전 | x가 루트가 됨 |
| Zig-Zig | x와 p가 모두 왼쪽 또는 모두 오른쪽 | g-p를 회전한 뒤 p-x를 회전 | x가 해당 부분트리의 루트가 됨 |
| Zig-Zag | x와 p의 방향이 서로 반대 | p-x를 회전한 뒤 새 부모 g와 x를 회전 | x가 해당 부분트리의 루트가 됨 |
학습을 위해 72의 왼쪽 자식이 51, 51의 왼쪽 자식이 37이라고 가정하자. x=37과 p=51이 모두 왼쪽 방향이므로 Zig-Zig다. 먼저 72와 51을 회전하고, 이어 51과 37을 회전하면 37이 이 부분트리의 위로 올라간다. 반대로 37이 51의 오른쪽 자식이었다면 방향이 꺾이므로 Zig-Zag를 선택한다.
잘못된 판단의 원인: x가 왼쪽 자식이라는 사실 하나만 보고 Zig-Zig를 고르면 틀릴 수 있다. p가 g의 어느 쪽 자식인지까지 함께 봐야 ‘같은 방향’인지 ‘꺾인 방향’인지 결정된다.
Splay는 최근 접근을 반영하지만 항상 낮은 트리를 만들지는 않는다
Splay 트리는 접근할 때마다 해당 노드를 루트로 올린다. 같은 키가 가까운 시기에 다시 사용된다면 다음 접근 경로가 짧아질 수 있다. 강의의 적용 예에서도 깊은 곳의 노드 7이 여러 번의 회전을 거쳐 루트가 되며, 각 회전은 키의 중위 순서를 바꾸지 않는다.
그러나 Splay의 목표는 모든 노드에서 높이 차를 1 이하로 만드는 것이 아니다. 방금 접근한 노드를 올리는 과정에서 다른 경로가 길어질 수 있다. 따라서 한 번의 회전 뒤 모양만 보고 AVL 조건까지 만족한다고 단정하지 않는다.
Splay 검산: x가 실제로 루트에 도달했는가 → 왼쪽에는 x보다 작은 키, 오른쪽에는 큰 키가 남았는가 → 분리했던 부분트리가 올바른 경계 키 사이에 다시 붙었는가를 차례로 확인한다.
AVL은 모든 노드에서 좌우 높이 차를 다시 계산한다
AVL 트리는 거의 완전한 균형을 허용하는 높이 균형 트리다. 각 노드에서 왼쪽 서브트리 높이와 오른쪽 서브트리 높이의 차가 최대 1이어야 한다. 루트 한 곳만 검사하는 것이 아니라 삽입 또는 삭제 경로를 따라 영향을 받은 조상들의 높이를 확인한다.
직접 구성한 높이 검산
루트 40의 왼쪽 자식이 25, 오른쪽 자식이 60이고, 25의 자식이 15와 30이라고 하자. 여기에 10을 15의 왼쪽에 넣으면 40의 왼쪽 서브트리 높이는 3, 오른쪽은 1이 되어 차가 2다. BST 순서는 맞지만 AVL 조건은 깨진다. 왼쪽-왼쪽 방향의 치우침을 회전으로 고치면 25가 위로 올라가고, 40은 오른쪽으로 내려가며 30은 둘 사이에 다시 붙는다.
회전 후 중위 순서는 10, 15, 25, 30, 40, 60으로 전과 같다. 동시에 새 루트 25의 좌우 높이와 노드 40의 좌우 높이 차가 모두 1 이하인지 확인해야 한다. 키 순서 검산과 높이 검산은 서로 다른 검사다.
오개념 교정: 왼쪽과 오른쪽 노드 수가 같아야 AVL인 것은 아니다. AVL이 직접 제한하는 것은 서브트리의 높이 차이며, 노드 수가 달라도 높이 차가 1 이하면 허용된다.
BB는 높이 대신 서브트리 무게의 비율을 제한한다
강의에서 트리의 무게는 트리에 속한 잎 노드의 개수로 정의한다. BB 트리는 각 노드의 양쪽 서브트리 무게가 지나치게 벌어지지 않도록 하는 무게 균형 트리다. 강의는 한 가지 비율 조건으로 √2−1 < 왼쪽 무게/오른쪽 무게 < √2+1을 제시하고, 균형의 엄격함을 조절하는 인수 β도 설명한다.
β는 0<β≤1/2 범위에 있다. 한쪽 서브트리 무게가 양쪽 무게 합에서 차지하는 비율을 β와 1−β 사이로 제한한다고 보면 된다. β=1/2이면 두 서브트리의 무게가 같아야 한다. β=1/4이면 한쪽 비율은 최소 1/4, 최대 3/4이므로 한쪽이 다른 쪽보다 약 3배의 무게를 갖는 경우까지 허용된다. β가 1/2에 가까울수록 조건은 엄격해진다.
직접 계산하는 β 판정
학습용 예로 왼쪽 무게가 3, 오른쪽 무게가 7이라고 하자. 왼쪽이 전체에서 차지하는 비율은 3/(3+7)=0.3이다. β=1/4이면 허용 구간 [0.25, 0.75] 안에 있으므로 통과한다. β=0.4이면 허용 구간 [0.4, 0.6]보다 작아 통과하지 못한다. 같은 트리라도 β를 어떻게 정했는지에 따라 판정이 달라진다.
회전 문제는 보존할 것과 개선할 것을 분리해 푼다
- 공통 조건 확인: 모든 후보가 왼쪽<부모<오른쪽의 BST 순서를 유지해야 한다.
- 목표 구조 선택: 최근 접근 노드를 올릴지, 높이 차를 줄일지, 무게 비율을 맞출지 정한다.
- 국소 관계 판별: Splay는 x-p-g 방향, AVL은 불균형 방향, BB는 양쪽 무게를 본다.
- 부분트리 재연결: 회전에 직접 참여하지 않은 부분트리도 키 범위에 맞는 자리에 붙인다.
- 두 번 검산: 중위 순서가 보존되었는지 확인한 뒤 각 구조의 목표 조건을 다시 계산한다.
회전 전후에 중위 순서가 달라졌다면 균형 여부를 보기 전에 이미 BST 조건을 깨뜨린 것이다. 반대로 중위 순서가 같다고 해서 AVL 높이 조건이나 BB 무게 조건까지 자동으로 맞는 것은 아니다. ‘정렬 보존’과 ‘구조 개선’을 분리해 검사해야 오류 원인을 찾을 수 있다.
핵심 개념 정리
- 이진 탐색 트리는 모든 노드에서 왼쪽 키<현재 키<오른쪽 키 관계를 유지하며, 탐색과 삽입은 같은 비교 경로를 따른다.
- 삭제는 자식 0개·1개·2개를 나눠 처리하고, 두 자식이면 중위 선행자 또는 후속자로 문제를 단순화한다.
- Splay 트리는 최근 접근 노드를 루트로 올리고, 회전 유형은 x·p·g의 방향 관계로 판정한다.
- AVL은 좌우 서브트리의 높이 차를 최대 1로 제한하고, BB는 β가 정한 서브트리 무게 비율을 유지한다.
- 회전은 키의 중위 순서를 보존해야 하며, 그다음에 높이·무게·접근 위치라는 각 트리의 목표를 따로 검산한다.
전체 사고 흐름: 먼저 BST의 대소 순서가 유지되는지 확인하고, 연산이 삭제라면 자식 수를 세며, 재구성 문제라면 Splay의 접근 위치·AVL의 높이·BB의 무게 중 무엇을 관리하는지 판별한다. 회전 뒤에는 중위 순서와 해당 균형 조건을 별도로 검사해야 새로운 예에서도 구조를 정확히 판단할 수 있다.
예상문제 10선
1. 중복 키를 허용하지 않는 이진 탐색 트리의 조건으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
- ① 오답: 왼쪽과 오른쪽의 대소 방향을 뒤바꿨다.
- ② 정답: 이 관계가 모든 노드에서 성립해야 한 방향 탐색이 가능하다.
- ③ 오답: 같은 깊이라는 위치는 키의 동일성을 요구하지 않는다.
- ④ 오답: 삽입 순서는 모양에 영향을 주지만 위치는 매 단계 키 비교로 정한다.
2. 루트 45, 왼쪽 26, 26의 오른쪽 34인 트리에 키 31을 삽입하는 경로는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
- ① 오답: 31은 45보다 작으므로 첫 방향부터 왼쪽이다.
- ② 오답: 31은 26보다 크므로 26의 오른쪽으로 가야 한다.
- ③ 오답: 34는 26의 오른쪽에서 만나며 31은 34보다 작다.
- ④ 정답: 31<45, 31>26, 31<34를 차례로 적용한 경로다.
3. 자식이 하나인 BST 노드를 삭제할 때 올바른 연결은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
- ① 정답: 유일한 서브트리를 부모 위치에 이어 붙이면 순서와 도달성을 보존한다.
- ② 오답: 남겨야 할 데이터까지 불필요하게 제거한다.
- ③ 오답: 키를 남기면 목표 노드가 삭제되지 않고 서브트리도 유실된다.
- ④ 오답: 루트를 삭제하면 그 자식이 새 루트가 되어야 한다.
4. 자식이 둘인 노드의 삭제를 왼쪽 서브트리로 처리할 때 먼저 고를 노드는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
- ① 오답: 가장 작은 키는 삭제 위치와 가까운 경계값이 아니다.
- ② 오답: 오른쪽을 쓴다면 가장 작은 중위 후속자를 골라야 한다.
- ③ 정답: 삭제 키보다 작은 값 중 가장 큰 중위 선행자라 대소 관계를 보존한다.
- ④ 오답: 깊이만으로 고르면 삭제 위치의 양쪽 키 범위를 깨뜨릴 수 있다.
5. Splay·AVL·BB 트리의 기준을 옳게 연결한 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
- ① 오답: 세 구조의 관리 대상을 서로 바꿔 연결했다.
- ② 정답: 접근 지역성, 높이 균형, 무게 균형의 차이를 정확히 구분한다.
- ③ 오답: Splay와 BB의 핵심 기준이 뒤바뀌었다.
- ④ 오답: 최근 접근 노드를 올리는 것은 Splay의 동작이다.
6. g의 왼쪽 자식이 p이고 p의 오른쪽 자식이 x일 때 필요한 Splay 회전은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
- ① 정답: p는 왼쪽, x는 오른쪽으로 방향이 꺾이므로 이중 회전한다.
- ② 오답: 둘 다 왼쪽일 때만 왼쪽 Zig-Zig다.
- ③ 오답: 둘 다 오른쪽인 구조가 아니다.
- ④ 오답: 문제에는 조부모 g가 있으므로 p는 루트가 아니다.
7. “Splay 연산 뒤에는 모든 노드의 좌우 높이 차가 1 이하가 된다”라는 설명의 오류는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
- ① 오답: Splay도 BST 순서를 유지하며 회전한다.
- ② 오답: 최근 접근 노드를 올리는 동작은 탐색 등 접근과 함께 사용된다.
- ③ 오답: Splay는 Zig·Zig-Zig·Zig-Zag 회전을 사용한다.
- ④ 정답: 높이 차 최대 1은 AVL 조건이며 Splay는 최근 접근 위치를 반영한다.
8. 어떤 노드의 왼쪽 무게가 3, 오른쪽 무게가 7일 때 왼쪽의 전체 무게 비율은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
- ① 오답: 양쪽의 비가 아니라 전체 중 왼쪽이 차지하는 몫을 묻는다.
- ② 오답: 이는 오른쪽이 전체에서 차지하는 비율이다.
- ③ 정답: 전체 무게 10 중 왼쪽 무게가 3이므로 0.3이다.
- ④ 오답: 무게 차이를 전체로 나눈 값은 왼쪽의 점유 비율이 아니다.
9. β=1/4인 BB 조건과 β=1/2인 조건을 옳게 비교한 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
- ① 오답: β가 1/2에 가까울수록 허용 구간이 좁아진다.
- ② 오답: β=1/4는 [1/4, 3/4], β=1/2는 한 점으로 범위가 다르다.
- ③ 오답: β=1/2이면 양쪽 무게가 같아야 한다.
- ④ 정답: β가 커질수록 균형 조건이 엄격해지는 관계를 반영한다.
10. 회전으로 재구성한 트리를 검토하는 가장 적절한 순서는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
- ① 정답: 공통 불변 조건과 구조별 목표를 분리해 확인하는 절차다.
- ② 오답: 루트가 같아도 하위 연결이 잘못되어 키 순서가 깨질 수 있다.
- ③ 오답: 중위 순서가 바뀌면 BST 조건을 잃으므로 균형 개선으로 볼 수 없다.
- ④ 오답: 세 구조는 최근 접근·높이·무게라는 서로 다른 기준을 사용한다.
참고 자료와 작성 기준
이 글은 방송대 컴퓨터과학과 「자료구조」 11강 ‘BS, Splay, AVL, BB’ 강의록을 바탕으로 이진 탐색 트리 연산과 세 재구성 전략의 판단 기준을 학습 목적에 맞게 재구성한 비공식 학습자료입니다. 31 삽입 경로, AVL 높이 검산과 β 무게 계산은 강의 원리를 연습하도록 직접 구성한 예입니다.
- 작성·편집: 올에이클래스 학습연구팀
- 주요 근거: 방송대 컴퓨터과학과 자료구조 11강 강의록
- 외부 보충 자료: 사용하지 않음
- 편집 원칙: 올에이클래스 편집 정책
- 최종 내용 검토: 2026-08-18
댓글
댓글 쓰기