0
$\begingroup$

I wonder what is the best data structure I can use in order to achieve the following:

Given a data structure based on a balanced BST, I would like to get a tree with the $\lfloor\frac{n}{2}\rfloor$ greatest values in $O(1)$.

I thought about maintaining another balanced BST and a variable containing the middle value, but I don't think it's a good idea, since the root of a balanced BST might not divide the tree into 2 halves so that the $\lfloor\frac{n}{2}\rfloor$ largest elements are to the right (the tree might be right heavy). Another idea was to use heap, but I don't see how it can help me.

Do you have any idea how to implement it? What do you think about mine?

$\endgroup$
1
$\begingroup$

Maintain two BSTs $T_1$ and $T_2$ such that $T_2$ always contains the largest $\lfloor n/2 \rfloor$ elements, and $T_1$ contains the remaining elements.

Insertions and deletions can be implemented in $O(\log n)$ time by performing the corresponding operation in a suitably chosen tree and then moving at most one element from one tree to the other.

For example, to insert an element $x$ proceed as follows:

  • Find maximum element $m$ of $T_1$
  • If $x \le m$:
    • Insert $x$ in $T_1$
    • If $|T_2| \neq \lfloor n/2 \rfloor$:
      • Delete $m$ from $T_1$
      • Insert $m$ in $T_2$
  • Otherwise:
    • Insert $x$ in $T_2$
    • If $|T_2| \neq \lfloor n/2 \rfloor$:
      • Find the minimum element $m'$ of $T_2$
      • Delete $m'$ from $T_2$
      • Insert $m'$ in $T_1$

Deletions are handled similarily.

The same approach also works if you maintain two heaps (a max-heap and a min-heap) instead of two BSTs.

See also this answer that uses a similar idea.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But, for example, if you insert another element to the main BST, you need to adjust the "max" BST accordingly. How can you know which element to delete and which to insert? it might break the efficiency of the insertion and deletion in the main BST, no? $\endgroup$ – Combinatoric Jun 19 at 20:23
  • $\begingroup$ No. All insertions and deletions are still performed in $O(\log n)$ time. The element to move (if any) is always either the largest element in $T_1$ or the smallest element in $T_2$. Before any operation $|T_1| - |T_2| \in \{ 0, 1 \}$. After inserting/deleting an element $|T_1| - |T_2| \in \{ -1, 0, 1, 2 \}$. Therefore to restore the invariant it suffices to move at most one element. $\endgroup$ – Steven Jun 19 at 20:24
  • $\begingroup$ Thank you, it makes sense now! happy to see I was in the right direction :) $\endgroup$ – Combinatoric Jun 19 at 20:49

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.