绳索数据结构说明？

Question

我正在阅读维基百科上的绳索数据结构,我对描述有点困惑.

维基链接:http://en.wikipedia.org/wiki/Rope_(data_structure)

描述

绳索是具有包含短字符串的叶节点的二叉树.

每个节点的权重值等于其字符串的长度加上其左子树中所有叶节点权重的总和,即节点的权重是非叶子节点的左子树中的总字符串长度,或者叶节点的字符串长度.

因此,具有两个子节点的节点将整个字符串分成两部分:左子树存储字符串的第一部分.右子树存储第二部分,其权重是左子重量与其包含字符串长度的总和.

下图是维基百科的一个例子.

.

我无法看到上图中的数字来自哪里.

每个节点的权重值等于其字符串的长度加上其左子树中所有叶节点的权重之和

• 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？)

我很确定我错过了什么.有人可以帮我清理一下吗？

谢谢.

Answer 1

每个节点的权重值等于其字符串的长度加上其左子树中所有叶节点的权重之和...

A没有正确的子树,所以它的值是所有叶子节点的权重之和(即使A有一个右子树,它的值也是相同的):6 + 3 + 2 + 4 + 1 + 6 = 22

B在其左子树中有两个叶子:6 + 3 = 9

C在其左子树中有一个叶子:6