Rope

This is about the advance data structure called rope/cord.

1. Rope/Cord-Data structure By D.Darling Jemima, 14MZ31

2. Definition of Rope A   rope or   cord , is a data structure composed of smaller  strings. It is used for efficiently storing and manipulating a very long string . A rope is a binary tree having leaf nodes that contain a short string. Each node has a weight value equal to the length of its string plus the sum of all leaf nodes weight in its left subtree .

3. A simple rope built on the string of " Hello_my_name_is_Jemima ". > 9 6 22 3 6 2 2 4 1 1 6 6 Hello_ my_ na m e_i s Jemima A B C D G E F I J K L H

4. Contd … A node with two children divides the whole string into two parts: the left subtree stores the first part of the string. The right subtree stores the second part and its weight is the sum of the left child's weight and the length of its contained string.

5. Operations in rope Index Split Concatenation Insert Delete

6. Index operation in ropes function index( RopeNode node, integer i ) if node.weight < i then return index( node.right , i - node.weight ) else if exists( node.left ) then return index( node.left , i ) else return node.string [ i ] endif endif end

7. Index(To find the character i =10) > 9 6 22 3 6 2 2 4 1 1 6 6 Hello_ my_ na m e_i s jemima A B C D E F I J K L G H

8. Concatenation 6 3 6 2 2 4 9 6 2 6 3 2 4 Hello_ my_ na m e_i Hello_ my_ na m e_i

9. Split 9 6 22 3 6 2 2 4 1 1 6 6 Hello_ my_ na m e_i s jemima

10. Split 9 6 22 3 6 2 2 4 1 1 6 6 Hello_ my_ na m e_i s jemima

11. Split 9 6 22 3 6 2 2 4 1 1 6 6 Hello_ my_ na m e_i s jemima 4

12. Advantages of ropes Ropes enable much faster insertion and deletion of text. Ropes don't require O(n) extra memory when operated upon (arrays need that for copying operations) Ropes don't require large contiguous memory spaces.

13. Application of ropes in text editor Hello, World! ^------Cursor here +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | H|e|l|l|o |,| |W| <free> | o|r|l|d |!| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ^ ^ | begin cur1 cur2 end

14. References http://en.wikipedia.org/wiki/Rope_data_structure.

15. 5 5 3 THANK_ YOU