112. Introducing the Rope data structure
Prerequisite: Starting with this problem, we will cover a bunch of complex data structures that require previous experience with binary trees, lists, heaps, queues, stacks, and so on. If you are a novice in the data structure field, then I strongly recommend you postpone the following problems until you manage to read The Complete Coding Interview Guide in Java which provides deep coverage of these preliminary topics.When we need to handle large amounts of text (for instance, if we develop a text editor, a powerful text search engine, and so on) we have to deal with a significant number of complex tasks. Among these tasks, we have to consider appending/concatenating strings and memory consumption.The Rope data structure is a special binary tree that aims to improve string operations while using memory efficiently (this is especially useful for large strings). Its Big O goals are listed in the following figure:
Figure 5.12 – Big O for Rope
Being a binary tree, a Rope can be shaped via the classical Node class as follows:
public static class Node {
private Node left;
private Node right;
private int weight;
private String str;
public Node(String str) {
this(null, null, str.length(), str);
}
public Node(Node left, Node right, int weight) {
this(left, right, weight, null);
}
public Node(Node left, Node right, int weight, String str) {
this.left = left;
this.right = right;
this.str = str;
this.weight = weight;
}
}
Each node holds pointers to its left and right child (left and right) and the total weight of the nodes in its left subtree (weight). Leaf nodes store small chunks of the large string (str). Here is a Rope for the text I am a very cool rope:
Figure 5.13 – Rope sample
Next, let’s implement the main operations of a Rope, and let’s start with searching by index.
Implementing indexAt(Node node, int index)
The indexAt(Node node, int index) method attempts to find the character at the given index. This is a recursive process based on a simple rule as follows:
If index > (weight – 1) then index = index-weight and move to the right node.
If index < weight then just move to the left node.
These two steps are repeated until we hit a leaf node and we return the character at the current index.Let’s assume that we want to return the character from index 5, which is e (see figure 5.14):
Starting from the root, we have that index = 5, index < 8, so we move left.
Next, index = 5, 5 > 3, so index = 5 – 3 = 2 and we move right
Next, index = 2, 2 > 1, so index = 2 – 1 = 1 and we move right
The right node is a leaf node, so we return charAt(1), which is e
Figure 5.14 – Implementing indexAt()
In code, this algorithm is quite simple:
public static char indexAt(Node node, int index) {
if (index > node.weight – 1) {
return indexAt(node.right, index – node.weight);
} else if (node.left != null) {
return indexAt(node.left, index);
} else {
return node.str.charAt(index);
}
}
Next, let’s talk about concatenating two Ropes.