다음 중 AVL 트리가 아닌 것은? | [7급 국가직 자료구조론] 08년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 08년 1회차
다음 중 AVL 트리가 아닌 것은?
1
2
3
4
해설

루트가 20이고 왼쪽 서브트리가 10-15-14로 깊어진 트리는 AVL 트리가 아니다.

AVL 트리는 모든 노드에서 왼쪽·오른쪽 서브트리 높이 차(균형 인수)가 1 이하여야 한다. 이 트리는 루트의 왼쪽 높이가 3, 오른쪽(25) 높이가 1이라 균형 인수가 2이다.

  • 루트 15, 왼쪽 10(2, 14), 오른쪽 25(20)인 트리: 모든 노드의 높이 차가 1 이하이다.
  • 루트 15에서 10의 오른쪽 자식 12 아래에 14가 붙은 트리: 10에서 높이 차 1, 루트에서 높이 차 1로 균형을 만족한다.
  • 루트 14, 왼쪽 4(2, 10(8, 12)), 오른쪽 20(15, 25)인 트리: 4에서 높이 차 1, 루트에서 높이 차 1이다.

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

이어서 풀어보기

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