Editing Rope (data structure) (section)

=== Concat ===
[[File:Vector Rope concat.svg|right|x200px|thumb|Figure 2.2: Concatenating two child ropes into a single rope.]]
: ''Definition:'' <code>Concat(S1, S2)</code>: concatenate two ropes, ''S''<sub>1</sub> and ''S''<sub>2</sub>, into a single rope.
: ''Time complexity:'' {{tmath|O(1)}} (or {{tmath|O(\log N)}} time to compute the root weight)

A concatenation can be performed simply by creating a new root node with {{mono|1=left = S1}} and {{mono|1=right = S2}}, which is constant time. The weight of the parent node is set to the length of the left child ''S''<sub>1</sub>, which would take {{tmath|O(\log N)}} time, if the tree is balanced.

As most rope operations require balanced trees, the tree may need to be re-balanced after concatenation.