다음과 같이 6개의 키값으로 구성된 4개의 입력 배열 데이터 (가)～(… | [7급 국가직 자료구조론] 26년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 26년 1회차
다음과 같이 6개의 키값으로 구성된 4개의 입력 배열 데이터 (가)～(라)를 각각 순서대로 삽입하여 4개의 AVL 트리를 생성하였다. 생성된 모든 트리에 공통으로 존재하는 리프 노드 키값으로 옳은 것은?
(가) 4 1 2 8 5 9 (나) 1 2 8 5 9 4 (다) 9 8 4 2 1 5 (라) 9 8 1 5 4 2
1
2
2
4
3
5
4
9
해설
네 AVL 트리에 공통인 리프 키는 9이다.
각각 삽입·회전을 추적한 결과다(루트(왼쪽, 오른쪽) 형식).
(가): 5(2(1, 4), 8(−, 9)) → 리프 1, 4, 9
(나): 5(2(1, 4), 8(−, 9)) → 리프 1, 4, 9
(다): 4(2(1, −), 8(5, 9)) → 리프 1, 5, 9
(라): 4(1(−, 2), 8(5, 9)) → 리프 2, 5, 9네 트리 모두에 리프로 남는 키는 9뿐이다.
- 2는 (라)에서만 리프이고 나머지에서는 내부 노드다.
- 4는 (가)·(나)에서는 리프지만 (다)·(라)에서는 루트다.
- 5는 (다)·(라)에서는 리프지만 (가)·(나)에서는 루트다.
오류나 개정된 내용이 보이면 알려주세요