다음 중 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이다.
오류나 개정된 내용이 보이면 알려주세요



