다음 키(key)를 갖는 데이터들을 공백 AVL 트리에 차례대로 저장하… | [7급 국가직 자료구조론] 17년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 17년 1회차
다음 키(key)를 갖는 데이터들을 공백 AVL 트리에 차례대로 저장하였다. 생성된 AVL 트리를 T라고 할 때, 다음 설명 중에서 옳은 것은?
12, 14, 9, 16, 19, 11
1
T에 키가 25인 노드를 삽입하면 루트 노드가 바뀌게 된다.
2
T에서 키가 9인 노드를 삭제하면 T의 높이가 1 감소한다.
3
T에 키가 7인 노드를 삽입하면 T의 높이가 1 증가한다.
4
키가 9인 노드와 키가 16인 노드는 형제 노드이다.
해설

옳은 설명은 키가 9인 노드와 16인 노드가 형제라는 것이다.

12, 14, 9, 16을 넣은 뒤 19를 삽입하면 14에서 RR 불균형이 생겨 회전하고, 이어 11을 넣으면 T는 루트 12, 왼쪽 자식 9(오른쪽 자식 11), 오른쪽 자식 16(자식 14, 19)인 높이 3의 트리가 된다. 9와 16은 모두 루트 12의 자식이다.

  • 25를 삽입하는 경우: 19의 오른쪽에 붙어 루트의 균형 인수가 -1이 될 뿐 회전이 없으므로 루트는 12 그대로이다.
  • 9를 삭제하는 경우: 자식 11이 그 자리를 대신하고 12-16-14 경로가 남으므로 높이는 3 그대로이다.
  • 7을 삽입하는 경우: 9의 왼쪽에 붙어 왼쪽 서브트리 높이가 2로 유지되므로 T의 높이는 늘지 않는다.

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

이어서 풀어보기

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