[FEATURE]Implementation of Rope Data Structure and Rebalancing algorithm on it
Closed this issue · 9 comments
Detailed description
Implement the Rope data structure, a binary tree-based alternative to traditional strings, optimized for efficient operations on large texts, such as concatenation, insertion, deletion, and substring extraction. The feature should also include a rebalancing algorithm to maintain performance over successive operations.
Context
In many applications like text editors, DNA sequence editors, or large document processing tools, string operations become expensive due to frequent modifications. Using a Rope allows operations like insert, delete, and substring to be done in O(log n) time instead of O(n). Rebalancing becomes necessary over time to prevent performance degradation as the tree becomes unbalanced.
This feature will:
-
Improve performance for text-heavy operations.
-
Provide a foundational structure for editor-like applications.
-
Serve as a useful data structure for competitive programming and algorithmic learning.
Possible implementation
Structure:
- Each node stores:
-
Left and right child.
-
Weight = length of left subtree.
-
String (only in leaf nodes).
- Operations to implement:
-
charAt(index)
-
insert(index, string)
-
delete(start, end)
-
substring(start, end)
-
concat(rope1, rope2)
-
split(index)
-
rebalance()
- Rebalancing Algorithm:
-
In-order traversal to collect all leaves.
-
Build a new balanced binary tree from these leaves.
-
Could be triggered manually or after N operations.
- Optional:
-
Utility to visualize the tree.
-
Benchmark tools to compare Rope vs. StringBuilder/String.
Additional information
-
Reference paper: "Ropes: An Alternative to Strings" by Boehm et al.
-
Potential Java implementations to reference:
I’m Ramesh Chandra Soren, a C++ enthusiast interested in tree-based data structures. I’d love to contribute to the features you described for the Rope implementation.
What I’ve done so far
- Read “Ropes: An Alternative to Strings” by Boehm et al.
- Sample implementation named as
rope.hpp.
Are there any coding style guidelines or test frameworks you’d prefer I follow?
Thanks for maintaining this project—looking forward to your feedback!
—Ramesh
I think the repo maintainers aren't currently active , you can fork the repo and work on it , if you got any response from maintainers get guidance from them.
Feel free to implement this, Please just create a pull request. Make sure to follow contribution guidelines and always use .cpp file extension
Okk
Hi everyone
I would love to make this data structure. I have read and done competitive programming, specifically USACO Gold, and know a lot about tree structures.
Could I create an implementation of this data structure?
Thanks,
Sarthak Gupta
Please raise a pull request if one doesn't exist already! we encourage pull requests.
Hey There
I recently came across this issue i think i can resolve this can you please assign this to me ?
This issue has been automatically marked as abandoned because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.
Please ping one of the maintainers once you add more information and updates here. If this is not the case and you need some help, feel free to ask for help in our Gitter channel or our Discord server. Thank you for your contributions!