방송대 방통대 자료구조 11강 - 이진 탐색 트리와 균형 트리 - 요약 노트 시험족보 예상문제 - 올에이클래스

자료구조 11강 - 이진 탐색 트리와 균형 트리

이진 탐색 트리의 정렬 규칙을 바탕으로 탐색·삽입·삭제 과정을 익힌다. 트리 모양이 성능에 미치는 영향을 이해하고, 최근 접근 노드를 루트로 옮기는 Splay 트리와 높이·무게의 균형을 관리하는 AVL·BB 트리의 차이를 정리한다.

01. 이진 탐색 트리의 개념

키의 대소 관계로 탐색 범위를 줄이는 트리

이진 탐색 트리(binary search tree, BS 트리)는 특정 데이터의 검색과 노드의 삽입·삭제를 효율적으로 처리하기 위해 순서 제약을 둔 이진 트리이다. 탐색·삽입·삭제에서 비교 대상이 되는 값을 키(key)라고 한다. 키는 노드의 데이터 자체일 수도 있고 노드를 구별하는 별도의 필드일 수도 있다.

임의의 노드 v를 기준으로 왼쪽 서브트리의 모든 키는 v의 키보다 작고, 오른쪽 서브트리의 모든 키는 v의 키보다 크다. 이 조건이 모든 노드에서 재귀적으로 성립해야 한다. 강의의 삽입 구현은 같은 키를 다시 넣지 않는 것으로 설명하므로 중복 키는 허용하지 않는다.

핵심 규칙: 왼쪽 키 < 현재 키 < 오른쪽 키. 단순히 루트와 자식 사이에서만 맞으면 되는 것이 아니라 각 노드의 전체 왼쪽·오른쪽 서브트리에 적용된다.

하나의 정렬 순서, 여러 트리 모양

같은 키 집합으로도 삽입 순서에 따라 서로 다른 모양의 이진 탐색 트리가 만들어질 수 있다. 그러나 어느 올바른 BS 트리든 중위 순회하면 키가 오름차순으로 출력된다. 모양은 달라도 정렬 결과가 같은 이유가 바로 왼쪽-루트-오른쪽의 순서 제약 때문이다.

02. 이진 탐색 트리의 탐색과 삽입

탐색 과정

탐색은 루트에서 시작해 찾을 키 k와 현재 노드의 키 k_i를 비교한다. 두 값이 같으면 탐색에 성공한다. k가 더 작으면 왼쪽 서브트리로, 더 크면 오른쪽 서브트리로 이동한다. 이동한 포인터가 NULL이 되면 해당 키가 트리에 없으므로 탐색에 실패한다.

비교 결과	다음 동작
k = 현재 키	현재 노드를 반환하고 탐색 성공
k < 현재 키	왼쪽 서브트리를 탐색
k > 현재 키	오른쪽 서브트리를 탐색
현재 포인터가 NULL	키를 찾지 못했으므로 탐색 실패

삽입 과정

삽입도 먼저 탐색 경로를 따른다. 삽입 키가 현재 키보다 작으면 왼쪽, 크면 오른쪽으로 이동한다. 해당 방향의 자식 포인터가 NULL인 위치를 만나면 그곳에 새 노드를 연결한다. 같은 키를 만나면 중복 키이므로 강의 구현에서는 삽입을 중단한다.

예를 들어 루트가 C이고 왼쪽에 B, 오른쪽에 E, E의 왼쪽에 D가 있을 때 A는 C보다 작고 B보다 작으므로 B의 왼쪽에 삽입된다. F는 C와 E보다 크므로 E의 오른쪽에 삽입된다. 삽입 후에도 중위 순회 결과는 A-B-C-D-E-F로 정렬된다.

탐색과 삽입의 비교 횟수는 방문한 경로 길이에 좌우된다. 트리가 균형에 가까우면 경로가 짧지만, 한쪽으로 치우치면 연결 리스트처럼 길어질 수 있다.

03. 이진 탐색 트리의 삭제

자식 수에 따라 달라지는 처리

