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.

  • $\begingroup$ Please state or refer the definition of 2-3 tree to use. $\endgroup$
    – greybeard
    Dec 26 '21 at 21:51
  • $\begingroup$ @greybeard deleted it from SO $\endgroup$
    – Raea6789
    Dec 26 '21 at 22:23
  • $\begingroup$ @greybeard what do you mean by definition isn't it just one? a B+ tree $\endgroup$
    – Raea6789
    Dec 26 '21 at 22:25
  • $\begingroup$ 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))$. $\endgroup$
    – greybeard
    Dec 27 '21 at 6:08
  • $\begingroup$ @greybeard rank(x) starting from 1,and All leaves have same depth... so you think there is no solution? $\endgroup$
    – Raea6789
    Dec 27 '21 at 10:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.