Как определить раунд по элементу в дереве (Турнирные скобки)?

Question

Предположим, у нас есть следующее дерево:

1
    9
2
        13
3
    10
4 
            15
5
    11
6 
        14
7   
    12
8

Где элементы (совпадения):
1-8 раунд 1
9-12 раунд 2
13-14 раунд 3
15 раунд 4

Как я могу определить раунд элемента "n" в дереве shuch? Мои текущие формулы:

total_rounds = floor(log(totalTeams,2));

matches_per_round = (totalTeams / pow(2, current_round))

next_match_id = (totalTeams/2) + ceil(match_id/2)

total_matches = total_teams - 1

Answer 1

Представьте, что дерево было пронумеровано в обратном порядке.

15
     7
14
         3
13 
     6
12 
             1
11
     5 
10 
         2
9   
     4
8

В этом случае это будет просто логарифм числа, округленного в меньшую сторону.Теперь мы просто вычитаем это число из числа раундов, и все готово.

reverse_number = total_matches - match_number + 1;
reverse_match_round = floor(log(reverse_number, 2));
match_round = total_rounds - match_round;

(Обратите внимание, что reverse_match_round на самом деле 0-проиндексировано, в отличие от match_round. Однако, поскольку мы вычитаем его из total_rounds, проще сохранить его таким образом, чем индексировать его 1. Если вы предпочитаете индексировать его 1, просто добавьте +1 к каждой из двух последних строк.)