삭제할 노드를 먼저 탐색한 다음 자식 수를 확인한다. 잎 노드는 부모의 해당 링크를 NULL로 바꾸면 된다. 자식이 하나인 노드는 부모가 삭제 노드의 유일한 자식을 직접 가리키게 한다. 자식이 둘인 노드는 연결을 단순히 끊을 수 없으므로 순서를 보존하는 대체 노드를 사용해야 한다.

삭제 노드의 상태	처리 방법
자식 0개	부모의 해당 포인터를 NULL로 바꾸고 노드 제거
자식 1개	부모 포인터를 삭제 노드의 유일한 자식에 연결
자식 2개	왼쪽 서브트리의 최댓값인 중위 선행자 또는 오른쪽 서브트리의 최솟값인 중위 후속자로 대체

자식이 둘인 경우 강의 코드는 왼쪽 서브트리에서 가장 오른쪽 노드, 즉 중위 선행자를 찾아 삭제 노드의 키로 옮기고 원래 선행자 노드를 제거하는 방식을 보여 준다. 반대로 오른쪽 서브트리의 가장 왼쪽 노드인 중위 후속자를 사용해도 탐색 트리 순서를 보존할 수 있다.

삭제 판단 순서: 삭제 노드 탐색 → 자식 수 확인 → 0개면 링크 제거, 1개면 자식 올리기, 2개면 선행자·후속자로 값 대체 후 그 노드 삭제.

04. 트리 모양과 탐색 성능

균형이 성능을 좌우한다

BS 트리는 어느 키가 어떤 순서로 삽입되는지에 따라 모양이 달라진다. 균형 잡힌 트리에서는 비교할 때마다 탐색 범위가 크게 줄어 평균적으로 짧은 경로를 사용한다. 반대로 정렬된 키를 순서대로 삽입해 한쪽으로 길게 늘어진 트리가 되면 탐색 경로가 노드 수에 비례할 수 있다.

앞으로 어떤 노드를 자주 탐색·삽입·삭제할지 미리 알 수 없다면 경험적으로 좋은 구조를 만들기 어렵다. 이에 따라 두 방향의 개선이 사용된다. 자주 쓰는 노드를 위로 올리는 Splay 트리와, 구조 자체의 균형 조건을 유지하는 AVL·BB 트리이다.

구조	관리 기준	핵심 아이디어
Splay 트리	최근 접근 이력	접근한 노드를 회전해 루트 가까이 이동
AVL 트리	서브트리 높이	왼쪽·오른쪽 높이 차를 1 이하로 제한
BB 트리	서브트리 무게	양쪽 서브트리의 노드 분포 비율을 제한

05. Splay 트리와 회전 연산

최근 사용한 노드를 루트로 옮기는 적응형 트리

Splay 트리는 자주 탐색하는 키를 가진 노드가 루트 가까이에 위치하도록 구성한 이진 탐색 트리이다. 노드 x에 접근하면 x가 루트가 될 때까지 Splay 연산을 반복한다. 최근 접근한 노드를 다시 사용할 가능성이 높다는 지역성을 활용하므로 자주 사용하는 키의 다음 접근 경로가 짧아진다.

Splay 연산에서도 이진 탐색 트리의 중위 순서가 보존되도록 간선 연결을 회전한다. x의 부모를 p, 조부모를 g라고 할 때 세 가지 경우를 구분한다.

연산	조건	회전
Zig	p가 루트인 경우	p와 x 사이를 한 번 회전
Zig-Zig	x와 p가 모두 같은 방향의 자식인 경우	p-g 연결을 회전한 뒤 x-p 연결을 회전
Zig-Zag	x와 p의 방향이 서로 반대인 경우	x-p 연결을 회전한 뒤 x-g 연결을 회전

예를 들어 x가 p의 왼쪽 자식이고 p도 g의 왼쪽 자식이면 같은 방향이므로 Zig-Zig이다. x가 p의 왼쪽 자식이지만 p가 g의 오른쪽 자식이면 방향이 엇갈리므로 Zig-Zag이다. 회전 후에도 x보다 작은 키는 왼쪽, 큰 키는 오른쪽에 남아야 한다.

