數據結構，以支持最佳操作用於記分板

Question

存在被需要由下面兩個操作來維護和支持一個記分板：

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

的插入功能可以與他的得分或更新沿着插入playerName在玩家已經在記分牌中的情況下玩家的得分。

提供一個數據結構來支持上述兩個操作，使它們儘可能優化。這兩個函數都會被頻繁調用。

Answer 1

家庭作業？因爲它給你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> 

從這棵樹

現在，如果你想獲得所有玩家排名第二，你只需看看根源，看看有三個左節點，所以在根節點玩家（P1）排名第四。你會下降到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)) 

插入或刪除節點時，更新的平衡和權重信息（多少左右的孩子有）。更新分數時，刪除節點並重新插入新分數。