Ropes
One of the most common data structures in programming is a string and some of the most common operations of a string are appending and concatenating them. Strings are stored as an array of characters so adding a new letter to the end of a string would O(n) time. This leaves room for improvement and which is why the Rope data structure was created.
What are Ropes?
A rope is made up of nodes organized as a binary tree. Each of these nodes holds smaller strings to create one very long string or rope. Every node also holds the total weight of all the nodes in its left subtree. Essentially weight is the sum of all the leaf nodes in the nodes left subtree. A rope is commonly used in text editors and search engines basically anything handling large amounts of text.
Ropes vs. Strings
Advantages
- Ropes don’t require O(n) memory to perform tasks like insertion, deletion, and searching
- Opposed to character arrays, ropes don’t need large contiguous memory allocations
- Users can undo the last concatenation they made simply by removing the root
- They have a stable performance regardless of size
Disadvantages
- Much slower on smaller strings
- Bigger risk for bugs because more complex source code
- More memory needed to store parent node
Performance Analysis
Operations
1. Search(Index i)
To find a character at the ith position we search recursively beginning at the root node. Then we follow the main rule if the weight of the current node is lower than the value of i we subtract the weight from i and move right. If the weight is less than the value i we just move left. We keep going until we reach a leaf node and at the leaf we return the character at the ith position.
Example: We want to find the 7th character in the rope “Ropes are very cool you try to use them”
Psyudocode:
function index(RopeNode node, integer i)
if node.weight < i and exists(node.right) then
return index(node.right, i — node.weight)
end
if exists(node.left) then
return index(node.left, i)
end
return node.[i]string
end
2. Concatenation(S1+S2)
Concatenating two string(S1+2) is done by creating a new root node which has the weight of the leaf nodes in S1. The new node made now has S1 as its left child and S2 as its right child. This operation requires a balanced tree so rebalancing may acquire after the concatenation.
Example: We concatenate two ropes
Pysuedocode
function concatenation(ropenode node1, ropenode node2)
newrope.left = node1
newrope.right = node2
Get Wyatt Saltzman’s stories in your inbox
Join Medium for free to get updates from this writer.
newrope.val = length(node1)
3. Splitting
To split a string there are two important cases.
- Split is the last character of a leaf node
- Split is a middle character of a leaf node
The second case simplifies to the first case by splitting the string to make two new leaf nodes and creating a parent node for these two new leafs.
Example Lets split the string “Ropes are very cool you try to use them” to “Ropes are very “ and “cool you try to use them”
4. Insert(i, S’)
The insertion method makes use of 1 splitting and 2 concatenations. This cost of the operation is the sum of the three operations used.
The algorithm is:
- Split the string into S1 and S2 at i
- Concatenate S1 and the string to be inserted to form S3
- Concatenate S1 and S3
5. Delete(i, j)
This operation uses two splits and 1 concatenation. This cost of the operation is the sum of the three operations used.
The algorithm is:
- Split the original string at i into S1 and S2
- Split S2 at j into S3 and S4
- Concatenate S1 and S4
Code Example
Here is an example I coded in C++ for the index, insertion, and deletion methods.
Code:
Output:
As you can see the 6th position in the rope is the letter “I” which was correctly returned when the at() function was used. After inserting the word so to the rope you can see the rope now says so twice. Then I deleted the word “Hello” from the rope and as you can see in the terminal the rope now is “I love cropes so so much”.
Further Reading
http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.14.9450&rep=rep1&type=pdf
Work Cited
https://www.geeksforgeeks.org/ropes-data-structure-fast-string-concatenation/
https://www.geeksforgeeks.org/stl-ropes-in-c/
https://iq.opengenus.org/rope-data-structure/
https://en.wikipedia.org/wiki/Rope_%28data_structure%29
GitHub Repo
