다음과 같은 키 값을 갖는 데이터들을 순서대로 삽입하여 AVL 트리를 … | [7급 국가직 자료구조론] 10년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 10년 1회차
다음과 같은 키 값을 갖는 데이터들을 순서대로 삽입하여 AVL 트리를 구성했을 때, 이 트리에서 각 키를 탐색하기 위한 평균 비교횟수는?8, 12, 23, 9, 7, 6
1
2
3
4
해설
평균 비교횟수는 이다.
8, 12, 23을 넣으면 8에서 RR 불균형이 생겨 좌회전으로 12가 루트가 된다. 이어 9, 7을 넣으면 루트 12, 왼쪽 8(자식 7, 9), 오른쪽 23이 된다.
6을 넣으면 루트 12에서 LL 불균형이 생겨 우회전하고, 최종 트리는 루트 8, 왼쪽 7(왼쪽 자식 6), 오른쪽 12(자식 9, 23)이다.
비교횟수(깊이)는 8이 1, 7과 12가 2, 6·9·23이 3이다.
오류나 개정된 내용이 보이면 알려주세요