Splay 트리는 모든 순간 완전한 균형을 강제하지 않는다. 접근 패턴에 따라 구조를 스스로 조정하며 최근 접근 노드를 루트로 올린다는 점이 AVL 트리와 다르다.

06. AVL 트리

높이 차를 제한하는 균형 이진 탐색 트리

AVL 트리는 Adelson-Velskii와 Landis가 제안한 높이 균형 이진 탐색 트리이다. 완전히 가득 찬 모양을 요구하지는 않지만, 모든 노드 v에서 왼쪽 서브트리 높이와 오른쪽 서브트리 높이의 차가 최대 1이어야 한다.

키를 삽입하거나 삭제한 뒤 특정 노드에서 높이 차의 절댓값이 2 이상이 되면 AVL 조건을 위반한다. 이때 회전을 적용해 높이를 다시 균형 있게 만든다. 이 제약 덕분에 트리가 한쪽으로 길게 늘어지는 현상을 방지하고 직접 탐색 성능을 안정적으로 유지한다.

AVL 조건: 모든 노드 v에 대해 |높이(v의 왼쪽 서브트리) - 높이(v의 오른쪽 서브트리)| ≤ 1.

완전히 균형 잡힌 트리를 매 삽입마다 만들려면 많은 노드를 옮길 수 있다. AVL 트리는 높이 차 1까지 허용하는 완화된 조건을 사용하므로 비교적 적은 회전으로 탐색 경로의 높이를 제한한다.

07. BB 트리와 무게 균형

서브트리의 노드 분포를 기준으로 균형 잡기

BB(bound-balanced) 트리는 높이가 아니라 각 노드의 양쪽 서브트리 무게를 기준으로 균형을 유지하는 이진 탐색 트리이다. 강의에서 트리의 무게는 트리에 속한 잎 노드의 개수로 설명한다.

균형 제어 인수 β는 0 < β ≤ 1/2 범위에 있다. 임의의 노드 x에서 한쪽 서브트리의 무게가 전체에 비해 너무 작거나 너무 커지지 않도록 비율을 β와 1-β 사이로 제한한다. β = 1/2이면 양쪽 서브트리가 같은 무게를 가져야 하는 가장 엄격한 균형이고, β = 1/4이면 한쪽이 다른 쪽보다 약 세 배 많은 노드를 갖는 정도까지 허용한다.

구분	AVL 트리	BB 트리
균형 기준	왼쪽·오른쪽 서브트리 높이 차	왼쪽·오른쪽 서브트리 무게 비율
제어 값	높이 차 절댓값 ≤ 1	0 < β ≤ 1/2의 무게 제한
목적	탐색 경로의 높이를 제한	노드 분포의 치우침을 제한

완전한 균형을 매번 유지하려면 삽입·삭제 때 O(n)개의 노드를 옮길 수도 있지만, AVL과 BB 트리는 완화된 균형 조건을 사용해 일반적으로 O(log n) 수준의 노드 이동으로 균형을 회복하도록 설계된다.

08. 핵심 개념 정리

이진 탐색 트리는 모든 노드에서 왼쪽 키가 작고 오른쪽 키가 큰 순서 규칙을 지킨다. 탐색과 삽입은 키 비교에 따라 한쪽 서브트리로 내려가며, 중위 순회 결과는 오름차순이다.

삭제는 자식 수에 따라 처리한다. 잎은 링크를 끊고, 자식 하나면 그 자식을 올리며, 자식 둘이면 중위 선행자나 후속자로 대체한다. 연산 시간은 트리 높이에 좌우되므로 치우친 모양을 방지하거나 자주 쓰는 노드를 위로 올릴 필요가 있다.

Splay는 최근 접근 노드를 Zig·Zig-Zig·Zig-Zag 회전으로 루트에 올린다. AVL은 서브트리 높이 차를 1 이하로, BB는 서브트리 무게 비율을 정해진 범위로 유지한다.

