데이터 <1, 3, 5, 7, 8, 10, 9>를 차례대로 … | [7급 국가직 자료구조론] 21년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 21년 1회차
데이터 <1, 3, 5, 7, 8, 10, 9>를 차례대로 하나씩 입력받아 이진 탐색 트리와 AVL 트리를 각각 만들었을 때, 두 트리 간의 높이 차는?
1
1
2
2
3
3
4
4
해설
두 트리의 높이 차는 4이다. 거의 정렬된 순서로 넣으면 이진 탐색 트리는 한쪽으로 치우치지만, AVL 트리는 회전으로 균형을 유지한다.
이진 탐색 트리: 1→3→5→7→8→10이 오른쪽으로 이어지고 9는 10의 왼쪽 자식이 되어 높이 7(루트 높이 1 기준)이다.
AVL 트리: 5 삽입 시 1에서, 8 삽입 시 5에서, 10 삽입 시 3에서 각각 RR 회전하고, 9 삽입 시 8에서 RL 회전한다. 최종 형태는 루트 7, 왼쪽 3(1, 5), 오른쪽 9(8, 10)로 높이 3이다.
따라서 높이 차는 이다.
오류나 개정된 내용이 보이면 알려주세요