Tencent Database Technology

Nov 23, 2017 · Fundamentals

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

This article explains how to extend a red‑black tree with a subtree‑size counter to support O(log n) rank and selection operations, detailing the required count updates during insertion, deletion, and tree rotations, and provides complete pseudocode for left/right rotations, rank queries, and element‑by‑rank retrieval.