최종 암기: BS 중위 순회 = 오름차순 · 삭제 0/1/2자식 구분 · Splay = 최근 접근 노드를 루트로 · Zig는 1회전 · Zig-Zig·Zig-Zag는 2회전 · AVL = 높이 균형 · BB = 무게 균형.

예상문제 20개

1. 이진 탐색 트리에서 임의의 노드 v에 대한 올바른 키 관계는?

① 왼쪽과 오른쪽 키가 모두 v보다 작다. ② 왼쪽 키는 v보다 크고 오른쪽 키는 작다. ③ 자식의 키에는 아무 제한이 없다. ④ 왼쪽 서브트리 키 < v의 키 < 오른쪽 서브트리 키

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
이 관계가 트리의 모든 노드와 전체 서브트리에서 성립해야 한다.

2. 이진 탐색 트리를 중위 순회했을 때 얻는 결과는?

① 삽입 순서 ② 키의 오름차순 ③ 키의 무작위 순서 ④ 레벨의 내림차순

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
중위 순회는 왼쪽-루트-오른쪽 순서이므로 BS 트리의 키를 오름차순으로 출력한다.

3. 현재 노드의 키가 50이고 찾는 키가 30일 때 다음 탐색 방향은?

① 왼쪽 서브트리 ② 오른쪽 서브트리 ③ 루트로 되돌아간다. ④ 즉시 탐색에 성공한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
30은 50보다 작으므로 더 작은 키가 모여 있는 왼쪽 서브트리로 이동한다.

4. 이진 탐색 트리에서 탐색 포인터가 NULL에 도달했다는 의미는?

① 루트가 삭제되었다. ② 중복 키를 찾았다. ③ 찾는 키가 트리에 없어 탐색에 실패했다. ④ 트리가 항상 균형 상태이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
키 비교에 따라 내려갔으나 더 이어지는 노드가 없으므로 해당 키는 존재하지 않는다.

5. 강의의 BS 트리 삽입 연산에서 현재 키와 삽입 키가 같을 때의 처리는?

① 왼쪽에 같은 키를 추가한다. ② 오른쪽에 같은 키를 추가한다. ③ 기존 키를 두 배로 바꾼다. ④ 중복 키로 판단하여 삽입하지 않는다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
강의의 삽입 코드는 같은 키를 만나면 중복값을 허용하지 않고 종료한다.

6. 자식이 없는 잎 노드를 삭제하는 방법은?

① 부모의 해당 포인터를 NULL로 바꾼다. ② 전체 트리를 다시 생성한다. ③ 모든 형제 노드도 함께 삭제한다. ④ 반드시 루트와 교환한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
잎은 자식 서브트리가 없으므로 부모와의 연결을 끊고 공간을 반환하면 된다.

7. 자식이 하나인 BS 트리 노드를 삭제할 때의 올바른 처리는?

① 유일한 자식도 함께 삭제한다. ② 부모가 삭제 노드의 유일한 자식을 가리키게 한다. ③ 반대편에 빈 노드를 만든다. ④ 중위 순회를 금지한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
유일한 자식을 삭제 위치로 올려 부모와 직접 연결하면 탐색 순서가 유지된다.

8. 자식이 둘인 노드를 삭제할 때 대체 노드로 사용할 수 있는 것은?

① 트리의 임의의 잎 ② 루트의 부모 ③ 중위 선행자 또는 중위 후속자 ④ 가장 깊은 노드라면 무엇이든 가능하다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
왼쪽의 최댓값 또는 오른쪽의 최솟값은 삭제 위치에서 BS 순서를 보존한다.

9. BS 트리가 한쪽으로 길게 치우쳤을 때 나타나는 문제는?

① 탐색 경로가 노드 수에 비례해 길어질 수 있다. ② 중위 순회가 내림차순으로 바뀐다. ③ 모든 키가 자동으로 중복된다. ④ 노드 삭제가 항상 불가능하다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
편향 트리는 연결 리스트와 비슷한 모양이 되어 루트부터 긴 경로를 따라가야 한다.

10. Splay 트리의 기본 아이디어는?

