0

维基百科条目说:

每个节点的“权重”等于其字符串的长度加上其左子树中所有权重的总和。因此,具有两个孩子的节点将整个字符串分成两部分:左子树存储字符串的第一部分。右子树存储第二部分,其权重是两部分之和。

我有点困惑,它首先说节点权重是其字符串的长度加上其左子树中所有权重的总和。然后它说如果一个节点有两个孩子(因此有一个左子树和一个右子树),那么权重是两个部分的总和,而不仅仅是左子树。看图是有道理的(22 正下方的 9 是 9 并且不是更大,因为 7 的右子树/子树对权重没有贡献)但是措辞对我来说似乎是错误的,还是我误解了什么?

4

1 回答 1

1

是的,句号掉线了。“权重”是分区点,所以它只包括左子字符串(或包含的字符串,如果你有的话)。

您不需要存储节点的总长度,但修改绳索需要通知所有父节点更改(应该是 O(log n),所以没关系。)

于 2012-09-24T00:03:54.027 回答