What is the time complexity of finding the kth smallest element of all the elements in two order statistics binary search trees? An order statistics tree is a binary search tree where the size of a subtree at each node is stored at that node. Taking the root of the first tree and trying to find the largest element not greater than it in the second tree and doing a binary search on the rank of the element till the $k^{th}$ rank is reached for an element in the first tree, gives a complexity of $O(h1∗h2)$ If an element with rank $k$ is not found in the first tree, repeat the process with the trees switched.
8
-
$\begingroup$ What are your thoughts? What is the best algorithm you've found on your own? $\endgroup$– D.W. ♦May 25, 2022 at 5:57
-
$\begingroup$ Taking the root of the first tree and trying to find the largest element not greater than it in the second tree and doing a binary search on the rank of the element in the first tree gives a complexity of $\mathcal{O}(h1*h2)$ $\endgroup$– Neel KariaMay 25, 2022 at 6:02
-
$\begingroup$ @NeelKaria next time, don’t delete the question from cs.theory stack exchange. Instead, migrate the question. My answer in the comments is now gone. Did you have time to read it? And if so, what are you still stuck at? $\endgroup$– AspiringMatMay 25, 2022 at 6:39
-
$\begingroup$ Don't comment comments asking for additional information or clarification: Edit your question. (I don't see k in your sketch.) $\endgroup$– greybeardMay 25, 2022 at 8:15
-
$\begingroup$ @AspiringMat, sorry for not migrating it; I was not aware of that. I understand the logic with sorted arrays, but I have trouble with accessing the $i^{th}$ element of the tree in $O(1)$ time, which is required. $\endgroup$– Neel KariaMay 25, 2022 at 8:59
|
Show 3 more comments