Keeping Players in Order

Let’s start from what the leaderboard has to do. It needs three operations:

Set a player’s rating. Go from a player ID to their current rating, and change it to the new one. The players must stay in order by rating.
Get a player’s rank. Go from a player ID to their rating. Then go from that rating to how many players are rated higher.
Get the players ranked $i$ to $j$ . Go from rank $i$ to the player at that rank. Then take the next players in order.

So we need to go quickly:

from a player ID to a rating,
from a rating to a rank,
and from a rank to a player.

From a player ID to a rating

A map does this. A hash table finds a player’s rating by their ID in constant time on average.

From a rating to a rank, and back

A balanced search tree ordered by rating keeps the players in order. Finding a rating takes about $lo g_{2} n$ steps, where $n$ is the number of players. But a search tree alone does not know how many players are rated higher. It has the same problem as the index in the player database.

So we augment the tree: each node also holds the size of its subtree. The size is the number of nodes in the subtree, counting the node itself. Here is a small tree with seven players. Each node shows a rating, the player, and the size:

graph TD
    A["1800: player 31 (size 7)"] --> B["1620: player 8 (size 3)"]
    A --> C["1900: player 12 (size 3)"]
    B --> D["1500: player 40 (size 1)"]
    B --> E["1710: player 27 (size 1)"]
    C --> F["1850: player 5 (size 1)"]
    C --> G["2100: player 19 (size 1)"]

Higher ratings are to the right.

A player’s rank

Let’s find player 27’s rank. The map gives player 27’s rating: 1710. Now walk from the root to 1710, and count the players rated higher on the way:

At 1800, go left. Player 31 and everyone in its right subtree are rated higher than 1710. That is $1 + 3 = 4$ players.
At 1620, go right. Player 8 is rated lower. Add nothing.
At 1710, stop. Its right subtree is empty. Add nothing.

4 players are rated higher, so player 27 has rank 5.

So the rule is this. Each time the walk goes left, add the node and the size of its right subtree. At the end, add the size of the target’s right subtree.

The walk visits one node on each level, so it takes about $lo g_{2} n$ steps. It does not visit the players it counts one by one. It adds the subtree sizes instead.

The player at a rank

Let’s find the player at rank 5. Start at the root, with $i = 5$ . At each node, let $r$ be the size of its right subtree:

If $i$ is at most $r$ , the player is in the right subtree. Go right.
If $i$ is $r + 1$ , the player is this node.
Otherwise, the player is in the left subtree. Subtract $r + 1$ from $i$ , and go left.

At 1800, $r$ is 3. 5 is more than 4, so $i$ becomes $5 - 4 = 1$ , and we go left. At 1620, $r$ is 1. 1 is at most 1, so we go right. At 1710, $r$ is 0. 1 is $0 + 1$ , so the player at rank 5 is player 27. That matches the rank we found above.

For ranks $i$ to $j$ , we find the player at rank $i$ . Then we follow the tree to the next lower rating, until we have $j - i + 1$ players.

Setting a rating

To set a player’s rating, we remove the player’s node and insert it again with the new rating. Each node on the two paths gets its size updated. The tree also rebalances itself, and the rotations update the sizes of the nodes they move. You saw balanced trees in a data structures course. We do not go into the rotations here.

The cost

Finding a rank walks from the root to one node. Setting a rating removes a node and inserts it again. That is two such walks. So the work grows with $lo g_{2} n$ . $lo g_{2}$ of 20 million is about 24.3, so one walk is about 25 steps for 20 million players. A page takes one walk to find its first player, then one more step for each of its 50 players. In the player database, counting the players rated higher than a player in the middle takes about 10 million steps.