비어 있는 초기 상태의 이진 트리에 다섯 개의 키(1, 2, 3, 4,… | [7급 국가직 자료구조론] 25년 1회차 기출문제 상세 페이지

레드-블랙 트리는 회전과 재색칠 후에도 이진 탐색 트리 성질을 유지하므로 중위 순회 결과는 항상 오름차순인 1, 2, 3, 4, 5이다.
1(루트, 흑) → 2(적) → 3 삽입 시 적색 연속으로 좌회전해 2가 루트 → 4 삽입 시 삼촌 1이 적색이라 재색칠 → 5 삽입 시 3 기준 좌회전으로 4가 3과 5의 부모가 된다.
최종 형태: 루트 2, 왼쪽 1, 오른쪽 4(자식 3, 5)
1, 3, 5, 4, 2: 최종 트리의 후위 순회 결과다.
2, 1, 3, 5, 4: 오름차순이 아니므로 이진 탐색 트리의 중위 순회가 될 수 없다.
2, 1, 4, 3, 5: 최종 트리의 전위 순회 결과다.