다음과 같은 순서로 입력되는 데이터에 대해 올바르게 AVL-트리를 구성… | [7급 국가직 자료구조론] 07년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 07년 1회차
다음과 같은 순서로 입력되는 데이터에 대해 올바르게 AVL-트리를 구성한 것은?
AFECBD
1
2
3
4
해설

A, F, E, C, B, D를 차례로 넣으면 최종 AVL 트리는 루트 C, 왼쪽 B(자식 A), 오른쪽 E(자식 D·F)가 된다.

A, F, E 삽입 시 A에서 RL 불균형이 생겨 E가 루트(A, F)가 된다. C를 A의 오른쪽에 넣고 B를 넣으면 A에서 다시 RL 불균형이 생겨 B가 A·C의 부모가 된다.

마지막 D가 C의 오른쪽에 붙으면 루트 E의 왼쪽 높이가 3, 오른쪽이 1이 되어 LR 회전으로 C가 루트로 올라가고, D는 E의 왼쪽 자식이 된다.

  • 루트 D, 왼쪽 B(A, C), 오른쪽 F(자식 E)인 트리는 균형은 맞지만 삽입·회전 과정에서 D가 루트로 오지 않는다.
  • 루트 C, 왼쪽 A(오른쪽 자식 B)인 트리는 LR 회전 뒤에도 B가 왼쪽 자식 A를 유지한다는 점과 맞지 않는다.
  • 루트 D, 오른쪽 E 아래 F만 있는 트리도 D가 루트가 되는 회전이 일어나지 않으므로 결과가 아니다.

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

이어서 풀어보기

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