0

ウィキペディアのエントリは言う:

各ノードには、文字列の長さに左側のサブツリーのすべての重みの合計を加えたものに等しい「重み」があります。したがって、2つの子を持つノードは、文字列全体を2つの部分に分割します。左側のサブツリーには、文字列の最初の部分が格納されます。右側のサブツリーには2番目の部分が格納され、その重みは2つの部分の合計です。

私は少し混乱しています。最初に、ノードの重みは文字列の長さに左側のサブツリーのすべての重みの合計を加えたものであると言います。次に、ノードに2つの子(したがって、左と右のサブツリー)がある場合、重みは、左のサブツリーだけでなく、両方の部分の合計であると表示されます。ダイアグラムを見るのは理にかなっていますが(22のすぐ下の9は9であり、7の正しい子/サブツリーは重みに寄与しないため、大きくはありません)、言い回しは私にはわかりませんか、それとも私は何かを誤解していますか?

4

1 に答える 1

1

ええ、言い回しはオフです。「重み」はパーティションポイントであるため、左側のサブ文字列(または、代わりに含まれている文字列の場合は含まれている文字列)のみが含まれます。

ノードの全長を保存する必要はありませんが、ロープを変更するには、すべての親ノードに変更を通知する必要があります(O(log n)である必要があるため、問題ありません)。

于 2012-09-24T00:03:54.027 に答える