다음 데이터를 이용하여 AVL 트리를 생성할 때, 이에 대한 설명으로 … | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 12년 1회차
다음 데이터를 이용하여 AVL 트리를 생성할 때, 이에 대한 설명으로 옳지 않은 것은?
12, 11, 10, 5, 3, 7, 6, 1, 13, 2, 4
1
AVL트리에서 7을 검색하기 위해서는 4번의 비교가 필요하다.
2
AVL트리의 루트 값은 5이다.
3
4가 삽입될 때, AVL 트리의 균형이 깨져서 재구성이 발생한다.
4
6은 리프노드이다.
해설

완성된 AVL 트리에서 7은 5 → 10 → 7 순으로 세 번 비교로 찾으므로, 네 번의 비교가 필요하다는 설명이 옳지 않다.

삽입 중 회전: 10 삽입 시 LL(루트 11) → 3 삽입 시 LL(노드 10 기준) → 7 삽입 시 LR(루트 10) → 13 삽입 시 RR(노드 11 기준) → 2 삽입 시 LR(노드 3 기준) → 4 삽입 시 루트 10에서 LL 회전이 일어나 루트가 5가 된다.

최종 트리: 5의 왼쪽 2(자식 1, 3), 3의 오른쪽 4 / 5의 오른쪽 10(자식 7, 12), 7의 왼쪽 6, 12의 자식 11, 13.

  • 최종 루트 값은 5이다 — 옳다.
  • 4를 넣으면 루트 10의 균형인수가 2가 되어 재구성이 발생한다 — 옳다.
  • 6은 7의 왼쪽 자식이며 자식이 없는 리프노드이다 — 옳다.

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

이어서 풀어보기

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