2
$\begingroup$

Assume I have a polygon chain implementation which is backed by a key-value store which stores the position of a point inside the chain as key and the point itself as value. So a polygon chain of the points $p_1\rightarrow p_2\rightarrow p_3$ is stored as $\{0\Rightarrow p_1,1\Rightarrow p_2,2\Rightarrow p_3\}$. The key-value store is implemented with a data structure which allows the operations split and join in $O(\log n)$ time.

I want to join the chain $P = p_1\rightarrow p_2\rightarrow p_3$ and the chain $Q = q_1->q_2->q_3$ to a chain $p_1\rightarrow p_2\rightarrow p_3\rightarrow q_1\rightarrow q_2\rightarrow q_3$.

Is there a way to join two polygon chains in logarithmic time without updating the keys? If I do a simple join, I get a problem with duplicated keys, so the keys of $Q$ have to be updated before the join, but this destroys my logarithmic time approach as I need linear time for updating the keys.

Am I wrong here already?

If not, is there a way to keep the logarithmic time?

$\endgroup$
1
  • $\begingroup$ After merging indexes (keys) of points that was in $q$ should be increased on $|p|$, suchwise if your store indexes (keys) explicitly you need at least $O(|q|)$ time to update it. I can recommend use treap with implicit indexes (treap is example of randomized binary trees). List implementation based on treap have $O(log N)$ time-complexity for add/select/delete element and for concatenate/split lists operations. $\endgroup$
    – knok16
    Jul 23, 2015 at 20:58

1 Answer 1

3
$\begingroup$

You are asking for a data structure for sequences (aka vectors or arrays) that permits efficient concatenation. I suggest using any standard binary tree data structure, e.g., AVL tree, red-black tree, splay tree, treap, etc. They support $O(\lg n)$ time concatenation and $O(\lg n)$ time lookups. The differences between them come down to details related to implementation complexity and constant-factor differences in running time.

With these algorithms, the keys are not stored explicitly. Instead, they are implicit. To lookup key $i$, you search for the $i$th leaf from the left, but the key $i$ is never stored anywhere. Thus, when concatenating two trees, there is no need to renumber the keys. You can find the $i$th leaf in $O(\lg n)$ time: augment the data structure so that each node keeps a count of the number of leafs underneath it; then it's clear how to traverse the tree during a lookup (whether to go left or right at each node is an easy decision, given the information stored in each node).

$\endgroup$
2
  • $\begingroup$ no, my main question is the neccesarity of updating keys before a join-operation. the polygon chain itself is already implemented as a binary tree which allows join in logarithmic time $\endgroup$ Jul 24, 2015 at 7:08
  • $\begingroup$ @ManuelJain, I've updated my answer to explain that aspect: see the 2nd paragraph of my answer. $\endgroup$
    – D.W.
    Jul 24, 2015 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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