비어있는 레드 블랙 트리(red black tree)에 차례대로 키(k… | [7급 국가직 자료구조론] 22년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 22년 1회차
비어있는 레드 블랙 트리(red black tree)에 차례대로 키(key) 값 1, 3, 2, 4, 5, 6을 넣고 완성한 레드 블랙 트리를 전위 순회한 결과는? (단, 키를 저장하고 있는 노드만 순회하고, 순회 결과에서 키 값 뒤에 B를 붙이면 블랙 노드, R을 붙이면 레드 노드임을 나타낸다)
1
2B, 1B, 4R, 3B, 5B, 6R
2
2B, 1R, 4R, 3B, 5B, 6R
3
4B, 2R, 1B, 3B, 5B, 6R
4
4B, 2R, 1B, 3R, 5B, 6R
해설
완성된 레드 블랙 트리의 전위 순회는 2B, 1B, 4R, 3B, 5B, 6R이다.
1(B), 3(R) 삽입 후 2를 넣으면 부모 3이 레드이고 삼촌이 없어 회전(오른쪽 후 왼쪽)하여 2B(1R, 3R)가 된다.
4 삽입 시 부모 3과 삼촌 1이 모두 레드라 색 변경: 1B, 3B, 루트 2는 블랙 유지.
5 삽입 시 부모 4는 레드, 삼촌이 없어 3에서 왼쪽 회전 → 4B(3R, 5R).
6 삽입 시 부모 5와 삼촌 3이 레드라 색 변경 → 3B, 5B, 4R.최종 트리는 루트 2B, 왼쪽 1B, 오른쪽 4R(자식 3B·5B), 5B의 오른쪽 6R이다.
- 2B, 1R, 4R, 3B, 5B, 6R: 4 삽입 때 색 변경으로 1은 블랙이 된다.
- 4B, 2R, 1B, 3B, 5B, 6R: 루트가 바뀌는 회전은 2 삽입 때뿐이라 루트는 2로 유지된다.
- 4B, 2R, 1B, 3R, 5B, 6R: 루트가 2이고, 3은 마지막 색 변경에서 블랙이 된다.
오류나 개정된 내용이 보이면 알려주세요