다음은 알파벳 문자열을 키값으로 저장하는 AVL트리이다. 이 트리에서 … | [7급 국가직 자료구조론] 09년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 09년 1회차
다음은 알파벳 문자열을 키값으로 저장하는 AVL트리이다. 이 트리에서 데이터 ‘JAN’을 삽입한 결과로 옳은 것은?

문제 이미지
1
2
3
4
해설

JAN 삽입 후 LR 회전이 일어나 MAR가 새 루트가 되고, 왼쪽에 AUG(자식 APR, JAN), 오른쪽에 MAY(오른쪽 자식 NOV)가 오는 트리가 옳다.

JAN은 MAY보다 작고 AUG보다 크며 MAR보다 작으므로 MAR의 왼쪽 자식으로 들어간다. 이때 MAY의 왼쪽 높이는 3, 오른쪽 높이는 1이 되어 균형인수가 +2가 되고, 삽입 위치가 왼쪽 자식(AUG)의 오른쪽 서브트리이므로 LR 불균형이다.

LR 회전은 AUG를 중심으로 왼쪽 회전한 뒤 MAY를 중심으로 오른쪽 회전하는 것으로, 중간값인 MAR가 위로 올라가고 MAR의 왼쪽 자식 JAN은 AUG의 오른쪽 자식으로 옮겨진다.

  • MAR의 왼쪽에 JAN만 붙이고 루트를 MAY로 둔 트리: 이진 탐색 순서는 맞지만 MAY의 균형인수가 +2로 AVL 조건을 위반한다.
  • JAN을 NOV의 왼쪽 자식으로 둔 트리: JAN은 MAY보다 작으므로 오른쪽 서브트리에 올 수 없어 탐색 순서가 깨진다.
  • JAN을 APR의 오른쪽 자식으로 둔 트리: JAN은 AUG보다 크므로 AUG의 왼쪽 서브트리에 올 수 없고, 균형도 깨진다.

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

이어서 풀어보기

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