# Rank operation in search tree, number of nodes between 2 values

What kind of search tree should I use in which I will have operation Rank[x, y] which will return number of existing nodes/values between x and y in time O(depth of tree) so the operations find, insert and delete will have also time complexity O(depth of tree)? I was thinking about a-b tree, which has find, insert and delete in O(log n), but I do not know how should I implement the rank operation. I was thinking to add each value in node information about number of its children but it wont be in O(log n) time.

• (time O(depth of tree) leaves a lot of leeway. Interpret a linear list or an array as a tree of depth $n$…) May 9, 2021 at 10:27

Use an AVL tree $$T$$ that is augmented so that each vertex $$v$$ also stores the number of vertices in the subtree of $$T$$ rooted at $$v$$.
Given two vertices $$u$$ and $$v$$ of the tree you can find the number of values between $$u$$'s and $$v$$'s key by summing the sizes of at most $$O(\log n)$$ subtrees of $$T$$ dangling from the (unique) path from $$u$$ to $$v$$ in $$T$$.
These are exactly the highlighted trees/vertices in this answer, which also gives you a $$O(\log n)$$-time algorithm to find them.
The time complexities of insertions, deletions, and searches are asymptotically unaffected (i.e., they are in $$O(\log n)$$).
• Once you have $u$ and $v$, you want the sum of the following three quantities: (i) the number of nodes on the (unique) path between $u$ and $v$ in $T$ (where both endpoints are included); (ii) the sizes of the right subtrees of the vertices that lie on the path between $u$ (included) and the lowest common ancestor $w$ of $u$ and $v$ in $T$, where the right subtree of $w$ is excluded; (iii) the sizes of the left subtrees of the vertices that lie on the path between $v$ (included) and $w$ (excluded). For an example, look at the vertices and subtrees that are highlighted in the answer I linked. May 15, 2021 at 20:12