2

文字列の代替データ構造としてロープ ツリーを実装しようとしています。

ウィキペディアのページには、ツリーを分割するためのルールが不明ですが、これらのルールは最初は機能しているように見えました。ただし、いくつかの分割操作の後、無効なツリーになりました。

          6
          /\
         /  \
        4    \
       /\     \    
      /  \     \
     /    2     4
    /     /\    /\
   4     2  3  4 7
   A     B  C  D E

数字はノードの重みを表し、葉の場合は部分文字列の長さを表します。この不正なツリーでは、部分文字列 C に到達することはできません。

良い木の例. ウィキペディアの説明に従って、すべての文字に到達できます。

        6
        /\
       /  \
      /   7    
     /    /\
    4    3  \
   / \  / \  \
   4  2 3 4   7
   A  B C D   E

私は CS のバックグラウンドがないので、ツリーの何が問題なのかわかりません。このツリーの問題を適切に表現する方法さえわかりません。このツリーの (CS 用語での) 何が問題で、どうすれば解決できますか?

4

1 に答える 1

2

ルートは次の不変条件に違反しています。

各ノードの重みは、左側のサブツリー内のすべての葉の重みの合計です。

2 番目のツリーは、構造を変更することで不変条件を修正しますが、これは必須ではありません。同じ構造で異なる重みを使用した修正版を次に示します。

     r: 9
       /\
      /  \
  a: 4    \
    /\     \    
   /  \     \
  / b: 2     4
 /     /\    /\
4     2  3  4  7
A     B  C  D  E

Cの最初の文字(1 ベースのインデックスを想定した場合は 7番目の文字) に到達するにIndex(r, 7)は、ウィキペディアの記事に従って実行します。「ログ」は次のとおりです。

  • 7 < 9 であることを確認します。Index(a, 7)
  • 7 > 4 であることを確認します。Index(b, 3)
  • 3 > 2 であることを確認します。Index(C, 1)
  • の最初の文字を返すC

補遺:

ウィキペディアの記事では、次の (異なる!) 不変条件が提案されていることに注意してください。

各ノードの「重み」は、その文字列の長さに左側のサブツリー内のすべての重みの合計を加えたものです。

この定式化は、すぐ上の図と一致しません。

ウィキペディア ロープ ツリーの例

上記の不変式によると、図のノードBの重みは 15 である必要があります。

于 2014-02-25T19:26:52.387 に答える