다음 AVL 트리에 대해 노드 4, 5, 6을 차례대로 삽입한 결과는?… | [7급 국가직 알고리즘] 24년 1회차 기출문제 상세 페이지

삽입 결과는 루트 7, 왼쪽 2(자식 1과 5, 5의 자식 4·6), 오른쪽 8(오른쪽 자식 9)인 트리이다.
4는 7의 왼쪽에 들어가 루트 8의 왼쪽 높이가 오른쪽보다 2 커지고, 경로가 왼쪽→오른쪽이므로 LR 이중 회전으로 7이 루트가 되어 7(2(1, 4), 8(-, 9))이 된다.
5는 4의 오른쪽에 들어가도 균형이 유지된다. 6이 5의 오른쪽에 들어가면 노드 4에서 RR 불균형이 생겨 좌회전 한 번으로 5(4, 6)이 된다.
루트가 6인 트리: 노드 7의 오른쪽에 9, 그 왼쪽에 8이 매달려 7의 좌우 높이 차가 2가 되므로 AVL 트리가 아니다.
루트 7의 왼쪽 자식이 5인 트리: 6 삽입 때 불균형은 노드 4에서만 생기므로 2가 5 아래로 내려가는 회전은 일어나지 않는다.
루트가 4인 트리: 4를 삽입할 때 LR 회전으로 루트가 7이 되며, 이후 삽입에서 루트가 다시 바뀌지 않는다.