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

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

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .