다음 데이터를 비어 있는 AVL(Adelson-Velskii, Land… | [7급 국가직 자료구조론] 23년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 23년 1회차
다음 데이터를 비어 있는 AVL(Adelson-Velskii, Landis) 트리에 순서대로 삽입할 때, 완전 이진 트리에 해당하는 것만을 모두 고른 것은?ㄱ. 1, 2, 4, 3, 6, 5
ㄴ. 2, 1, 5, 4, 6, 3
ㄷ. 3, 1, 4, 2, 5, 6
ㄹ. 4, 1, 2, 3, 6, 5
1
ㄱ, ㄴ
2
ㄱ, ㄹ
3
ㄴ, ㄷ
4
ㄷ, ㄹ
해설
완전 이진 트리가 되는 것은 ㄱ, ㄹ이다.
삽입 후 균형 인수의 절댓값이 2가 되면 회전한다. 최종 트리는 다음과 같다(괄호 안은 왼쪽, 오른쪽 자식).
- ㄱ: 1, 2, 4에서 RR 회전 → 2(1, 4), 3·6 삽입 후 5에서 루트 2가 불균형 → RR 회전 → 4(2(1, 3), 6(5, –)): 마지막 레벨이 왼쪽부터 채워져 완전 이진 트리
- ㄴ: 2(1, 5(4, 6))에 3 삽입 시 루트에서 RL 회전 → 4(2(1, 3), 5(–, 6)): 5의 왼쪽이 비고 오른쪽만 있어 완전 이진 트리가 아님
- ㄷ: 3(1(–, 2), 4(–, 5))에 6 삽입 시 4에서 RR 회전 → 3(1(–, 2), 5(4, 6)): 1의 왼쪽이 비어 완전 이진 트리가 아님
- ㄹ: 4, 1, 2에서 LR 회전 → 2(1, 4), 3·6 삽입 후 5에서 RR 회전 → 4(2(1, 3), 6(5, –)): 완전 이진 트리
오류나 개정된 내용이 보이면 알려주세요