소프트웨어
-
[2019 5급 공무원 2차] 자료구조론 제 5문알고리즘 2020. 6. 24. 16:16
2019년 국가공무원 5급 [기술] 공개경쟁채용 제 2차 시험 제 5문 제 5 문. 선택 트리(selection tree)는 완전 이진 트리(complete binary tree)를 사용하여 토너먼트 경기 방식을 통해 트리를 구축하는 자료구조로서 승자 트리(winner tree)와 패자 트리(loser tree)가 있다. 선택 트리를 사용하여 키 값이 가장 작은 원소를 선택한다고 할 때, 승자 트리에서는 형제 노드끼리 값을 비교하여 값이 작은 원소가 승자가 되어 부모 노드로 복사된 다음 토너먼트 경쟁을 계쏙하는 반면, 패자 트리에서는 키 값이 큰 패자는 부모 노드에 복사되고, 키 값이 작은 승자는 그 위 부모 노드로 올라가서 다시 토너먼트 경쟁을 계속 하는 형태로 트리를 구성한다. 따라서 승자 트리에서는..