① 모든 잎을 같은 레벨에 둔다. ② 키를 삽입 순서로만 출력한다. ③ 가장 작은 키를 항상 루트로 둔다. ④ 최근 접근한 노드를 회전해 루트 가까이 옮긴다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
Splay는 최근 사용 노드를 다시 사용할 가능성이 높다는 접근 지역성을 활용한다.

11. Splay 연산에서 x의 부모 p가 루트일 때 사용하는 회전은?

① Zig-Zag ② Zig-Zig ③ Zig ④ BB

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
부모가 루트이면 x와 p 사이를 한 번 회전하는 Zig를 적용한다.

12. x와 부모 p가 조부모 g에 대해 같은 방향으로 연속된 자식일 때 적용하는 것은?

① Zig ② Zig-Zig ③ Zig-Zag ④ 중위 삭제

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
왼쪽-왼쪽 또는 오른쪽-오른쪽처럼 방향이 같으면 Zig-Zig 이중 회전을 사용한다.

13. x와 부모 p의 방향이 서로 엇갈릴 때 적용하는 Splay 연산은?

① 단일 Zig만 적용 ② Zig-Zig ③ 회전하지 않음 ④ Zig-Zag

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
왼쪽-오른쪽 또는 오른쪽-왼쪽처럼 방향이 반대이면 Zig-Zag 이중 회전을 적용한다.

14. Splay 회전 후에도 반드시 유지되어야 하는 성질은?

① 모든 레벨이 가득 차야 한다. ② 이진 탐색 트리의 키 순서 ③ 루트의 키가 항상 가장 작아야 한다. ④ 모든 노드의 높이가 같아야 한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
회전은 구조를 바꾸지만 중위 순서, 즉 왼쪽 < 루트 < 오른쪽 관계는 보존한다.

15. AVL 트리의 균형 조건은?

① 모든 노드에서 양쪽 서브트리 높이 차의 절댓값이 1 이하이다. ② 모든 노드의 키가 같다. ③ 왼쪽 서브트리가 항상 비어 있다. ④ 잎 노드가 정확히 두 개이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
AVL은 각 노드의 왼쪽·오른쪽 높이 차를 최대 1까지 허용하는 높이 균형 트리이다.

16. AVL 트리에서 삽입 후 높이 차의 절댓값이 2가 되었다면?

① AVL 조건을 만족한다. ② 중위 순회를 한 번만 하면 해결된다. ③ AVL 조건을 위반하므로 회전으로 균형을 회복해야 한다. ④ 해당 트리는 자동으로 Splay 트리가 된다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
AVL이 허용하는 높이 차는 1 이하이므로 2가 되면 균형 조정이 필요하다.

17. BB 트리에서 균형 판단의 기준이 되는 것은?

① 최근 접근 시간 ② 양쪽 서브트리의 무게 비율 ③ 키의 문자 길이 ④ 루트의 삽입 시각

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
BB는 bound-balanced의 약자로 양쪽 서브트리 무게의 치우침을 제한한다.

18. BB 트리의 균형 제어 인수 β의 범위는?

① β < 0 ② β > 1 ③ 1/2 < β < 1 ④ 0 < β ≤ 1/2

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
β는 0보다 크고 1/2 이하이며 값이 1/2에 가까울수록 더 엄격한 무게 균형을 요구한다.

19. AVL 트리와 BB 트리의 차이를 바르게 설명한 것은?

① AVL은 최근 접근, BB는 키 순서를 기준으로 한다. ② AVL은 무게, BB는 최근 접근을 기준으로 한다. ③ AVL은 높이, BB는 무게를 균형 기준으로 한다. ④ 두 트리는 균형 조건이 완전히 같다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
AVL은 서브트리 높이 차를, BB는 서브트리 노드 분포인 무게 비율을 제한한다.

20. Splay·AVL·BB 트리의 공통 기반이 되는 자료구조는?

① 이진 탐색 트리 ② 원형 큐 ③ 단순 연결 리스트 ④ 인접 행렬

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
세 트리는 BS 트리의 키 순서를 유지하면서 접근 특성이나 균형 조건을 추가한 구조이다.