RopeA rope is a binary tree in which each node v has a weight (v). AllLeaf leavesnodes and(as well as some onesingle-child internodeinternal containsnodes) analso arraycontain storing a light weight string (a short string). andThe eachweight of thosea nodesnode has a weight(v)is equalsequal to the length of the shortits string.Forplus the othersum nodes,of the weight isall the sum of weights in its left subtree. So,Thus thea two-childnode nodeswith intwo Rope can be considered aschildren dividingdivides the whole string into two parts: the left subtree representstores the first part of the string and, the right subtree representstores the second part, of string. Andand the weight can be considered asis the length of the substring in leftfirst part. We can set the weight for each node by doing an in-order traversal and set the weight[[Image:Formula_for_rope.jpg|x120px|border|link=|alt=]]
FromSeen from another viewperspective, the binary tree of Ropea rope can be seen as several levels of nodenodes. The bottom level contains all the nodes whichthat containhave ana extra fieldshort string. (v)Higher andlevels whenhave thefewer leveland become higher, the number offewer nodes become less, anduntil finally, there is just one root node in the highesttop level. So, weWe can build the Roperope by putting all the nodes with light-weightshort stringstrings in the bottom level, then create the second least level by randomly pickpicking half those nodes fromin bottom levelorder to createform newparent nodenodes asin the parents. for the right half nodes in bottomnext level. whoNodes haswith no parents, they become the right child of the nodesnode located into itstheir left. In this way, we build the higher level,levels finallyone therelevel wouldat bea onlytime. oneWe nodestop inwhen somethere level,is whichonly means thisone node is the rootremaining.
