Incomputer programming, arope, orcord, is adata structure composed of smallerstrings that is used to efficiently store and manipulate longer strings or entire texts. For example, atext editing program may use a rope to represent the text being edited, so that operations such as insertion, deletion, and random access can be done efficiently.[1]
A rope is a type ofbinary tree where each leaf (end node) holds a string of manageable size and length (also known as aweight), and each node further up the tree holds the sum of the lengths of all the leaves in its leftsubtree. A node with two children thus divides the whole string into two parts: the left subtree stores the first part of the string, the right subtree stores the second part of the string, and a node's weight is the length of the first part.
For rope operations, the strings stored in nodes are assumed to be constantimmutable objects in the typical nondestructive case, allowing for somecopy-on-write behavior. Leaf nodes are usually implemented asbasic fixed-length strings with areference count attached for deallocation when no longer needed, although othergarbage collection methods can be used as well.
In the following definitions,N is the length of the rope, that is, the weight of the root node.
finalclassInOrderRopeIteratorimplementsIterator<RopeLike>{privatefinalDeque<RopeLike>stack;InOrderRopeIterator(@NonNullRopeLikeroot){stack=newArrayDeque<>();varc=root;while(c!=null){stack.push(c);c=c.getLeft();}}@OverridepublicbooleanhasNext(){returnstack.size()>0;}@OverridepublicRopeLikenext(){valresult=stack.pop();if(!stack.isEmpty()){varparent=stack.pop();varright=parent.getRight();if(right!=null){stack.push(right);varcleft=right.getLeft();while(cleft!=null){stack.push(cleft);cleft=cleft.getLeft();}}}returnresult;}}
staticbooleanisBalanced(RopeLiker){valdepth=r.depth();if(depth>=FIBONACCI_SEQUENCE.length-2){returnfalse;}returnFIBONACCI_SEQUENCE[depth+2]<=r.weight();}staticRopeLikerebalance(RopeLiker){if(!isBalanced(r)){valleaves=Ropes.collectLeaves(r);returnmerge(leaves,0,leaves.size());}returnr;}staticRopeLikemerge(List<RopeLike>leaves){returnmerge(leaves,0,leaves.size());}staticRopeLikemerge(List<RopeLike>leaves,intstart,intend){intrange=end-start;if(range==1){returnleaves.get(start);}if(range==2){returnnewRopeLikeTree(leaves.get(start),leaves.get(start+1));}intmid=start+(range/2);returnnewRopeLikeTree(merge(leaves,start,mid),merge(leaves,mid,end));}
Insert(i, S’): insert the stringS’ beginning at positioni in the strings, to form a new stringC1, ...,Ci,S',Ci + 1, ...,Cm.This operation can be done by aSplit() and twoConcat() operations. The cost is the sum of the three.
publicRopeinsert(intidx,CharSequencesequence){if(idx==0){returnprepend(sequence);}if(idx==length()){returnappend(sequence);}vallhs=base.split(idx);returnnewRope(Ropes.concat(lhs.fst.append(sequence),lhs.snd));}
Index(i): return the character at positioniTo retrieve thei-th character, we begin arecursive search from the root node:
@OverridepublicintindexOf(charch,intstartIndex){if(startIndex>weight){returnright.indexOf(ch,startIndex-weight);}returnleft.indexOf(ch,startIndex);}
For example, to find the character ati=10 in Figure 2.1 shown on the right, start at the root node (A), find that 22 is greater than 10 and there is a left child, so go to the left child (B). 9 is less than 10, so subtract 9 from 10 (leavingi=1) and go to the right child (D). Then because 6 is greater than 1 and there's a left child, go to the left child (G). 2 is greater than 1 and there's a left child, so go to the left child again (J). Finally 2 is greater than 1 but there is no left child, so the character at index 1 of the short string "na" (ie "n") is the answer. (1-based index)
Concat(S1, S2): concatenate two ropes,S1 andS2, into a single rope.A concatenation can be performed simply by creating a new root node withleft = S1 andright = S2, which is constant time. The weight of the parent node is set to the length of the left childS1, which would take time, if the tree is balanced.
As most rope operations require balanced trees, the tree may need to be re-balanced after concatenation.
Split (i, S): split the stringS into two new stringsS1 andS2,S1 =C1, ...,Ci andS2 =Ci + 1, ...,Cm.There are two cases that must be dealt with:
The second case reduces to the first by splitting the string at the split point to create two new leaf nodes, then creating a new node that is the parent of the two component strings.
For example, to split the 22-character rope pictured in Figure 2.3 into two equal component ropes of length 11, query the 12th character to locate the nodeK at the bottom level. Remove the link betweenK andG. Go to the parent ofG and subtract the weight ofK from the weight ofD. Travel up the tree and remove any right links to subtrees covering characters past position 11, subtracting the weight ofK from their parent nodes (only nodeD andA, in this case). Finally, build up the newly orphaned nodesK andH by concatenating them together and creating a new parentP with weight equal to the length of the left nodeK.
As most rope operations require balanced trees, the tree may need to be re-balanced after splitting.
publicPair<RopeLike,RopeLike>split(intindex){if(index<weight){valsplit=left.split(index);returnPair.of(rebalance(split.fst),rebalance(newRopeLikeTree(split.snd,right)));}elseif(index>weight){valsplit=right.split(index-weight);returnPair.of(rebalance(newRopeLikeTree(left,split.fst)),rebalance(split.snd));}else{returnPair.of(left,right);}}
Delete(i, j): delete the substringCi, …,Ci +j − 1, froms to form a new stringC1, …,Ci − 1,Ci +j, …,Cm.This operation can be done by twoSplit() and oneConcat() operation. First, split the rope in three, divided byi-th andi+j-th character respectively, which extracts the string to delete in a separate node. Then concatenate the other two nodes.
@OverridepublicRopeLikedelete(intstart,intlength){vallhs=split(start);valrhs=split(start+length);returnrebalance(newRopeLikeTree(lhs.fst,rhs.snd));}
Report(i, j): output the stringCi, …,Ci +j − 1.To report the stringCi, …,Ci +j − 1, find the nodeu that containsCi andweight(u) >= j, and then traverseT starting at nodeu. OutputCi, …,Ci +j − 1 by doing anin-order traversal ofT starting at nodeu.
| Operation | Rope | String |
|---|---|---|
| Index[1] | O(log n) | O(1) |
| Split[1] | O(log n) | O(1) |
| Concatenate | O(1) amortized, O(log n) worst case[citation needed] | O(n) |
| Iterate over each character[1] | O(n) | O(n) |
| Insert[2][failed verification] | O(log n) | O(n) |
| Append[2][failed verification] | O(1) amortized, O(log n) worst case | O(1) amortized, O(n) worst case |
| Delete | O(log n) | O(n) |
| Report | O(j + log n) | O(j) |
| Build | O(n) | O(n) |
Advantages:
Disadvantages:
This table compares thealgorithmic traits of string and rope implementations, not theirraw speed. Array-based strings have smaller overhead, so (for example) concatenation and split operations are faster on small datasets. However, when array-based strings are used for longer strings, time complexity and memory use for inserting and deleting characters becomes unacceptably large. In contrast, a rope data structure has stable performance regardless of data size. Further, the space complexity for ropes and arrays are both O(n). In summary, ropes are preferable when the data is large and modified often.
 | This articlerelies largely or entirely on asingle source. Relevant discussion may be found on thetalk page. Please helpimprove this article byintroducing citations to additional sources. Find sources: "Rope" data structure – news ·newspapers ·books ·scholar ·JSTOR(September 2011) |
