키 값 <2, 6, 3, 4, 5, 1, 7, 8>을 순서대… | [7급 국가직 자료구조론] 24년 1회차 기출문제 상세 페이지

단일 회전은 1회, 이중 회전은 2회 발생한다.
빨강으로 삽입한 노드의 부모가 빨강일 때, 삼촌이 빨강이면 색 변경만 하고 삼촌이 검정(NIL 포함)이면 회전한다. 삽입 노드·부모·조부모가 일직선이면 단일 회전, 꺾여 있으면 이중 회전이다.
3 삽입: 2 → 6(오른쪽) → 3(왼쪽)으로 꺾이고 삼촌이 없어 이중 회전, 3이 루트가 된다.
4 삽입: 부모 6과 삼촌 2가 모두 빨강이라 색 변경만 한다.
5 삽입: 6 → 4(왼쪽) → 5(오른쪽)로 꺾이고 삼촌이 없어 이중 회전, 5가 4와 6의 부모가 된다.
1·7 삽입: 1은 부모가 검정이라 그대로, 7은 삼촌 4가 빨강이라 색 변경만 한다.
8 삽입: 6 → 7 → 8이 오른쪽 일직선이고 삼촌이 없어 단일 회전한다.
단일 1회·이중 1회로 보면 5 삽입 때의 꺾인 배치에서 일어나는 이중 회전을 빠뜨린 것이다.
단일 2회·이중 1회로 보면 색 변경만으로 해결되는 삽입을 회전으로 센 것이고, 이중 회전도 하나 빠졌다.
단일 2회·이중 2회로 보면 4나 7 삽입처럼 삼촌이 빨강인 경우를 회전으로 센 것이다.