레드-블랙(red-black) 트리는 모든 노드의 색상이 레드 또는 블… | [7급 국가직 자료구조론] 14년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 14년 1회차
레드-블랙(red-black) 트리는 모든 노드의 색상이 레드 또는 블랙인 이진 탐색 트리이다. 키 값 7, 3, 6, 2, 1, 8, 4를 차례대로 삽입하여 레드-블랙 트리를 만들었을 때, 레드 링크로 연결된 노드 쌍이 아닌 것은? (단, 레드 링크는 레드 자식 노드를 가리키는 링크이다)
1
(1, 2)
2
(2, 6)
3
(3, 4)
4
(7, 8)
해설
레드 링크로 연결되지 않은 쌍은 (1, 2)이다.
7, 3, 6, 2, 1, 8, 4를 차례로 삽입하면 루트 6(블랙), 왼쪽 자식 2(레드)와 그 자식 1·3(블랙), 3의 오른쪽 자식 4(레드), 오른쪽 자식 7(블랙)과 그 오른쪽 자식 8(레드)이 된다.
6 삽입 때 이중 회전으로 6이 루트가 되고, 1 삽입 때 2를 중심으로 회전하며, 4 삽입 때 삼촌 1이 레드여서 색 변환으로 2는 레드, 1·3은 블랙이 된다.
- (2, 6): 2가 레드이므로 6에서 2로 가는 링크는 레드이다.
- (3, 4): 4가 레드이므로 레드 링크이다.
- (7, 8): 8이 레드이므로 레드 링크이다.
오류나 개정된 내용이 보이면 알려주세요