다음의 키 값을 가지는 7개의 데이터를 순서대로 삽입하여 AVL 트리를… | [7급 국가직 자료구조론] 20년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 20년 1회차
다음의 키 값을 가지는 7개의 데이터를 순서대로 삽입하여 AVL 트리를 구성한 후 후위 순회를 수행하였다. 방문 노드들의 키 값을 방문 순서대로 바르게 나열한 것은?
10, 4, 7, 12, 3, 13, 15
1
3, 4, 10, 15, 13, 12, 7
2
3, 7, 4, 12, 15, 13, 10
3
3, 7, 4, 15, 13, 12, 10
4
3, 10, 13, 15, 4, 12, 7
해설

후위 순회 결과는 3, 4, 10, 15, 13, 12, 7이다.

10, 4, 7 삽입 시 LR 불균형이 생겨 7이 루트(왼쪽 4, 오른쪽 10)가 된다. 12, 3을 넣은 뒤 13을 넣으면 10에서 RR 불균형이 생겨 회전 후 12(왼쪽 10, 오른쪽 13)가 7의 오른쪽 자식이 된다.

마지막 15는 13의 오른쪽에 붙고 모든 노드의 균형 인수가 −1~1 범위라 회전이 없다. 이 트리를 왼쪽 → 오른쪽 → 루트 순으로 방문한다.

  • 3, 7, 4, 12, 15, 13, 10: 회전 후 루트는 7이므로 마지막 방문 노드가 10일 수 없다.
  • 3, 7, 4, 15, 13, 12, 10: 회전 없이 일반 이진 탐색 트리로 삽입했을 때의 결과이다.
  • 3, 10, 13, 15, 4, 12, 7: 리프 3 다음에는 그 부모 4를 방문해야 하는데 10이 먼저 온다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 20년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기