what should we add to a 2-3 tree to be able to find a value with this time complexity?

I've got this question that asks me to make changes to the 2-3 trees that would make it possible to do a find(x) function that would find x with O(log(rank(x))) .

**rank(x) is x's index in a sorted sequence of all of the values of the tree. However we have to still do insert(x) and delete(x) with O(log(n)).

So I thought of using pointers, that would make it easier to find the wanted value and yet I have no Idea how to do it with the requested time complexity.

If you have an idea that may direct me to the solution , please share it.

• Please state or refer the definition of 2-3 tree to use. Dec 26 '21 at 21:51
• @greybeard deleted it from SO Dec 26 '21 at 22:23
• @greybeard what do you mean by definition isn't it just one? a B+ tree Dec 26 '21 at 22:25
• I am used to find in a data structure to mean given a $key$ ($x$?), find the associated $record$. Starting with B-trees, I'm used to All leaves have same depth. With rank(x) starting from 0 or 1, $O(\log(rank(x)))$ looks impossible. There are augmented trees allowing access to records by rank in time $O(\log(n))$. Dec 27 '21 at 6:08
• @greybeard rank(x) starting from 1,and All leaves have same depth... so you think there is no solution? Dec 27 '21 at 10:04