我想维护一个记分牌，其中包含n个根据他们的分数排序的球员，我所做的是:当玩家I获得x点时(如果他不是顶级玩家)，我会将他的分数与排名在他之上的玩家的分数进行比较，并在必要时进行交换，然后重复此操作，直到我发现排名在他之上的玩家的分数大于他的分数，或者直到他到达列表的顶端。问题是它的最坏情况时间是O (n)，它能在O (log n)这样的时间内完成吗?
保持平衡的搜索树，映射玩家得分。当玩家n的分数被z改变时，
-
发现的当前值 n , y
-
删除n
-
插入一个映射从 n y + z
复杂度是对数的