如何在树中逐个元素确定(锦标赛括号)？

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"？

我目前的公式是:

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到最后两个中的每一个行.)