绳索数据结构解释?
Rope data structure explanation?
我在维基百科上阅读有关绳索数据结构的内容,但对描述有点困惑。
维基 link:http://en.wikipedia.org/wiki/Rope_(data_structure)
描述
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, namely the weight of a node is the total string length in its left subtree for a non-leaf node, or the string length of itself for a leaf node.
Thus 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.
下图是维基百科的例子之一。
.
我无法确定上图中数字的来源。
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
- C = 6 + 0 (E + C的空串长度)?
- B = 6 + 3 + 0 + 0 (E + F + C的空字符串长度 + B的空字符串长度)?
- 不对,为什么是 A 22? (6+6+9 = 21?6+6+3+9 = 24?)
我很确定我错过了什么。有人可以帮我清理一下吗?
谢谢。
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...
A没有右子树所以它的值是所有叶节点的权值之和(即使A有右子树它的值也是一样的):6+3+2+4+1+ 6=22
B 的左子树有两个叶子:6+3=9
C 的左子树有一片叶子:6
我在维基百科上阅读有关绳索数据结构的内容,但对描述有点困惑。
维基 link:http://en.wikipedia.org/wiki/Rope_(data_structure)
描述
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, namely the weight of a node is the total string length in its left subtree for a non-leaf node, or the string length of itself for a leaf node.
Thus 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.
下图是维基百科的例子之一。
我无法确定上图中数字的来源。
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
- C = 6 + 0 (E + C的空串长度)?
- B = 6 + 3 + 0 + 0 (E + F + C的空字符串长度 + B的空字符串长度)?
- 不对,为什么是 A 22? (6+6+9 = 21?6+6+3+9 = 24?)
我很确定我错过了什么。有人可以帮我清理一下吗?
谢谢。
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...
A没有右子树所以它的值是所有叶节点的权值之和(即使A有右子树它的值也是一样的):6+3+2+4+1+ 6=22
B 的左子树有两个叶子:6+3=9
C 的左子树有一片叶子:6