What is a Rope?
A rope is a data structure that is used to store strings. The rope allows for insertions and deletions to occur in O (log n). It transforms the word into a tree. Even though it has O(log n) insertion/deletion, in order to actually get the word, the whole needs to be searched, so its O(n).
The Rope:
A rope will represent a string in a binary tree. The in-order traversal of the binary tree (left, root, right order) will produce the string. There are many ways to build the tree of a string, but in this article, a recursive solution will be used.
Roughly equally split the string at a letter n into s1 and s2. Where n is a part of neither substring. Make the root of the tree.
Recuriously build the tree by doing step 1 again for s1 and s2. In this case, the algorithm would break s1 into smaller chunks s3 and s4, making the middle character the root left child.
The splitting will keep going until the entire tree is built.
Rope Operations:
As mentioned, prior insertion and deletion can be done in O (log n) time. Try looking at the ropes of “ababa” “acbabab” and “abababc”. Each leaf node contains the two adjacent spots in the string. Look at the following image for elaboration:
When it comes to stuff like deletion, it happens the same as in a binary tree. Now that the string is in tree format, more operations can also be done. Entire chunks of the string can be swapped around. Simply swap some of the nodes.