다음 데이터를 순서대로 삽입하여 불균형이 발생했을 때 회전 연산을 수행… | [7급 국가직 알고리즘] 25년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 25년 1회차
다음 데이터를 순서대로 삽입하여 불균형이 발생했을 때 회전 연산을 수행하여 균형 상태를 유지하는 AVL 트리를 구성하였다. 구성된 AVL 트리에서 단말 노드(leaf node)에 해당하는 값만을 모두 고르면?50, 60, 70, 90, 80, 75, 73, 72, 78
1
72, 73, 90
2
72, 75, 90
3
50, 73, 75, 90
4
50, 72, 78, 90
해설
최종 AVL 트리의 단말 노드는 50, 72, 78, 90이다.
50·60·70 삽입 후 RR 회전으로 60이 루트가 되고, 90·80 삽입 시 70에서 RL 회전으로 80(70, 90)이 된다. 75 삽입 시 루트 60에서 RL 회전이 일어나 70(60(50), 80(75, 90))이 된다.
73·72 삽입 시 75에서 LL 회전으로 73(72, 75)이 되고, 78 삽입 시 80에서 LR 회전이 일어나 최종 트리는 70(60(50), 75(73(72), 80(78, 90)))이다.
- 72, 73, 90은 73이 72를 자식으로 가진 내부 노드라서 틀렸다.
- 72, 75, 90은 75가 회전 후 서브트리의 루트가 되는 내부 노드이며 단말인 50·78도 빠졌다.
- 50, 73, 75, 90은 73과 75가 모두 자식을 가진 내부 노드라서 틀렸다.
오류나 개정된 내용이 보이면 알려주세요