[FEATURE]Implementation of Rope Data Structure and Rebalancing algorithm on it

[THIRU-1074]

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:

1. Each node stores:

• Left and right child.

• Weight = length of left subtree.

• String (only in leaf nodes).

2. Operations to implement:

• charAt(index)

• insert(index, string)

• delete(start, end)

• substring(start, end)

• concat(rope1, rope2)

• split(index)

• rebalance()

3. 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.

4. 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:

• https://github.com/egor-bogomolov/rope-java

• Apache Commons Text Rope

[rameshgitter]

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

[THIRU-1074]

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.