승자 트리는 단말 노드(leaf node)에서부터 시작해서, 가장 작은… | [7급 국가직 자료구조론] 21년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 21년 1회차
승자 트리는 단말 노드(leaf node)에서부터 시작해서, 가장 작은 키 값을 갖는 노드(승자)를 찾아 부모로 올려서 루트 노드로부터 가장 작은 값을 찾아내는 방식이다. 승자 트리의 단말 노드에는 정렬된 배열(run)이 각각 달려 있고, 이 run에서 첫 번째 값을 읽어 가장 작은 값을 올려 내는 방식으로 모든 run을 비우면서 값을 정렬하게 된다. 8개의 run이 있는 아래 승자 트리에서 6, 8, 9 순서대로 3개의 레코드를 출력하고 난 뒤 run이 생략된 승자 트리의 형태로 옳은 것은?
1
[그림]
2
[그림]
3
[그림]
4
[그림]
해설
3개 출력 후의 승자 트리는 루트 10, 둘째 레벨 10·11, 셋째 레벨 10·15·11·17, 단말 10·20·20·15·11·12·90·17인 형태이다.
값이 출력된 단말은 자기 run의 다음 값으로 교체된다. 6이 나간 자리는 15, 8이 나간 자리는 11, 9가 나간 자리는 12가 되고, 나머지 단말은 그대로이다.
형제끼리 작은 값을 올리면 min(10,20)=10, min(20,15)=15, min(11,12)=11, min(90,17)=17, 다음 레벨은 10과 11, 루트는 10이 된다.
- 루트가 11이고 첫 단말이 17인 트리: 단말 10은 아직 출력되지 않았으므로 17로 바뀔 수 없다.
- 루트 10에 다섯째 단말이 13인 트리: 8이 나간 run의 다음 값은 13이 아니라 11이다.
- 루트 12에 다섯째 단말이 16인 트리: 단말 10이 남아 있어야 하고, 11은 아직 출력되지 않았다.
오류나 개정된 내용이 보이면 알려주세요