이진 탐색 트리의 문제점
이진 탐색 트리(Binary Search Tree)는 탐색, 삽입, 삭제 연산이 트리의 높이(height)에 비례한다.
- 평균적인 경우: O(log N)
- 최악의 경우: O(N)
문제의 핵심
- 데이터가 정렬된 상태로 입력될 경우
- 트리가 한쪽으로 치우친 편향 트리(Skewed Tree)가 된다
- 결국 연결 리스트와 유사한 구조가 된다
이 경우 탐색 성능이 크게 저하된다.
편향 트리의 특징
- 모든 노드가 한 방향으로만 연결됨
- 트리의 높이 = N
- 탐색 시간 복잡도 = O(N)
해결 방법: 균형 트리
이 문제를 해결하기 위해 트리의 균형을 유지하는 자료구조들이 등장했다.
대표적인 균형 트리 종류
AVL 트리
- 삽입/삭제 시마다 균형을 엄격하게 유지
- 항상 높이를 O(log N)으로 유지
2-3 트리
- 하나의 노드가 2개 또는 3개의 자식을 가질 수 있음
- 트리의 높이를 낮게 유지
2-3-4 트리
- 하나의 노드가 최대 4개의 자식을 가질 수 있음
- Red-Black 트리와 구조적으로 연관됨
Red-Black 트리 Red-Black Tree
- 노드에 색상(빨강/검정)을 부여하여 균형 유지
- AVL보다 완화된 균형 조건으로 삽입/삭제가 빠름
B 트리
- 디스크 기반 시스템에서 효율적인 구조
- 한 노드에 많은 데이터를 저장 가능
- 데이터베이스, 파일 시스템에서 사용
AVL 트리
AVL 트리는 노드가 추가되거나 삭제될 때, 스스로 균형 상태를 확인하고 필요 시 트리 구조를 변경하는 자가 균형 이진 탐색 트리이다.
균형 정도를 판단하기 위해 균형 인수(Balance Factor)를 사용한다.
균형 인수
- 균형 인수: -1, 0, 1 → 정상 상태
- 균형 인수의 절댓값이 2 이상 → 불균형 상태 (리밸런싱 필요)
AVL 트리 회전 정리
- LL, RR, LR, RL → 불균형의 형태 (케이스)
- Right Rotation / Left Rotation → 실제 수행하는 회전 연산
LL (Left Left)
- 불균형 노드의 균형 인수: +2
- 그 왼쪽 자식의 균형 인수: +1 또는 0
- 왼쪽 자식의 왼쪽 서브트리에 삽입되어 발생
→ LL 케이스 → Right Rotation (오른쪽 회전)
처리
- 왼쪽 자식이 부모로 올라간다
- 기존 부모는 오른쪽 자식으로 내려간다
- 왼쪽 자식의 오른쪽 서브트리는 기존 부모의 왼쪽 서브트리로 이동한다
RR (Right Right)
- 불균형 노드의 균형 인수: -2
- 그 오른쪽 자식의 균형 인수: -1 또는 0
- 오른쪽 자식의 오른쪽 서브트리에 삽입되어 발생
→ RR 케이스 → Left Rotation (왼쪽 회전)
처리
- 오른쪽 자식이 부모로 올라간다
- 기존 부모는 왼쪽 자식으로 내려간다
- 오른쪽 자식의 왼쪽 서브트리는 기존 부모의 오른쪽 서브트리로 이동한다
LR (Left Right)
- 불균형 노드의 균형 인수: +2
- 그 왼쪽 자식의 균형 인수: -1
- 왼쪽 자식의 오른쪽 서브트리에 삽입되어 발생
→ LR 케이스 → Left Rotation + Right Rotation
처리 순서
- 왼쪽 자식을 기준으로 Left Rotation (왼쪽 회전)
- 이후 부모를 기준으로 Right Rotation (오른쪽 회전)
과정
1단계 (부분 회전)
- 왼쪽 자식의 오른쪽 자식이 위로 올라온다
- 기존 왼쪽 자식은 그 왼쪽 자식으로 내려간다
- 올라온 노드의 왼쪽 서브트리는 기존 왼쪽 자식의 오른쪽 서브트리로 이동한다
→ LL 형태로 변환된다
2단계 (전체 회전)
- 중간 노드가 새로운 부모가 된다
- 기존 부모는 오른쪽 자식으로 내려간다
- 중간 노드의 오른쪽 서브트리는 기존 부모의 왼쪽 서브트리로 이동한다
RL (Right Left)
- 불균형 노드의 균형 인수: -2
- 그 오른쪽 자식의 균형 인수: +1
- 오른쪽 자식의 왼쪽 서브트리에 삽입되어 발생
→ RL 케이스 → Right Rotation + Left Rotation
처리 순서
- 오른쪽 자식을 기준으로 Right Rotation (오른쪽 회전)
- 이후 부모를 기준으로 Left Rotation (왼쪽 회전)
과정
1단계 (부분 회전)
- 오른쪽 자식의 왼쪽 자식이 위로 올라온다
- 기존 오른쪽 자식은 그 오른쪽 자식으로 내려간다
- 올라온 노드의 오른쪽 서브트리는 기존 오른쪽 자식의 왼쪽 서브트리로 이동한다
→ RR 형태로 변환된다
2단계 (전체 회전)
- 중간 노드가 새로운 부모가 된다
- 기존 부모는 왼쪽 자식으로 내려간다
- 중간 노드의 왼쪽 서브트리는 기존 부모의 오른쪽 서브트리로 이동한다
트리 회전과 서브트리 재배치
회전은 단순한 부모-자식 교체가 아니다.
회전은 서브트리까지 포함한 구조 재배치이다.
핵심
- BST 조건 유지
- 왼쪽 서브트리의 값 < 부모 노드의 값 < 오른쪽 서브트리의 값
- 중간 값 범위를 담당하는 서브트리를 올바른 위치로 이동시켜야 한다
예시: Right Rotation
기준 노드를 A, 그 왼쪽 자식을 B, B의 오른쪽 서브트리를 T2라고 하자.
- 회전 전: A의 왼쪽 자식이 B이고, B의 오른쪽 서브트리가 T2이다
- 회전 후: B가 부모가 되고, A는 B의 오른쪽 자식이 되며, T2는 A의 왼쪽 서브트리로 이동한다
즉,
- B의 오른쪽 서브트리(T2)는 A의 왼쪽 서브트리로 이동한다
이렇게 해야 B < T2 < A 관계를 유지할 수 있다.
질문 리스트
- BST의 시간 복잡도는 어떻게 되나요?
- BST가 최악의 경우 O(N)이 되는 이유는 무엇인가요?
- AVL 트리는 왜 필요한가요?
- AVL 트리의 균형 조건은 무엇인가요?
- Balance Factor란 무엇인가요?
- AVL 트리에서 회전이 필요한 이유는 무엇인가요?
- AVL 트리의 회전 종류에는 어떤 것들이 있나요?
- AVL 트리의 삽입 과정에서 어떤 경우에 어떤 회전이 발생하나요?
- AVL 트리의 단점은 무엇인가요?
- AVL 트리와 레드-블랙 트리의 차이점은 무엇인가요?
고난이도 / 꼬리 질문
- AVL 트리에서 높이는 최악의 경우 얼마까지 증가할 수 있나요?
- AVL 트리의 최소 노드 수와 높이의 관계를 설명할 수 있나요?
- AVL 트리의 높이가
O(log N)임을 어떻게 증명할 수 있나요? - 삽입과 삭제 중 어떤 연산이 더 복잡하고, 그 이유는 무엇인가요?
- AVL 트리에서 삭제 연산이 삽입보다 까다로운 이유는 무엇인가요?
- AVL 트리에서 한 번의 삽입에 회전이 여러 번 발생할 수 있나요?
- 반대로 삭제에서는 왜 여러 번 회전이 발생할 수 있나요?
- AVL 트리에서 Balance Factor를 매번 계산하면 비효율적인데, 이를 어떻게 최적화할 수 있나요?
- AVL 트리에서 높이를 저장하지 않고 균형을 유지할 수 있는 방법이 있을까요?
- AVL 트리와 힙(heap)의 구조적 차이와 사용 목적 차이는 무엇인가요?
- “균형을 유지하는 것”과 “탐색 성능” 사이에는 어떤 트레이드오프가 있나요?
- AVL 트리는 항상 완전 이진 트리인가요? 아니라면 차이는 무엇인가요?
- AVL 트리의 회전을 실제 코드 레벨에서 구현할 때 가장 실수하기 쉬운 부분은 어디인가요?
- 재귀 없이 AVL 트리를 구현하려면 어떤 점이 어려워지나요?
- AVL 트리를 배열 기반으로 구현할 수 있을까요? 가능하다면 어떤 문제가 생기나요?
- 실무에서 AVL보다 레드-블랙 트리를 더 많이 쓰는 이유를 성능 관점에서 설명해보세요
- 만약 데이터가 계속 정렬된 상태로 들어온다면 AVL 트리는 어떤 비용을 계속 지불하게 되나요?
- AVL 트리의 회전이 캐시 효율 측면에서는 어떤 영향을 줄 수 있나요?
- 멀티스레드 환경에서 AVL 트리를 사용할 때 어떤 문제가 발생할 수 있나요?