Code Notes made by Vaibhav Rathod

rope-data-structure

2 min read

Written by Vaibhav Rathod

Explanation

  • A Rope is a tree-based data structure used for efficiently concatenating and splitting strings. It avoids the inefficiencies of directly manipulating large strings in memory.

Steps

  • Create RopeNode: Each node stores a string or links to other nodes (internal node).
  • Concatenate: Merge two ropes by combining their root nodes.
  • Split: Split a rope at a given index by recursively dividing the rope at the node level.
  • Traverse: Traverse the tree to construct the string representation.

Time Complexity

  • Time complexity for operations like concatenation: O(log n), where n is the length of the string.
class RopeNode:
    def __init__(self, string, left=None, right=None):
        self.string = string  # String for leaf, or left/right for internal
        self.left = left
        self.right = right
 
class Rope:
    def __init__(self, root=None):
        self.root = root
 
    def concatenate(self, other_rope):
        """Concatenate two ropes."""
        new_node = RopeNode("", self.root, other_rope.root)
        self.root = new_node
 
    def split(self, index):
        """Split the rope at index."""
        left_part, right_part = self._split_recursive(self.root, index)
        return Rope(left_part), Rope(right_part)
 
    def _split_recursive(self, node, index):
        """Recursively split the rope at the node."""
        if node.left is None and node.right is None:  # Leaf node
            return RopeNode(node.string[:index]), RopeNode(node.string[index:])
        
        # Internal node, find appropriate split
        left_weight = len(node.left.string) if node.left else 0
        if index < left_weight:
            left_part, right_part = self._split_recursive(node.left, index)
            return left_part, self._merge(right_part, node.right)
        else:
            right_index = index - left_weight
            left_part, right_part = self._split_recursive(node.right, right_index)
            return self._merge(node.left, left_part), right_part
 
    def _merge(self, left, right):
        """Merge two rope nodes."""
        return RopeNode("", left, right)
 
    def __str__(self):
        """Return the rope as a string."""
        return self._in_order_traversal(self.root)
 
    def _in_order_traversal(self, node):
        """In-order traversal to construct the string."""
        if node.left is None and node.right is None:
            return node.string
        return self._in_order_traversal(node.left) + self._in_order_traversal(node.right)
 
 
# Example Usage
rope1 = Rope(RopeNode("Hello "))
rope2 = Rope(RopeNode("World!"))
 
rope1.concatenate(rope2)  # Concatenate ropes
print("Concatenated Rope:", rope1)
 
left_rope, right_rope = rope1.split(6)  # Split the rope at index 6
print("Left Rope:", left_rope)
print("Right Rope:", right_rope)

Graph View

Recently Updated