비어 있는 레드－블랙(red-black) 트리에 <19, 18, … | [7급 국가직 자료구조론] 21년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 21년 1회차
비어 있는 레드－블랙(red-black) 트리에 <19, 18, 2, 15, 6, 13, 7>을 순서대로 입력한 결과 생성되는 레드-블랙 트리로 옳은 것은? (단, 점선 노드는 레드 노드, 점선 링크는 레드 링크이며, 실선 노드는 블랙 노드, 실선 링크는 블랙 링크이고, 리프 노드에 연결된 사각형의 단말은 외부 노드를 의미한다)
1
[그림]
2
[그림]
3
[그림]
4
[그림]
해설
완성되는 트리는 루트 18(블랙), 왼쪽 6(레드)·오른쪽 19(블랙), 6의 자식 2·13(블랙), 13의 자식 7·15(레드)인 형태이다.
19, 18 삽입 후 2가 들어오면 삼촌이 없어 우회전으로 18이 루트가 된다. 15 삽입 시 삼촌 19가 레드라 색만 바꾸고, 6 삽입 시 2–15–6 꺾임을 이중 회전해 6(블랙) 아래 2·15(레드)가 된다.
13 삽입 시 삼촌 2가 레드라 재색칠로 6이 레드, 2·15가 블랙이 되고, 7 삽입 시 15–13–7 일직선이므로 15에서 우회전해 13(블랙) 아래 7·15(레드)가 된다.
- 루트가 7인 트리: 7은 마지막에 들어와 회전이 15에서만 일어나므로 루트로 올라가지 않는다.
- 루트가 13인 완전 균형 트리: 2 삽입 때 18이 루트가 된 뒤로는 루트에서 회전이 일어나지 않아 18이 끝까지 루트로 남는다.
- 루트가 15인 트리: 15를 루트로 올리는 회전이 일어나지 않으며 7은 13의 왼쪽 레드 자식이 된다.
오류나 개정된 내용이 보이면 알려주세요