공백 AVL 트리에 데이터를 순서대로 삽입하여 AVL 트리를 구성할 때… | [7급 국가직 자료구조론] 18년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 18년 1회차
공백 AVL 트리에 데이터를 순서대로 삽입하여 AVL 트리를 구성할 때, 나머지와 다른 모습의 AVL 트리가 구성되는 데이터 키(key)들의 순서는?
1
3, 4, 6, 5, 7, 8
2
5, 4, 7, 3, 6, 8
3
7, 5, 8, 6, 4, 3
4
8, 7, 5, 4, 6, 3
해설

나머지와 다른 AVL 트리가 만들어지는 순서는 3, 4, 6, 5, 7, 8이다.

3, 4, 6 삽입 시 RR 회전으로 4가 루트가 되고, 5와 7을 넣은 뒤 8을 넣으면 루트 4에서 다시 불균형이 생겨 RR 회전이 일어난다. 결과는 루트 6, 왼쪽 4(자식 3, 5), 오른쪽 7(오른쪽 자식 8)이다.

나머지 세 순서는 모두 루트 5, 왼쪽 4(왼쪽 자식 3), 오른쪽 7(자식 6, 8)인 같은 트리가 된다.

  • 5, 4, 7, 3, 6, 8: 회전 없이 바로 위 모양이 된다.
  • 7, 5, 8, 6, 4, 3: 7(5(4, 6), 8)에서 3을 넣으면 루트 7에서 LL 불균형이 생기고, 오른쪽 회전으로 5가 루트가 된다.
  • 8, 7, 5, 4, 6, 3: 8, 7, 5에서 LL 회전으로 7(5, 8)이 되고, 4, 6, 3을 넣은 뒤 다시 LL 회전으로 5가 루트가 된다.

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

이어서 풀어보기

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