Метод турниров основан на рекурсии, и с его помощью можно решать различные задачи, в которых информация, полученная в результате первого прохода по данным, может облегчить последующие проходы. Если мы воспользуемся им для поиска наибольшего значения, то он потребует построения бинарного дерева, все элементы которого являются листьями. На каждом уровне два элемента объединены в пару, причем наибольший из двух элементов копируется в родительский узел. Процесс повторяется до достижения корневого узла. Полное дерево турнира для фиксированного набора данных изображено на следующем рисунке:
 |
| Дерево турнира для набора из восьми значений |
В упражнении 1.1.3.5 упоминался алгоритм для поиска второго по величине элемента списка из N значений, требующий около N сравнений. Метод турниров поможет нам в этом. В результате всякого сравнения мы получаем «победителя» и «проигравшего». Проигравших мы забываем, и вверх по дереву двигаются только победители. Всякий элемент, за исключением наибольшего, «проигрывает» в точности в одном сравнении. Поэтому для построения дерева турнира требуется N - 1 сравнение.
Второй по величине элемент мог проиграть только наибольшему. Спускаясь по дереву вниз, мы составляем список элементов, проигравших наибольшему. Формулы для деревьев показывают, что число таких элементов не превосходит ⌈log2N⌉. Их поиск по дереву потребует ⌈log2N⌉ сравнений; еще ⌈log2N⌉ - 1 сравнений необходимо для выбора наибольшего из них. На всю работу уйдет N + 2⌈log2N⌉ - 2, т. е. O(N) сравнений.
С помощью метода турниров можно и сортировать список значений. Сортировка кучей, основана на методе турниров.
