다음 8개의 데이터를 순서대로 삽입하여 AVL 트리를 구성하였을 때, … | [7급 국가직 자료구조론] 25년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 25년 1회차
다음 8개의 데이터를 순서대로 삽입하여 AVL 트리를 구성하였을 때, 이에 대한 설명으로 옳은 것은?19, 7, 10, 15, 25, 32, 17, 5
1
루트 노드의 번호는 17이다.
2
중위 순회했을 때 네 번째 방문하는 노드의 번호는 15이다.
3
전위 순회했을 때 세 번째 방문하는 노드의 번호는 10이다.
4
후위 순회했을 때 다섯 번째 방문하는 노드의 번호는 32이다.
해설
완성된 AVL 트리를 중위 순회하면 네 번째로 방문하는 노드는 15이다.
10 삽입: 19-7-10의 LR 불균형 → 10을 루트로 회전 (왼쪽 7, 오른쪽 19)
32 삽입: 루트 10의 오른쪽이 2 더 높은 RR 불균형 → 10 기준 좌회전으로 19가 루트가 된다.
17, 5 삽입 후에는 균형이 유지된다.최종 트리: 루트 19, 왼쪽 10(자식 7, 15), 오른쪽 25(오른쪽 자식 32), 7의 왼쪽 5, 15의 오른쪽 17
중위: 5, 7, 10, 15, 17, 19, 25, 32
- 루트 노드는 17이 아니라 19이다.
- 전위 순회(19, 10, 7, 5, 15, 17, 25, 32)의 세 번째 노드는 7이다.
- 후위 순회(5, 7, 17, 15, 10, 32, 25, 19)의 다섯 번째 노드는 10이다.
오류나 개정된 내용이 보이면 알려주세요