0

有一个计分板需要由以下两个操作来维护和支持：

void insert(string playerName, int score);
list<string> getPlayersByRank(int rank);

在玩家已经出现在记分牌中的情况下，插入函数可以将玩家姓名连同他的分数一起插入或更新玩家的分数。

提供数据结构来支持上述两种操作，使其尽可能优化。这两个函数都会被频繁调用。

4

1 回答 1

2

家庭作业？

一个平衡的二叉树浮现在脑海中，因为它为您提供了 O(log(n)) 插入和 (O(n)) 中序遍历。

查看 AVL 树，例如：http ://en.wikipedia.org/wiki/AVL_tree

编辑：

感谢 tmyklebu 的提交，我意识到我忽略了你getPlayersByRank接受参数的事实，所以它是按等级查找而不是完全遍历。

该方法仍然有效，但您应该使用一个变体，其中每个节点都知道它在每个分支中有多少个后代。这样，您可以直接下降到所需的等级。

例子：

(<P1S1L1R1> = Player 1 Score 1 Left 1 Right 1)

             <P1S6L3R2>
            /            \
      <P2S8L1R1>        <P5S3L0R1>
      /        \           \
<P3S10L0R0>    <P4S8L0R0>    <P6S1L0R0>

现在从这棵树中，如果你想让所有玩家排名第 2，你只需查看根节点并看到左侧有 3 个节点，因此根节点 (P1) 处的玩家排名第 4。您将向左下降到 P2 并看到只有一个左侧节点，因此 P2 排名第二。但是，要让所有玩家排名第二，您仍然需要向右下降并找到得分相同的 P4（假设始终将相同得分的玩家插入右侧）。

所以每个节点的当前等级是：

 (rank of parent node) + (number of left children) 
    + (0 if (score is the same as score of parent node) or
       1 otherwise))

插入或删除节点时，更新平衡和权重信息（有多少左右孩子）。更新分数时，删除节点并重新插入新分数。

于 2013-05-15T10:55:15.997 回答