다음 정수들을 순서대로 삽입하여 AVL트리를 구성하였다. AVL트리의 … | [7급 국가직 자료구조론] 13년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 13년 1회차
다음 정수들을 순서대로 삽입하여 AVL트리를 구성하였다. AVL트리의 구성 과정 중에 사용된 회전방법들로 옳은 것은?
20, 16, 15, 9, 7, 12, 10, 1, 13, 5
1
LL 회전, RR 회전, RL 회전
2
RR 회전, RL 회전
3
LL 회전, LR 회전
4
LL 회전, LR 회전, RL 회전
해설

구성 과정에서 LL 회전과 LR 회전만 사용된다.

20, 16, 15 삽입 시 20에서 LL 회전(16이 루트), 9, 7 삽입 시 15에서 LL 회전이 일어난다.

12는 루트 16의 왼쪽 자식 9의 오른쪽 서브트리로 들어가 LR 회전(15가 루트)이 일어나고, 10, 1, 13은 균형을 유지하며, 5는 7의 왼쪽 자식 1의 오른쪽으로 들어가 다시 LR 회전이 일어난다.

  • LL·RR·RL 회전: RR과 RL 불균형은 한 번도 생기지 않는다.
  • RR·RL 회전: 실제로 쓰인 LL과 LR이 모두 빠져 있다.
  • LL·LR·RL 회전: 오른쪽 자식의 왼쪽으로 치우친 RL 불균형은 생기지 않는다.

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

이어서 풀어보기

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