Augmenting Red‑Black Trees with a Count Field for Order‑Statistic (Rank) Queries

Red‑black trees are self‑balancing binary search trees that support O(log n) search, insertion and deletion. To obtain the rank of a given element or retrieve an element by its rank, each node can be augmented with a count field that stores the size of the subtree rooted at that node (including the node itself).

During insertion or deletion the count of every ancestor of the modified node is updated (incremented or decremented by 1). The standard red‑black tree rotations are also extended to maintain correct counts for the rotated nodes.

Count field definition :

count[x] = count[left[x]] + count[right[x]] + 1; // when x is not null

count[x] = 0; // when x is null

Left rotation count updates (only nodes x and y change):

count[x] = count[α] + count[β] + 1;

count[y] = count[x] + count[γ] + 1;

Left‑rotate pseudocode :

LEFT-ROTATE(T, x)
    y = right[x]
    right[x] = left[y]
    left[y] = x
    // update counts
    count[x] = count[left[x]] + count[right[x]] + 1
    count[y] = count[x] + count[γ] + 1
    // adjust parent pointers (omitted for brevity)

Right rotation count updates (symmetrical to left rotation):

count[y] = count[γ] + count[β] + 1;

count[x] = count[x] + count[α] + 1;

Right‑rotate pseudocode :

RIGHT-ROTATE(T, y)
    x = left[y]
    left[y] = right[x]
    right[x] = y
    // update counts
    count[y] = count[γ] + count[β] + 1
    count[x] = count[y] + count[α] + 1
    // adjust parent pointers (omitted for brevity)

Query by rank (selection) :

QUERYBYRANK(T, r)
    y = root[T]
    while y != nil
        if count[left[y]] + 1 == r then
            // found the element
            exit
        else if count[left[y]] + 1 > r then
            y = left[y]
        else
            r = r - (count[left[y]] + 1)
            y = right[y]

Rank of a given key :

RANK(T, x)
    y = root[T]
    while y != nil
        if key[x] == key[y] then
            r = count[y]
            exit
        else if key[x] < key[y] then
            y = left[y]
        else
            r = r + count[left[y]] + 1
            y = right[y]

All operations retain the O(log n) time complexity of the original red‑black tree. The additional count updates occur only during rotations (at most three per insertion/deletion), so the performance impact is minimal. This augmentation is useful for implementing leaderboard features in games, though very large datasets (e.g., tens of millions of elements) may become limited by string key comparisons.