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.

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

1 Answer 1


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)$).

  • $\begingroup$ how could sum of the subtrees give me the result? which subtrees exactly should I sum? $\endgroup$
    – Rikib1999
    May 15, 2021 at 15:35
  • $\begingroup$ 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. $\endgroup$
    – Steven
    May 15, 2021 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.