AVL 트리 기출 질문입니다. (그림 추가)

[외뿔고래]

안녕하세요

선생님의 2020년 전산직 7급 기출책을 보며 공부하고 있습니다.

책에서 2012년 6번 과 2016년 6번 문제에서 AVL 트리 회전이 상이하여 질문드립니다.

먼저 2012년 6번 문제에서 12, 11, 10, 5, 3, 7 까지 삽입되는 단계에서 root를 포함하여 LR 회전이 발생합니다.

배열로 표현해볼게요

마지막 3까지 삽입한 상태의 배열은 11, 5, 12, 3, 10이 되고 7을 삽입하면 균형이 깨지게 됩니다.

여기서 11, 5, 10 이 LR 회전이 되면 10이 root 가 되고 root의 왼쪽 자식은 5, root의 오른쪽 자식이 12가 됩니다.

11은 12의 왼쪽 자식으로 들어가게 되는데요

2016년 6번의 경우를 보면

배열로 표기시 30, 19, 41, 7, 27 상태에서 23을 삽입하면 균형이 깨지게 되고

30, 19, 27이 LR 회전을 하면서 27이 root가 되고 root의 왼쪽 자식은 19이고, root의 오른쪽 자식은 30이 됩니다.

위와는 달리 원래 root의 오른쪽 자식인 41은 30의 오른쪽 자식으로 이동하게 됩니다.

교재의 풀이가 위 두 상황에서 다르게 처리가 되는데요

어느쪽이 맞는 것인지 궁금합니다.

[행복이]

[홍재연]

2012년 6번 문제는 LR 회전이 아니고 LL 회전인데요.

[외뿔고래]

행복이님 그림 올려주셔서 감사합니다.
그런데 교재에서는 다르게 풀이가 되어 있어요

홍재연 선생님 2012년6번의 마지막 단계가 아니라
12,11,10,5,3,7 까지 삽입된 상태에 대한 질문입니다.
그림을 열심히 그려봤습니다. 다시 한번 봐주세요.

[잔다]

Avl 은 이진탐색트리 입니다 회전시 분리 되었다가 재결합시 이진탐색 처럼 크면 오른쪽 작으면 왼쪽 입니다
그리구 중위순회하면 오름차순이죠

[홍재연]

다시 적습니다.
먼저 본인이 그린 그림에서 아래는 맞고 위는 틀렸습니다.

제가 그린 것은 본인이 그린 것처럼 그린 것이 아닙니다.
중간 과장이 없이 마지막 4가 입력되는 시점을 기준으로 그려져 있어서 본인이 혼란스러워 하는 것 같습니다.

[홍재연]

위에서
회전 대상은 (11, 5, 10)이므로
잘 아다시피 본인이 그린 것처럼 회전하면 틀린 것 아닌가요?

[홍재연]

그러면,
왜 교재에 그렇게 되어 있느냐? 입니다.

교재에 그런 모습으로 되어 있는 것은 13이 입력된 후에 모습입니다.