일련의 키(key) 값 2, 1, 8, 9, 7, 3, 6을 가지는 7… | [7급 국가직 자료구조론] 18년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 18년 1회차
일련의 키(key) 값 2, 1, 8, 9, 7, 3, 6을 가지는 7개의 데이터를 순서대로 삽입하여 레드-블랙 트리(red-black tree)를 구성하였다. 구성된 레드-블랙 트리를 후위 순회(postorder traversal)할 경우 방문 노드들의 키 값을 방문 순서대로 바르게 나열한 것은?
1
1, 3, 6, 2, 9, 8, 7
2
1, 3, 7, 6, 9, 8, 2
3
1, 6, 3, 2, 9, 8, 7
4
1, 6, 3, 7, 9, 8, 2
해설
후위 순회 결과는 1, 3, 7, 6, 9, 8, 2이다.
2(흑, 루트)에 1, 8을 적색으로 삽입한다. 9 삽입 시 부모 8과 삼촌 1이 모두 적색이라 색 변경(1, 8 흑)하고, 7은 8의 왼쪽 적색 자식이 된다.
3 삽입 시 부모 7과 삼촌 9가 적색이라 색 변경(7, 9 흑, 8 적)한다. 6 삽입 시 부모 3은 적색, 삼촌(7의 오른쪽)은 흑색이고 꺾인 모양이므로 이중 회전을 하여 6(흑)이 3, 7(적)을 자식으로 갖는다.
최종 트리: 2(1, 8(6(3, 7), 9))
- 1, 3, 6, 2, 9, 8, 7: 루트를 7로 본 순서로, 루트 2는 회전 없이 그대로 유지된다.
- 1, 6, 3, 2, 9, 8, 7: 루트를 7로 잘못 잡았고 6과 3의 부모·자식 관계도 뒤바뀌었다.
- 1, 6, 3, 7, 9, 8, 2: 회전 없이 6을 3의 오른쪽 자식으로 둔 것으로, 이중 회전 후에는 6이 3과 7의 부모가 된다.
오류나 개정된 내용이 보이면 알려주세요