Selection Tree
-
Selection Tree자료구조 2019. 9. 2. 18:12
여러 개의 list에서 가장 작은 값이나 가장 큰 값을 찾을 때 사용 리프는 각 list의 첫번째 값들. Winner Tree - Tournament의 승자를 node에 기록. root node는 트리에서 가장 작은 값 최종 승자는 승자가 속해있던 list의 다음 값으로 교체되고 재실행 Loser Tree - Tournament의 패자를 node에 기록 K-way merge sorting이나 Bin Packing 문제 해결에 적용됨 Bin Packing에서 Best Fit decreasing알고리즘에 Selection Tree가 사용됨 First Fit decreasing: Item을 내림차순으로 정렬한 후 첫번째부터 남는 공간이 있는 bin에 item을 채우고 안되면 새로운 bin 사용 Best Fit..