如何拆分绳树？ [英] How to split a rope tree?
问题描述
我碰到绳子树作为替代数据结构的字符串。
I came across a rope tree as an alternative data structure for a string.
http://en.wikipedia.org/wiki/Rope_(data_structure)
要CONCAT很容易，但我被困在分割操作。维基百科的文章指出：
To concat is easy, but I am stuck on the split operation. The wikipedia article states:
例如，分裂22个字符的绳索描绘图2.3为长度为11的两个相等的部分绳索，查询12字符在底层找到节点k。除去K和的G.转到右孩子之间的链接到父G和从G.旅行树向上的重量减去的K的重量和删除任何权利的链接，从这些节点中减去的K的重量（唯一节点研发，在这种情况下）。最后，通过连接在一起，并创建一个新的父P上的重量等于左节点k的长度建立新孤立节点K和小时。
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 the right child of G. Go to the parent G and subtract the weight of K from the weight of G. Travel up the tree and remove any right links, subtracting the weight of K from these nodes (only node D, 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.
查找的字符和重组的孤儿是没有问题的。但我不明白的旅行了树，并删除任何合适的链接，从这些节点中减去的K重量的。这个例子停在研发，但如果你遵循这些说明逐字你会继续到B和除去D-为好。这是什么算法，在正确的停车需求？你如何避免节点只有一个（左或右）的孩子？
Locating the character and recombining the orphans is no problem. But I don't understand the "Travel up the tree and remove any right links, subtracting the weight of K from these nodes". The example stops at D, but if you follow these instructions verbatim you would continue onto B and remove D as well. What is the correct stopping requirement in this algorithm? And how do you avoid nodes with only one (left or right) child?
一个伪code算法解释这部分将帮助良多。
A pseudo-code algorithm explaining this part would help tremendously.
推荐答案
维基百科的文章也不是很明确的。如果当前节点是 X 及其母公司是是你只会当旅游下的X 是是左子。在视觉上你会向上和向右就可以。
The wikipedia article is not very explicit. If the current node is X and its parent is Y you would only travel up if X is the left child of Y. Visually you're going up and to the right as far as you can.
这篇关于如何拆分绳树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
