다음 데이터를 차례대로 하나씩 입력받아 AVL 트리를 생성할 때, 필요… | [7급 국가직 자료구조론] 22년 1회차 기출문제 상세 페이지

회전은 RR회전, LL회전, LR회전 순서로 일어난다.
6, 7, 8 삽입 시 6에서 오른쪽-오른쪽으로 치우쳐 RR회전 → 루트 7, 자식 6·8.
2, 1 삽입 시 6에서 왼쪽-왼쪽으로 치우쳐 LL회전 → 7의 왼쪽이 2(자식 1·6).
5는 6의 왼쪽에 붙어 루트 7의 왼쪽 높이 3, 오른쪽 높이 1이 되고 경로가 왼쪽-오른쪽이므로 LR회전 → 루트 6, 왼쪽 2(자식 1·5), 오른쪽 7(오른쪽 자식 8). 마지막 4는 5의 왼쪽에 붙지만 모든 노드의 균형 인수가 ±1 이내라 회전이 없다.
LL회전, LR회전, LR회전: 처음 6, 7, 8은 오른쪽으로 치우치므로 첫 회전은 RR이다.
LL회전, LR회전, RL회전: 첫 회전이 RR이어야 하고 4 삽입 때는 회전이 없다.
RR회전, LL회전, RL회전: 5의 삽입 경로는 왼쪽 후 오른쪽이므로 RL이 아니라 LR이다.