Selection Tree

여러 개의 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 decreasing: Item을 내림차순으로 정렬한 후 bin들 중 공간이 item에 가장 딱 맞을 만큼 남은 bin에 item을 채우고 안되면 새로운 bin 사용. 공간이 가장 적절하게 남은 bin을 찾기위해 Selection Tree 사용

최적 값과의 비교