<보기>의 AVL 트리에 5를 삽입한 후, AVL 트리의 균… | [7급 서울시 자료구조론] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 자료구조론] 26년 1회차
<보기>의 AVL 트리에 5를 삽입한 후, AVL 트리의 균형을 유지하기 위해 수행해야 하는 회전으로 가장 옳은 것은?
1
LL 회전
2
RR 회전
3
LR 회전
4
RL 회전
해설
5를 삽입하면 루트 30에서 왼쪽-왼쪽 방향으로 불균형이 생기므로 LL 회전을 수행한다.
그림의 트리는 루트 30의 왼쪽에 20(자식 10, 25), 오른쪽에 40이 있다. 5는 30→20→10을 거쳐 10의 왼쪽 자식으로 삽입된다.
삽입 후 30의 왼쪽 서브트리 높이는 3, 오른쪽은 1이 되어 균형 인수가 +2이고, 불균형 노드 30에서 삽입 위치까지 왼쪽→왼쪽으로 내려가므로 20을 축으로 오른쪽 회전하는 LL 유형이다. 회전 후 20이 루트가 되고 왼쪽에 10(자식 5), 오른쪽에 30(자식 25, 40)이 온다.
- RR 회전은 불균형 노드의 오른쪽-오른쪽에 삽입된 경우에 쓴다.
- LR 회전은 왼쪽 자식의 오른쪽 서브트리에 삽입된 경우에 쓴다.
- RL 회전은 오른쪽 자식의 왼쪽 서브트리에 삽입된 경우에 쓴다.
오류나 개정된 내용이 보이면 알려주세요
