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