Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Rope (data structure)
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
=== Split === [[File:Vector Rope split.svg|right|x600px|thumb|Figure 2.3: Splitting a rope in half.]] : ''Definition:'' <code>Split (i, S)</code>: split the string ''S'' into two new strings ''S''<sub>1</sub> and ''S''<sub>2</sub>, {{math|1=''S''<sub>1</sub> = ''C''<sub>1</sub>, ..., ''C<sub>i</sub>''}} and {{math|1=''S''<sub>2</sub> = ''C''<sub>''i'' + 1</sub>, ..., ''C<sub>m</sub>''}}. : ''Time complexity:'' {{tmath|O(\log N)}} There are two cases that must be dealt with: # The split point is at the end of a string (i.e. after the last character of a leaf node) # The split point is in the middle of a string. 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 node ''K'' at the bottom level. Remove the link between ''K'' and ''G''. Go to the parent of ''G'' and subtract the weight of ''K'' from the weight of ''D''. Travel up the tree and remove any right links to subtrees covering characters past position 11, subtracting the weight of ''K'' from their parent nodes (only node ''D'' and ''A'', in this case). Finally, build up the newly orphaned nodes ''K'' and ''H'' by concatenating them together and creating a new parent ''P'' with weight equal to the length of the left node ''K''. As most rope operations require balanced trees, the tree may need to be re-balanced after splitting. <syntaxhighlight lang="java"> public Pair<RopeLike, RopeLike> split(int index) { if (index < weight) { val split = left.split(index); return Pair.of(rebalance(split.fst), rebalance(new RopeLikeTree(split.snd, right))); } else if (index > weight) { val split = right.split(index - weight); return Pair.of(rebalance(new RopeLikeTree(left, split.fst)), rebalance(split.snd)); } else { return Pair.of(left, right); } } </syntaxhighlight>
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)