다음과 같은 키 값을 갖는 데이터들을 순서대로 삽입하여 AVL 트리를 … | [7급 국가직 자료구조론] 10년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 10년 1회차
다음과 같은 키 값을 갖는 데이터들을 순서대로 삽입하여 AVL 트리를 구성했을 때, 이 트리에서 각 키를 탐색하기 위한 평균 비교횟수는?
8, 12, 23, 9, 7, 6
1
146\frac{14}{6}
2
156\frac{15}{6}
3
166\frac{16}{6}
4
176\frac{17}{6}
해설

평균 비교횟수는 146\dfrac{14}{6}이다.

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이다.
1+2+2+3+3+36=146\dfrac{1+2+2+3+3+3}{6}=\dfrac{14}{6}

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

이어서 풀어보기

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