다음 AVL 트리에 정수 23을 삽입하면 AVL 트리로서의 균형이 깨진… | [7급 국가직 자료구조론] 16년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 16년 1회차
다음 AVL 트리에 정수 23을 삽입하면 AVL 트리로서의 균형이 깨진다. 회전을 통해 이 트리를 AVL 트리로 변환한 후에 전위 순회(preorder traversal)를 수행하였을 때 노드 방문 순서는?
문제 이미지
1
30, 19, 7, 23, 41, 27
2
30, 7, 19, 23, 27, 41
3
27, 19, 7, 23, 30, 41
4
27, 19, 7, 30, 23, 41
해설

23을 삽입한 뒤 LR 회전으로 균형을 맞추면 전위 순회 결과는 27, 19, 7, 23, 30, 41이다.

23은 30의 왼쪽, 19의 오른쪽, 27의 왼쪽 자식으로 삽입된다. 이때 30의 균형 인수가 +2(왼쪽 높이 3, 오른쪽 높이 1)이고 그 왼쪽 자식 19의 균형 인수가 -1이므로 LR 불균형이다.

회전 결과 27이 루트가 되고, 왼쪽에 19(자식 7, 23), 오른쪽에 30(오른쪽 자식 41)이 놓인다. 이를 루트→왼쪽→오른쪽 순으로 방문한다.

  • 30, 19, 7, 23, 41, 27: 루트가 30으로 그대로 남아 있어 회전으로 균형을 복구한 트리의 순회가 아니다.
  • 30, 7, 19, 23, 27, 41: 역시 루트가 30으로 남아 있고, 전위 순회라면 7보다 부모인 19가 먼저 나와야 한다.
  • 27, 19, 7, 30, 23, 41: 23은 27보다 작아 27의 왼쪽 서브트리(19의 오른쪽 자식)에 있으므로 30보다 먼저 방문되어야 한다.

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

이어서 풀어보기

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